Re: vector swap time complexity
On 15 Set, 16:20, Victor Bazarov <v.Abaza...@comAcast.net> wrote:
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 i=
n
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 an=
d
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 behaviou=
r
*again* when you try to dereference (pc + i).
Oh, yes, of course I know that it's a cheat! Sorry for not making this
clear from starters.
Also about dereferencing pc, I'm just using it as a cheat to look into
memory that doesn't belong to me.
I take your response as a confirmation that the code I posted is _not_
ethic ;-)
BTW, should I have preferred a C-style cast such as "(size_t*)pv"
instead of reinterpret_cast, in such a cheat?
Cheers,
Francesco
____________________________
Francesco S. Carta, hobbyist
http://fscode.altervista.org