Re: vector swap time complexity
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?
-------
#include <iostream>
#include <vector>
using namespace std;
void dump(vector<char>* pv) {
size_t* pc = reinterpret_cast<size_t*>(pv);
for (size_t i = 0, e = sizeof(*pv) / sizeof(size_t);
i < e;
++i) {
cout << *(pc + i) << " ";
}
cout << endl;
}
void print(vector<char>* v, vector<char>* w) {
cout << " v == ";
dump(v);
cout << "&v[0] == " << size_t(&(*v)[0]) << endl;
cout << " w == ";
dump(w);
cout << "&w[0] == " << size_t(&(*w)[0]) << endl;
cout << endl;
}
int main()
{
vector<char> v;
vector<char> w;
v.push_back('v');
w.push_back('w');
print(&v, &w);
cout << "swap(v, w);" << endl << endl;
swap(v, w);
print(&v, &w);
return 0;
}
-------
The output on my machine...
-------
v == 205960 205961 205961
&v[0] == 205960
w == 206088 206089 206089
&w[0] == 206088
swap(v, w);
v == 206088 206089 206089
&v[0] == 206088
w == 205960 205961 205961
&w[0] == 205960
-------
....seems to confirm it - but the problem here is that I'm not sure
about the dump() function and about sizeof() in particular.
Pardon the drift.
Best regards,
Francesco
____________________________
Francesco S. Carta, hobbyist
http://fscode.altervista.org