Re: vector swap time complexity
Michael Doubez wrote:
On 15 sep, 14:59, thomas <freshtho...@gmail.com> 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.
From ?23.1/5, I imagine the swap operation could be o(N) - because of
the infamous Note A - but requirements of ?23.1/10 (i.e. swap doesn't
invalidate pointer, reference and iterators to elements) makes it
impossible in practice.
Why? The pointer is not invalidated, it just points to an element in
another container (and so does a reference or an iterator). Consider:
std::vector<int> onetwothree;
onetwothree.push_back(1);
onetwothree.push_back(2);
onetwothree.push_back(3);
int *p1 = &onetwothree[1];
assert(*p1 == 2);
std::vector<int> fivesixseven;
fivesixseven.push_back(5);
fivesixseven.push_back(6);
fivesixseven.push_back(7);
int *p2 = &fivesixseven[0];
assert(*p2 == 5);
std::swap(onetwothree, fivesixseven);
// the pointers are still valid, and even point to the same
// elements (by value) as before
assert(*p1 == 2);
assert(*p2 == 5);
Do the same exercise for references or iterators.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask