Re: vector swap time complexity
Francesco S. Carta wrote:
On 15 Set, 15:33, Pete Becker <p...@versatilecoding.com> wrote:
Sudarshan Narasimhan wrote:
On Sep 15, 5:22 pm, thomas <freshtho...@gmail.com> 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);
but how about "swap" between two "vector" or "map"?
can it be still O(1)?
I think it can be O(1) since the implementation of "&" is similar to
"pointer", so swap can be done between two "pointers".
But I don't know what exactly the designers think. Any comments?
IMHO, if the pointers are swapped, you should be able to see a swap in
the addresses of the objects which have been swapped. It doesnt seem
to be the case. Also, looks like swap runs in constant time
irrespective of the type of the objects. So i suspect it to be a
memcpy between the two location with some buffer being used for
holding up during transfer. However, i havent seen the implementation,
i will let someone who knows clarify it up.
struct simple_vector
{
int *data;
int count;
};
Swapping two of these objects requires swapping their data pointers and
their counts. That's all. std::vector has a few more internal details,
but its data storage is simply a pointer and a count.
Hi,
just a passing by question.
Is the following code "good" to check an implementation for the above
behavior?
AFAICT, no.
-------
#include <iostream>
#include <vector>
using namespace std;
void dump(vector<char>* pv) {
size_t* pc = reinterpret_cast<size_t*>(pv);
Huh??? 8-O
I suppose you figured that the first member of 'vector<char>' has the
type 'size_t', and while it's private and you can't get to it using
normal member access, you're trying to "cheat" here and get that value
using 'reinterpret_cast'. Well, first off, this is an illegal use of
'reinterpret_cast', so your code (which is already non-portable) has
undefined behaviour. Second, why are you treating 'pc' as a pointer to
an array of 'size_t'? It would seem that it requires *all* members of
'vector<char>' to be (a) of type 'size_t' and (b) be placed sequentially
in memory. Neither is necessarily true, so you have undefined behaviour
*again* when you try to dereference (pc + i).
for (size_t i = 0, e = sizeof(*pv) / sizeof(size_t);
i < e;
++i) {
cout << *(pc + i) << " ";
}
cout << endl;
}
[..]
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask