Re: vector swap time complexity
thomas wrote:
vector<int> A(2,0);
vector<int> B(3,0);
A.swap(B);
swap(A, B);
------------code------------
for simple "int" structure, the time complexity of "swap(&int,&int)"
is simply O(1);
Actually, for any type T vector<T>.swap(othervector) has complexity of
O(1) - the data storages and other fields are exchanged between the
objects, no data outside of the actual 'vector<T>' object moves.
but how about "swap" between two "vector" or "map"?
can it be still O(1)?
I am fairly certain that 'std::swap' is overloaded for vectors (and all
other standard containers) to call the member function 'swap' (which
will do the swap quickly). So, std::swap<std::vector<T> > is also of
O(1) complexity.
I think it can be O(1) since the implementation of "&" is similar to
"pointer", so swap can be done between two "pointers".
No particular implementation of references is mandated. What makes you
believe that it's <<similar to "pointer">>? There is no way in the
language to "reseat" a reference. What would the implementation of
'std::swap' look like without that ability? Or do you think there is
some magic (assembly) trick the library implementors perform?
But I don't know what exactly the designers think. Any comments?
I don't know what exactly the designers think either.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask