Re: vector swap time complexity
On 15 Set, 16:29, "Francesco S. Carta" <entul...@gmail.com> wrote:
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=
in
the addresses of the objects which have been swapped. It doesnt see=
m
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 implementati=
on,
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 detail=
s,
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 o=
f
'vector<char>' to be (a) of type 'size_t' and (b) be placed sequentiall=
y
in memory. Neither is necessarily true, so you have undefined behavi=
our
*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?
Well, never mind. Actually, checking for the address of individual
elements accessible from operator[], as we both did, is enough to
verify that behavior.
Just as a side note, Victor, I understand the points you mentioned
about the members, their size and their disposition in memory, and I
understand that such kind of cheats isn't absolutely on-topic here.
I just like to fiddle with things to get better insights. For example,
seems that my implementation of std::vector stores objects in an
array, stores the address of the first element of the array in the
first member and the address of the element one-past-the-end as the
second or the third member. My "seems", of course, doesn't ensure
anything and the best way to know an implementation detail is to
actually read it.
Once more, sorry for the drift. All and just experimental purposes -
for what they are worth :-/
Cheers,
Francesco
____________________________
Francesco S. Carta, hobbyist
http://fscode.altervista.org