STL container question

M

Maxim Yegorushkin

In other words, no. <g> One could also point out that quicksort can be
used to sort a vector but can't be used on a list, so obviously sorting
a vector is faster.
Click to expand...

Not always so.

You are correct that as lists do not provide random-access iterators
quicksort can not be used. Instead, lists are normally sorted using
merge sort. Merge sort has better worst-case performance than
quicksort. The drawback of merge sort is that it normally requires
extra memory, whereas quicksort does not.

http://en.wikipedia.org/wiki/Merge_sort
<quote>
In the worst case, merge sort does about 39% fewer comparisons than
quicksort does in the average case; merge sort always makes fewer
comparisons than quicksort, except in extremely rare cases, when they
tie, where merge sort's worst case is found simultaneously with
quicksort's best case. In terms of moves, merge sort's worst case
complexity is O(n log n)—the same complexity as quicksort's best case,
and merge sort's best case takes about half as many iterations as the
worst case.
</quote>
 
I

Ioannis Vranos

Hendrik said:
Ioannis said:
[...]
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.
Click to expand...

Why don't you just measure before you doubt the statements
of those who already went and did this?

On my platform, this
Click to expand...


[ Non-portable code...]


and thus again disagrees with you.

Eagerly awaiting your counter example,
Click to expand...


#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(vec.size());


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());
}
 
H

Hendrik Schober

Ioannis said:
Hendrik said:
Ioannis said:
[...]
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.
Click to expand...
Why don't you just measure before you doubt the statements
of those who already went and did this?

On my platform, this
Click to expand...


[ Non-portable code...]


and thus again disagrees with you.

Eagerly awaiting your counter example,
Click to expand...


Code: 
[/QUOTE]

  I had to add another zero in order to get sensible results:

    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.016 seconds
    The sorting of the list took 0.468 seconds

  HTH,

  Schobi
Click to expand...
 
I

Ioannis Vranos

Hendrik said:
Ioannis said:
Hendrik said:
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
Click to expand...


[ Non-portable code...]


and thus again disagrees with you.

Eagerly awaiting your counter example,
Click to expand...


Code: 
[/QUOTE]

I had to add another zero in order to get sensible results:

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.016 seconds
The sorting of the list took 0.468 seconds[/QUOTE]



Your computer is faster than mine and probably with more RAM.


In my computer with SIZE 10000:


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

Creating vector with 10000 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 2.55 seconds

The sorting of the list took 0.02 seconds

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





In my computer with SIZE 100000 (uses swap):


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

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 27.46 seconds

The sorting of the list took 4.58 seconds

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



==> The timings less than 1 second are not conclusive. Add 0s until you 
exceed 1-2 seconds.
Click to expand...
Click to expand...
 
H

Hendrik Schober

Ioannis said:
[...]
==> The timings less than 1 second are not conclusive. Add 0s until you
exceed 1-2 seconds.
Click to expand...

If I add a single one more, the program runsout of memory.

Schobi
 
I

Ioannis Vranos

The program had a serious bug.


corrected:


Ioannis said:
Hendrik said:
Ioannis said:
[...]
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.
Click to expand...

Why don't you just measure before you doubt the statements
of those who already went and did this?

On my platform, this
Click to expand...


[ Non-portable code...]


and thus again disagrees with you.

Eagerly awaiting your counter example,
Click to expand...
Click to expand...


#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());
}
 
H

Hendrik Schober

Ioannis said:
The program had a serious bug.


corrected:
[...]
Click to expand...

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

Schobi
 
I

Ioannis Vranos

Ioannis said:
The program had a serious bug.


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());
}
Click to expand...




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

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



2. const size_t SIZE= 100000;

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

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 26.8 seconds

The sorting of the list took 0.1 seconds

john@john-desktop:~/Projects/src$
 
I

Ioannis Vranos

Hendrik said:
Ioannis said:
The program had a serious bug.


corrected:
[...]
Click to expand...

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
Click to expand...



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.


For example try

const size_t SIZE= 400000;
 
I

Ioannis Vranos

Victor said:
This exercise is pointless. I made 200K elements (no swap, but the
computer uses up to 2.5G of RAM, probably mostly due to the need to keep
all the pointers in the list elements) and I still consistently get


Creating vector with 200000 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.156 seconds

What is it you're trying to prove? That your computer and your
implementation are dilapidated? Get a better compiler.
Click to expand...



The specific code had a serious bug (list had double elements than
vector). Also differences in milliseconds have no point (are inconclusive).
 
I

Ioannis Vranos

Ioannis said:
The program had a serious bug.
Click to expand...

> [...]
>
>
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

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



2. const size_t SIZE= 100000;

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

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 26.8 seconds

The sorting of the list took 0.1 seconds

john@john-desktop:~/Projects/src$
Click to expand...



Just for the record, my system is:


OS: Ubuntu 8.04 x86.

Compiler: gcc version 4.2.3 (Ubuntu 4.2.3-2ubuntu7)

Hardware: Pentium III 1 GHz, 1 GB RAM.
 
I

Ioannis Vranos

Victor said:
What is it you're trying to prove? That your computer and your
implementation are dilapidated? Get a better compiler.
Click to expand...


Apart from the bug, sorting a list, does not involve the construction or
destruction of any object, while in the case of vector, element objects
are copied.
 
I

Ioannis Vranos

Victor said:
Tell me again, what does your example prove? And, again, get a better
compiler and a better library. Whatever version you're using is *crap*,
obviously.
Click to expand...


Do you agree that sorting a list does not involve object creation, while
sorting a vector involves the copying of the object elements?
 
R

Richard Herring

Ioannis Vranos said:
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.
Click to expand...

So how many constructions and destructions does std::sort involve?
Regarding ints, I think sorting a vector of ints and as list of ints,
both have about the same efficiency.
Click to expand...

How many integer assignments to swap two ints in a vector?
How many pointer assignments to swap two elements in a list?
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.
Click to expand...

What would he have to change with a vector?
 
C

Chris M. Thomasson

Victor Bazarov said:
Whatever it involves (and I'd think it would actually be *swapping* and
not assignment or copying),
Click to expand...


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"?



apparently *your library* does it in a very unacceptable manner.
You can theorize as much as you want, but in the end the results only
prove that one needs to measure before coming to any conclusions. Logic
does not always work well...
Click to expand...

;^)
 
L

Lars Tetzlaff

Ioannis said:
The program had a serious bug.


corrected:


Ioannis said:
Hendrik said:
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
Click to expand...


[ Non-portable code...]


and thus again disagrees with you.

Eagerly awaiting your counter example,
Click to expand...
Click to expand...


#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());
}
Click to expand...


This program doesn't sort at all, because the vec is initialized with
one constant! Change the list filling code to

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


and you have something to sort.

My result on OpenSuse 11 64Bit with Phenom 9850 and 4GB RAM, gcc 4.3.1,
const size_t SIZE=100000, compiled with g++ -O3 :

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 1.12 seconds

The sorting of the list took 0.12 seconds



Lars
 
J

Jerry Coffin

(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.
Click to expand...

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.
Instead, lists are normally sorted using merge sort.
Click to expand...

This, however, is true. Even though you _can_ use quicksort on a linked
list, the potential gains from doing so are much smaller than the
potential losses.
Merge sort has better worst-case performance than
quicksort. The drawback of merge sort is that it normally requires
extra memory, whereas quicksort does not.
Click to expand...

When applied to arrays/vectors, that's true. For a linked list, they
both require essentially the same extra memory.
 
J

Juha Nieminen

Ioannis said:
list::sort is faster than any sort on vector, because it does not
involve the construction or destruction of any object.
Click to expand...

This is true even if the elements being sorted are ints?

What do you think is faster, copying and assigning individual ints, or
updating pairs of pointers at each stage of the sorting?
 
J

Juha Nieminen

Jerry said:
You can't (efficiently) use a median-of-three (or whatever) pivot selection
Click to expand...

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

STL Container? 4
Building a Large Container 26
A Better Container Choice? 3
Selecting Container for "Top 20" Application 25
Deriving from a STL container 22
STL container and stack frame size 5
Observing a container 2
STL Container class that holds no more than one object? 6

Members online

No members online now.
Total: 48 (members: 0, guests: 48)
Robots: 206

Forum statistics

Threads
473,774
Messages
2,569,596
Members
45,142
Latest member
arinsharma

Latest Threads

Top