Re: vector swap time complexity
thomas wrote:
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.
Well, I am no sure if we are at the same page about the meaning of O
(1).
I suspect it can be O(n), where "n" refers to the size of the type T
(such as a vector).
Of course, it's always O(1) regarding to the whole object T.
The time complexity of vector swap is constant, regardless of how many
elements the vector holds.
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.
ok.
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?
Yeah, I suspect the implementors may perform some tricks to achieve
better time performance.
Actually I may find it difficult to balance if I was the designer.
I don't know what exactly the designers think either.
Then how can you know it's exactly O(1) if you don't know what's
inside?
Some code supporting the O(n) perspective:
------code-----------
vector<int> p(1,0);
for(int i=0; i<10; i++){
vector<int> q(2,0);
q.swap(p);
}
------code-----------
The only implementation trick to achieve O(1) is by swap "pointer"
like address.
But it surely cannot work here, because "q" in the stack vanishes out
of the "{}" scope.
So the address of "q" becomes invalid.
But the address of the stored data remains valid, because it's allocated
on the free store. So the data pointer in q is swapped with the data
pointer in p, and the other fields in the two vectors are also swapped.
Constant time, regardless of how many elements the vector holds.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of
"The Standard C++ Library Extensions: a Tutorial and Reference"
(www.petebecker.com/tr1book)