STL container question

[Ioannis Vranos]

Doesn't a swap sort of imply a copy of "something"?

struct object {
int x;
};

object objs[2] = { { 0 }, { 1 } };

How do you swap `obj[0]' with `obj[1]' without copying "something"?

A vector::swap() can be a shallow swap. For example if a vector is
implemented as a pointer pointing to an array on the free store, swap
could just swap the pointer values, without interfering with the contents.

 

[Ioannis Vranos]

The program had a serious bug.


corrected:

Hendrik Schober wrote:
Ioannis Vranos wrote:
[...]
We must think generally. In general, sorting a list is faster than
sorting a vector, because the list sorting does not involve the
construction or destruction of any object.

Regarding ints, I think sorting a vector of ints and as list of
ints, both have about the same efficiency.
Why don't you just measure before you doubt the statements
of those who already went and did this?

On my platform, this

[ Non-portable code...]



and thus again disagrees with you.

Eagerly awaiting your counter example,

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <cstddef>
#include <algorithm>


class SomeClass
{
typedef std::vector<int> TypeVector;

TypeVector vec;

enum { VectorSize= 1000 };

public:

SomeClass();

bool operator<(const SomeClass &argSomeClass) const
{
return vec[0]< argSomeClass.vec[0];
}
};





int main()
{
using namespace std;

srand(time(0));

const size_t SIZE=10000;

typedef vector<SomeClass> Vector;
typedef list<SomeClass> List;


cout<< "\nCreating vector with "<< SIZE<< " elements..."<< flush;
Vector vec(SIZE);

cout<<" Done!\n\n"<< flush;

===> List lis;


cout<< "Filling list with vector elements..."<< flush;

for(Vector::size_type i= 0; i< vec.size(); ++i)
lis.push_back(vec);

cout<< " Done!\n\n"<< flush;


clock_t timeBeginVector, timeEndVector, timeBeginList, timeEndList;


cout<< "Timing the sorting of the vector..."<< flush;

timeBeginVector= clock();

sort(vec.begin(), vec.end());

timeEndVector= clock();

cout<< " Done!\n\n"<< flush;


cout<< "Timing the sorting of the list..."<< flush;

timeBeginList= clock();

lis.sort();

timeEndList= clock();


cout<< " Done!\n\n"<< flush;


cout<< "The sorting of the vector took "
<< static_cast<double>((timeEndVector- timeBeginVector))/
CLOCKS_PER_SEC
<< " seconds\n\n";

cout<< "The sorting of the list took "
<< static_cast<double>((timeEndList- timeBeginList))/
CLOCKS_PER_SEC
<< " seconds\n\n";
}



SomeClass::SomeClass():vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

This program doesn't sort at all, because the vec is initialized with
one constant!

? Yes it is initalised with its number of elements, which are SomeClass
objects created with their default constructor.

Change the list filling code to

for(Vector::size_type i= 0; i< vec.size(); ++i) {
vec= SomeClass();
lis.push_back(vec);
}

Why?

 

[Lars Tetzlaff]

The program had a serious bug.


corrected:


Ioannis Vranos wrote:
Hendrik Schober wrote:
Ioannis Vranos wrote:
[...]
We must think generally. In general, sorting a list is faster than
sorting a vector, because the list sorting does not involve the
construction or destruction of any object.

Regarding ints, I think sorting a vector of ints and as list of
ints, both have about the same efficiency.
Why don't you just measure before you doubt the statements
of those who already went and did this?

On my platform, this

[ Non-portable code...]



and thus again disagrees with you.

Eagerly awaiting your counter example,

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <cstddef>
#include <algorithm>


class SomeClass
{
typedef std::vector<int> TypeVector;

TypeVector vec;

enum { VectorSize= 1000 };

public:

SomeClass();

bool operator<(const SomeClass &argSomeClass) const
{
return vec[0]< argSomeClass.vec[0];
}
};





int main()
{
using namespace std;

srand(time(0));

const size_t SIZE=10000;

typedef vector<SomeClass> Vector;
typedef list<SomeClass> List;


cout<< "\nCreating vector with "<< SIZE<< " elements..."<< flush;
Vector vec(SIZE);

cout<<" Done!\n\n"<< flush;

===> List lis;


cout<< "Filling list with vector elements..."<< flush;

for(Vector::size_type i= 0; i< vec.size(); ++i)
lis.push_back(vec);

cout<< " Done!\n\n"<< flush;


clock_t timeBeginVector, timeEndVector, timeBeginList, timeEndList;


cout<< "Timing the sorting of the vector..."<< flush;

timeBeginVector= clock();

sort(vec.begin(), vec.end());

timeEndVector= clock();

cout<< " Done!\n\n"<< flush;


cout<< "Timing the sorting of the list..."<< flush;

timeBeginList= clock();

lis.sort();

timeEndList= clock();


cout<< " Done!\n\n"<< flush;


cout<< "The sorting of the vector took "
<< static_cast<double>((timeEndVector- timeBeginVector))/
CLOCKS_PER_SEC
<< " seconds\n\n";

cout<< "The sorting of the list took "
<< static_cast<double>((timeEndList- timeBeginList))/
CLOCKS_PER_SEC
<< " seconds\n\n";
}



SomeClass::SomeClass():vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

This program doesn't sort at all, because the vec is initialized with
one constant!

? Yes it is initalised with its number of elements, which are SomeClass
objects created with their default constructor.

On my system all values are equal. The constructor is only called once!
The other elements are initialized with a copy of this SomeClass object!

Don't know what the standard says about this ...

Change the list filling code to

for(Vector::size_type i= 0; i< vec.size(); ++i) {
vec= SomeClass();
lis.push_back(vec);
}

Why?

To get distinct elements. See above.


Lars

 

[Ioannis Vranos]

corrected:

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <cstddef>
#include <algorithm>


class SomeClass
{
typedef std::vector<int> TypeVector;

TypeVector vec;

enum { VectorSize= 1000 };

public:

SomeClass();

bool operator<(const SomeClass &argSomeClass) const
{
return vec[0]< argSomeClass.vec[0];
}
};





int main()
{
using namespace std;

srand(time(0));

const size_t SIZE=10000;

typedef vector<SomeClass> Vector;
typedef list<SomeClass> List;


cout<< "\nCreating vector with "<< SIZE<< " elements..."<< flush;
Vector vec(SIZE);

cout<<" Done!\n\n"<< flush;

===> List lis;


cout<< "Filling list with vector elements..."<< flush;

for(Vector::size_type i= 0; i< vec.size(); ++i)
lis.push_back(vec);

cout<< " Done!\n\n"<< flush;


clock_t timeBeginVector, timeEndVector, timeBeginList, timeEndList;


cout<< "Timing the sorting of the vector..."<< flush;

timeBeginVector= clock();

sort(vec.begin(), vec.end());

timeEndVector= clock();

cout<< " Done!\n\n"<< flush;


cout<< "Timing the sorting of the list..."<< flush;

timeBeginList= clock();

lis.sort();

timeEndList= clock();


cout<< " Done!\n\n"<< flush;


cout<< "The sorting of the vector took "
<< static_cast<double>((timeEndVector- timeBeginVector))/
CLOCKS_PER_SEC
<< " seconds\n\n";

cout<< "The sorting of the list took "
<< static_cast<double>((timeEndList- timeBeginList))/
CLOCKS_PER_SEC
<< " seconds\n\n";
}



SomeClass::SomeClass():vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

>
>

This program doesn't sort at all, because the vec is initialized with
one constant!

? Yes it is initalised with its number of elements, which are SomeClass
objects created with their default constructor.

On my system all values are equal. The constructor is only called once!
The other elements are initialized with a copy of this SomeClass object!

There are two vecs in the code. Please be more specific, which are you
referring to?

 

[Lars Tetzlaff]

corrected:

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <cstddef>
#include <algorithm>


class SomeClass
{
typedef std::vector<int> TypeVector;

TypeVector vec;

enum { VectorSize= 1000 };

public:

SomeClass();

bool operator<(const SomeClass &argSomeClass) const
{
return vec[0]< argSomeClass.vec[0];
}
};





int main()
{
using namespace std;

srand(time(0));

const size_t SIZE=10000;

typedef vector<SomeClass> Vector;
typedef list<SomeClass> List;


cout<< "\nCreating vector with "<< SIZE<< " elements..."<< flush;
Vector vec(SIZE);

cout<<" Done!\n\n"<< flush;

===> List lis;


cout<< "Filling list with vector elements..."<< flush;

for(Vector::size_type i= 0; i< vec.size(); ++i)
lis.push_back(vec);

cout<< " Done!\n\n"<< flush;


clock_t timeBeginVector, timeEndVector, timeBeginList, timeEndList;


cout<< "Timing the sorting of the vector..."<< flush;

timeBeginVector= clock();

sort(vec.begin(), vec.end());

timeEndVector= clock();

cout<< " Done!\n\n"<< flush;


cout<< "Timing the sorting of the list..."<< flush;

timeBeginList= clock();

lis.sort();

timeEndList= clock();


cout<< " Done!\n\n"<< flush;


cout<< "The sorting of the vector took "
<< static_cast<double>((timeEndVector- timeBeginVector))/
CLOCKS_PER_SEC
<< " seconds\n\n";

cout<< "The sorting of the list took "
<< static_cast<double>((timeEndList- timeBeginList))/
CLOCKS_PER_SEC
<< " seconds\n\n";
}



SomeClass::SomeClass():vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

This program doesn't sort at all, because the vec is initialized with
one constant!

? Yes it is initalised with its number of elements, which are SomeClass
objects created with their default constructor.

On my system all values are equal. The constructor is only called once!
The other elements are initialized with a copy of this SomeClass object!

There are two vecs in the code. Please be more specific, which are you
referring to?

Vector vec(SIZE); in main.

Lars

 

[Ioannis Vranos]

Vector vec(SIZE); in main.

Already spotted the strange behaviour and posted a new message with the
subject "Strange behaviour".

 

[Rolf Magnus]

The program had a serious bug.


corrected:
[...]

Creating vector with 100000 elements... Done!
Filling list with vector elements... Done!
Timing the sorting of the vector... Done!
Timing the sorting of the list... Done!
The sorting of the vector took 0.015 seconds
The sorting of the list took 0.437 seconds

Again, increase the number of const size_t SIZE so as to exceed 1-2
seconds for the sorting of one container, and then post your results.

What does your example have to do with the OP's question? The OP has one int
as member, while in your code, each element contains a vector of 1000 ints
instead. If this proves anything, then that you can construct a situation
where a list is faster than a vector. Unfortunately, that situation has
nothing to do with the OP's question.

 

[Chris M. Thomasson]

Doesn't a swap sort of imply a copy of "something"?

struct object {
int x;
};

object objs[2] = { { 0 }, { 1 } };

How do you swap `obj[0]' with `obj[1]' without copying "something"?

A vector::swap() can be a shallow swap. For example if a vector is
implemented as a pointer pointing to an array on the free store, swap
could just swap the pointer values, without interfering with the contents.

My point was that "something" is copied; in this case a pointer value.
However, in this case, that statement would be a ridiculous nit-pick!

;^)

 

[Chris M. Thomasson]

Doesn't a swap sort of imply a copy of "something"?

struct object {
int x;
};

object objs[2] = { { 0 }, { 1 } };

How do you swap `obj[0]' with `obj[1]' without copying "something"?

A vector::swap() can be a shallow swap. For example if a vector is
implemented as a pointer pointing to an array on the free store, swap
could just swap the pointer values, without interfering with the
contents.

My point was that "something" is copied; in this case a pointer value.
However, in this case, that statement would be a ridiculous nit-pick!

;^)

Anyway, I this was about sorting vectors... AFAICT, this implies some
swapping of the contents of slots in the array, and swapping implies
"something" is copied. If its a pointer value, so be it. If not, well, then
things can start to get expensive. The sort and swap impl needs to be very
highly optimized indeed.

 

[Chris M. Thomasson]

Chris M. Thomasson wrote:


Doesn't a swap sort of imply a copy of "something"?

struct object {
int x;
};

object objs[2] = { { 0 }, { 1 } };

How do you swap `obj[0]' with `obj[1]' without copying "something"?



A vector::swap() can be a shallow swap. For example if a vector is
implemented as a pointer pointing to an array on the free store, swap
could just swap the pointer values, without interfering with the
contents.

My point was that "something" is copied; in this case a pointer value.
However, in this case, that statement would be a ridiculous nit-pick!

;^)

Anyway, I this was about sorting vectors...

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Anyway, I _thought_ this was about sorting vectors...


ARGH!

 

[Chris M. Thomasson]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

You are correct that as lists do not provide random-access iterators
quicksort can not be used.

Actually, that's not true. It's entirely possible to implement a
quicksort on a linked list. You can't (efficiently) use a median-of-
three (or whatever) pivot selection, but the quicksort itself has no
need for random-access iteration.

You can use quick-sort on a skip-list where one of the skip-links points to
the middle of the list, or some other pivot.

 

[Erik Wikström]

The program had a serious bug.

[...]


And my results:


1. const size_t SIZE= 90000;


john@john-desktop:~/Projects/src$ ./foobar_cpp

Creating vector with 90000 elements... Done!

Filling list with vector elements... Done!

Timing the sorting of the vector... Done!

Timing the sorting of the list... Done!

The sorting of the vector took 24.79 seconds

The sorting of the list took 0.1 seconds

I managed to duplicate your results once, but only once. Despite
numerous tries your code consistently shows the vector being at least an
order of magnitude faster. Make sure your are not running other CPU-
intensive applications while running the test.

The system I tested on is DELL T7400 (dual Intel Xeon quad core), Vista
Ultimate 64, Visual C++ 2008 sp1, 4 gigs of RAM. Since no parallelizing
is done in your program, the number of cores doesn't matter, but the CPU
is faster, and while I would love to try it on a 16-gigabyte machine or
better, I don't have access to one. My machine is what our clients are
getting, so the results stand. You're free to speculate what makes it
so *bad* on your machine, but I'd seriously think about switching to a
real OS and a real compiler, if I got such bad results as you do.

Long since I last heard anyone calling Linux and gcc toy products.

 

[Ioannis Vranos]

OK, as it was determined, your compiler has a bug (that makes it invoke
the default c-tor for all elements of a vector constructed with only the
size given.

Actually from the responses I got in the "Strange behaviour (corrected)"
thread, it isn't a bug.

I've added a copy constructor that does exactly the same
thing as the default constructor and finally got your results. A vector
of large objects with random values takes longer to sort than a list of
large objects with similarly random values. Significantly longer. Your
theory is confirmed, I suppose.

Now, it has really nothing to do with the OP's problem, but still...

Strangely enough there should be no difference. With the default copy
constructor I get the differences I mentioned, while you get them only
when you define the copy constructor explicitly.

 

[jl_post]

If the programmer decides to replace ints with other objects, he will
not have to change much in the code, if he uses a list.

Even if he uses a std::vector, he still won't have to change much
in the code.

In my experience, it is usually not a good thing to write code
optimized for something that "might" happen in the future. If it does
happen, let the coder change it then, and not earlier.

I've seen code where data was stored in a list (or vector), but
nothing whatsoever was being done with the list after that. When I
asked the original coder why it was there, the reply was, "So that if
a future coder needs a list of the data, it's there to use."

Seriously, though, if you saw a list or vector that had did nothing
other than being populated, wouldn't you think it was a bug (or at
least vestigial code that was forgotten to be removed)?

I mean, if I had to add code that required me to use a list/vector
of that data, I would probably declare and populate my own list (who
wouldn't?). Even if I did see the first list (the one written for
future use), I would probably pass it over thinking it was needed for
some other piece of code -- fearing that if I manipulated it in any
way it might break current functional code.

To be honest, I think the STL sort algorithms are efficient enough
that the type of container they sort doesn't really matter in the long
run. In other words, they scale well enough that their difference in
speed can be pretty much considered negligible.

That being said, I think the original poster should use the
container that best suits the problem best. If the data is meant to
be used as a linked-list, then he/she should use a std::list. If the
data is meant to be used as a vector, then he/she should use a
std::vector.

Personally, I would suggest using a std::set, since it seems like
all he/she needs the container for is for checking to see if a number
is among the set of numbers he/she has already encountered -- unless
he/she also needs to use the set of numbers somewhere else as a list
or a vector.

Take care,

-- Jean-Luc

 

[Ioannis Vranos]

Actually from the responses I got in the "Strange behaviour (corrected)"
thread, it isn't a bug.






Strangely enough there should be no difference. With the default copy
constructor I get the differences I mentioned, while you get them only
when you define the copy constructor explicitly.

Disregard this message of mine.

 

[Ioannis Vranos]

Second correction:


#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <cstddef>
#include <algorithm>


class SomeClass
{
typedef std::vector<int> TypeVector;

TypeVector vec;

enum { VectorSize= 1000 };

public:

SomeClass();
SomeClass(const SomeClass &);

bool operator<(const SomeClass &argSomeClass) const
{
return vec[0]< argSomeClass.vec[0];
}
};





int main()
{
using namespace std;

srand(time(0));

const size_t SIZE=1000;

typedef vector<SomeClass> Vector;
typedef list<SomeClass> List;


cout<< "\nCreating vector with "<< SIZE<< " elements..."<< flush;
Vector vec(SIZE);

cout<<" Done!\n\n"<< flush;

List lis;


cout<< "Filling list with vector elements..."<< flush;

for(Vector::size_type i= 0; i< vec.size(); ++i)
lis.push_back(vec);

cout<< " Done!\n\n"<< flush;


clock_t timeBeginVector, timeEndVector, timeBeginList, timeEndList;


cout<< "Timing the sorting of the vector..."<< flush;

timeBeginVector= clock();

sort(vec.begin(), vec.end());

timeEndVector= clock();

cout<< " Done!\n\n"<< flush;


cout<< "Timing the sorting of the list..."<< flush;

timeBeginList= clock();

lis.sort();

timeEndList= clock();


cout<< " Done!\n\n"<< flush;


cout<< "The sorting of the vector took "
<< static_cast<double>((timeEndVector- timeBeginVector))/
CLOCKS_PER_SEC
<< " seconds\n\n";

cout<< "The sorting of the list took "
<< static_cast<double>((timeEndList- timeBeginList))/
CLOCKS_PER_SEC
<< " seconds\n\n";
}



SomeClass::SomeClass():vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}


==> SomeClass::SomeClass(const SomeClass &):vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

 

[Ioannis Vranos]

Personally, I would suggest using a std::set, since it seems like
all he/she needs the container for is for checking to see if a number
is among the set of numbers he/she has already encountered -- unless
he/she also needs to use the set of numbers somewhere else as a list
or a vector.

I also think std::set is the answer for the OP.

 

[Jerry Coffin]

Not true.

Granted, you can't do it for the *first* partition, but there's no
problem in getting the median-of-three pivot in subsequent partitions.

Quite true -- my statement was sufficiently incomplete that it wasn't
really accurate as stated. Thanks for the correction.

 

[Lars Tetzlaff]

Second correction:


==> SomeClass::SomeClass(const SomeClass &):vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

You will never get a sorted vector. Every time you copy an element you
will change it's value!

Lars

 

[Ioannis Vranos]

Second correction:


==> SomeClass::SomeClass(const SomeClass &):vec(VectorSize)
{
using namespace std;

for(TypeVector::size_type i= 0; i< vec.size(); ++i)
vec= rand();

sort(vec.begin(), vec.end());
}

You will never get a sorted vector. Every time you copy an element you
will change it's value!

I think during sort(), the default assignment operator is used, and not
the copy constructor.