By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,247 Members | 1,223 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,247 IT Pros & Developers. It's quick & easy.

STL container question

P: n/a
Hi

I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.

Thanks for any help

B2003
Oct 1 '08 #1
Share this Question
Share on Google+
80 Replies


P: n/a
Boltar wrote:
I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.
Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'. If you expect both searching and updating
the container, 'std::set' is probably better, its insertions are quite
fast. What book on the Standard Library are you reading that does not
have comparison of different standard containers in terms of performance?

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 1 '08 #2

P: n/a
Boltar schrieb:
Hi

I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.

Thanks for any help

B2003
std::set

Lars
Oct 1 '08 #3

P: n/a
Boltar wrote:
I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.
Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).
Oct 1 '08 #4

P: n/a
Victor Bazarov wrote:
>
Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'.

For that case, I think std::list is a better option, since the sorting
will be faster,
Oct 1 '08 #5

P: n/a
Ioannis Vranos wrote:
Victor Bazarov wrote:
>>
Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'.


For that case, I think std::list is a better option, since the sorting
will be faster,
Do you have any proof of that?

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 1 '08 #6

P: n/a
Victor Bazarov wrote:
Ioannis Vranos wrote:
>Victor Bazarov wrote:
>>>
Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'.


For that case, I think std::list is a better option, since the sorting
will be faster,

Do you have any proof of that?

Lists are implemented using pointers to point to the previous and to the
next elements, so list::sort(), is more efficient by changing pointer
values, while sorting a vector involves copying objects.
Oct 1 '08 #7

P: n/a
Ioannis Vranos wrote:
Lists are implemented using pointers to point to the previous and to the
next elements, so list::sort(), is more efficient by changing pointer
values, while sorting a vector involves copying objects.
The original poster talked about storing integer values. I highly
doubt sorting a list of integers will be faster than sorting an array of
integers. In fact, I'm pretty sure of the contrary.
Oct 1 '08 #8

P: n/a
Boltar wrote:
I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.
If memory usage is not an issue, std::set is by far the easiest solution.

(OTOH if the amount of integers can be counted in the millions, then
it may be better to use a sorted vector or whatever.)
Oct 1 '08 #9

P: n/a
Ioannis Vranos wrote:
Victor Bazarov wrote:
>Ioannis Vranos wrote:
>>Victor Bazarov wrote:

Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'.
For that case, I think std::list is a better option, since the sorting
will be faster,

Do you have any proof of that?


Lists are implemented using pointers to point to the previous and to the
next elements, so list::sort(), is more efficient by changing pointer
values, while sorting a vector involves copying objects.
And you really think that doing two pointer exchanges is faster than one
integer exchange?
Oct 1 '08 #10

P: n/a
Jeff Schwab wrote:
Boltar wrote:
>I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.

Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).
However, it can still be slower, since it's more or less the worst thing you
can do to the cache.

Oct 1 '08 #11

P: n/a
On 2008-10-01 18:57, Rolf Magnus wrote:
Jeff Schwab wrote:
>Boltar wrote:
>>I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.

Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).

However, it can still be slower, since it's more or less the worst thing you
can do to the cache.
Still, you should only get one cache-miss when looking for a value, if
you use a set or vector you will probably get more.

--
Erik Wikström
Oct 1 '08 #12

P: n/a
On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<iv*****@no.spam.nospamfreemail.grsaid:
Victor Bazarov wrote:
>Ioannis Vranos wrote:
>>Victor Bazarov wrote:

Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'.
For that case, I think std::list is a better option, since the sorting
will be faster,

Do you have any proof of that?


Lists are implemented using pointers to point to the previous and to
the next elements, so list::sort(), is more efficient by changing
pointer values, while sorting a vector involves copying objects.
In other words, no. <gOne 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. The problem with both arguments is exactly what
Victor implied: they're handwaving. Proof requires much more detailed
analysis, or if you're making a decision for a particular platform,
measurement.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Oct 1 '08 #13

P: n/a
Jeff Schwab schrieb:
Boltar wrote:
>I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.

Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).
How do you get O(1) from a sorted vector<int>? A binary search costs
O(log N).

Lars
Oct 1 '08 #14

P: n/a
Lars Tetzlaff wrote:
Jeff Schwab schrieb:
>Boltar wrote:
>>I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.
Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).

How do you get O(1) from a sorted vector<int>? A binary search costs
O(log N).
Jeff meant one would get O(1) from looking up in the full array of bits.
Every integer would mean a shift to form the index and a mask to get
to the bit value, one shift, one pointer addition, one dereference, one
bitwise AND per lookup, O(1).

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 1 '08 #15

P: n/a
Victor Bazarov schrieb:
Lars Tetzlaff wrote:
>Jeff Schwab schrieb:
>>Boltar wrote:

I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.
Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).

How do you get O(1) from a sorted vector<int>? A binary search costs
O(log N).

Jeff meant one would get O(1) from looking up in the full array of bits.
Every integer would mean a shift to form the index and a mask to get to
the bit value, one shift, one pointer addition, one dereference, one
bitwise AND per lookup, O(1).

V
I see, something like vector<bool>. Ok, that would be fast.

Lars
Oct 1 '08 #16

P: n/a
Erik Wikström wrote:
On 2008-10-01 18:57, Rolf Magnus wrote:
>Jeff Schwab wrote:
>>Boltar wrote:

I need to store a number of integer values which I will then search on
later to see if they exist in my container. Can someone tell me which
container would be quickest for finding these values? I can't use a
plain C array (unless I make it 2^32 in size!) since I don't know the
max integer value.

Sorted vector. See Effective STL, Item 23.

For the record, you wouldn't 2^32 integers, just 2^32 bits = 500 MiB.
It's actually not that much RAM, depending on your target system, and
would let you check for integers with O(1) complexity (rather than O(log
N)).

However, it can still be slower, since it's more or less the worst thing
you can do to the cache.

Still, you should only get one cache-miss when looking for a value, if
you use a set or vector you will probably get more.
If you only do a single look-up, yes. But in that case, building up an array
of 500 Megabytes will take a quite significant amount of time. ;-)
Oct 1 '08 #17

P: n/a
On Oct 1, 3:40 pm, Jeff Schwab <j...@schwabcenter.comwrote:
Boltar wrote:
I need to store a number of integer values which I will then
search on later to see if they exist in my container. Can
someone tell me which container would be quickest for
finding these values? I can't use a plain C array (unless I
make it 2^32 in size!) since I don't know the max integer
value.
Sorted vector. See Effective STL, Item 23.
For the record, you wouldn't 2^32 integers, just 2^32 bits =
500 MiB. It's actually not that much RAM, depending on your
target system, and would let you check for integers with O(1)
complexity (rather than O(log N)).
Some systems won't allow you to allocate that much as a local
variable, so you might as well use std::vector. If the
reallocations are an issue, one call up front to capacity should
solve that.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34
Oct 1 '08 #18

P: n/a
On Oct 1, 7:31 pm, Erik Wikstrm <Erik-wikst...@telia.comwrote:
On 2008-10-01 18:57, Rolf Magnus wrote:
Jeff Schwab wrote:
Boltar wrote:
I need to store a number of integer values which I will
then search on later to see if they exist in my container.
Can someone tell me which container would be quickest for
finding these values? I can't use a plain C array (unless
I make it 2^32 in size!) since I don't know the max
integer value.
Sorted vector. See Effective STL, Item 23.
For the record, you wouldn't 2^32 integers, just 2^32 bits
= 500 MiB. It's actually not that much RAM, depending on
your target system, and would let you check for integers
with O(1) complexity (rather than O(log N)).
However, it can still be slower, since it's more or less the
worst thing you can do to the cache.
Still, you should only get one cache-miss when looking for a
value, if you use a set or vector you will probably get more.
One thing I don't understand here: both a C style array and
std::vector use a single block of contiguous memory. How could
cache performance be any different for them?

(An earlier suggestion to use std::list does suffer from this,
of course.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34
Oct 1 '08 #19

P: n/a
On Oct 1, 7:40 pm, Pete Becker <p...@versatilecoding.comwrote:
On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<ivra...@no.spam.nospamfreemail.grsaid:
Victor Bazarov wrote:
Ioannis Vranos wrote:
Victor Bazarov wrote:
>>Store first, then sort, then search (using
'std::binary_search'), you could just use 'std::vector'.
>For that case, I think std::list is a better option, since
the sorting will be faster,
Do you have any proof of that?
Lists are implemented using pointers to point to the
previous and to the next elements, so list::sort(), is more
efficient by changing pointer values, while sorting a vector
involves copying objects.
In other words, no. <gOne 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. The problem
with both arguments is exactly what Victor implied: they're
handwaving. Proof requires much more detailed analysis, or if
you're making a decision for a particular platform,
measurement.
To other considerations: you can't use binary_search on
std::list---with any sort of size, that's going to make a
significant difference in favor of vector. And of course, an
std::list has horrible locality, which will translate into a lot
of cache misses (or even virtual page faults). So even if
sorting it were faster (which I somehow doubt)...

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34
Oct 1 '08 #20

P: n/a
James Kanze wrote:
On Oct 1, 7:31 pm, Erik Wikström <Erik-wikst...@telia.comwrote:
>On 2008-10-01 18:57, Rolf Magnus wrote:
Jeff Schwab wrote:
Boltar wrote:
I need to store a number of integer values which I will
then search on later to see if they exist in my container.
Can someone tell me which container would be quickest for
finding these values? I can't use a plain C array (unless
I make it 2^32 in size!) since I don't know the max
integer value.
>Sorted vector. See Effective STL, Item 23.
>For the record, you wouldn't 2^32 integers, just 2^32 bits
= 500 MiB. It's actually not that much RAM, depending on
your target system, and would let you check for integers
with O(1) complexity (rather than O(log N)).
However, it can still be slower, since it's more or less the
worst thing you can do to the cache.
>Still, you should only get one cache-miss when looking for a
value, if you use a set or vector you will probably get more.

One thing I don't understand here: both a C style array and
std::vector use a single block of contiguous memory. How could
cache performance be any different for them?
We're not talking about C style arrays vs. vector, but about different
algorithms. One is to storing the values in a sorted array/vector, then
doing a binary search for the value. The other is like a trivial kind of
hash table, where each possible integer value has a boolean entry, so you
can simply use the value as index. Saves the search, but needs a big amount
of memory that is much larger than the cache.
Oct 1 '08 #21

P: n/a
Rolf Magnus wrote:
James Kanze wrote:
>On Oct 1, 7:31 pm, Erik Wikström <Erik-wikst...@telia.comwrote:
>>On 2008-10-01 18:57, Rolf Magnus wrote:
Jeff Schwab wrote:
Boltar wrote:
>I need to store a number of integer values which I will
>then search on later to see if they exist in my container.
>Can someone tell me which container would be quickest for
>finding these values? I can't use a plain C array (unless
>I make it 2^32 in size!) since I don't know the max
>integer value.
Sorted vector. See Effective STL, Item 23.
For the record, you wouldn't 2^32 integers, just 2^32 bits
= 500 MiB. It's actually not that much RAM, depending on
your target system, and would let you check for integers
with O(1) complexity (rather than O(log N)).
However, it can still be slower, since it's more or less the
worst thing you can do to the cache.
Still, you should only get one cache-miss when looking for a
value, if you use a set or vector you will probably get more.
One thing I don't understand here: both a C style array and
std::vector use a single block of contiguous memory. How could
cache performance be any different for them?

We're not talking about C style arrays vs. vector, but about different
algorithms. One is to storing the values in a sorted array/vector, then
doing a binary search for the value. The other is like a trivial kind of
hash table, where each possible integer value has a boolean entry, so you
can simply use the value as index. Saves the search, but needs a big amount
of memory that is much larger than the cache.
Right, but the whole thing doesn't have to be in cache, just the parts
that are used. The rest may as well be swapped out of memory
altogether. Of course, that's the point of cache. :)
Oct 2 '08 #22

P: n/a
Juha Nieminen wrote:
Ioannis Vranos wrote:
>Lists are implemented using pointers to point to the previous and to the
next elements, so list::sort(), is more efficient by changing pointer
values, while sorting a vector involves copying objects.

The original poster talked about storing integer values. I highly
doubt sorting a list of integers will be faster than sorting an array of
integers. In fact, I'm pretty sure of the contrary.

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.
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.
Oct 2 '08 #23

P: n/a
Pete Becker wrote:
>
In other words, no. <gOne 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.

list::sort is faster than any sort on vector, because it does not
involve the construction or destruction of any object.
Oct 2 '08 #24

P: n/a
James Kanze wrote:
To other considerations: you can't use binary_search on
std::list---with any sort of size, that's going to make a
significant difference in favor of vector.

Of course you can:
#include <algorithm>
#include <list>
#include <cstddef>
#include <iostream>
int main()
{
using namespace std;

typedef list<intintlist;

intlist ilist;
for (size_t i= 0; i< 100; ++i)
ilist.push_back(100-i);
ilist.sort();
for(intlist::const_iterator p= ilist.begin(); p!= ilist.end(); ++p)
cout<< *p<< endl;
binary_search(ilist.begin(), ilist.end(), 50);
}
Oct 2 '08 #25

P: n/a
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

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

const unsigned int kLimit = 1000000;

template< class Cont >
void fill(Cont& cont)
{
for( unsigned int u = 0; u < kLimit; ++u ) {
cont.push_back(u);
}
}

template< class Cont >
void test(Cont& cont);

int main()
{
std::vector<unsigned intv; v.reserve(kLimit);
std::list<unsigned intl;

std::cout << "filling a vector..." << std::endl;
fill(v);
std::cout << "filling a list..." << std::endl;
fill(l);
std::cout << "...done.\n";

std::cout << "sorting a vector..." << std::endl;
test(v);
std::cout << "sorting a list..." << std::endl;
test(l);

return 0;
}

template< typename T, class Al >
inline void sort(std::vector<T,Al>& v) {std::sort(v.begin(),v.end());}

template< typename T, class Al >
inline void sort(std::list<T,Al>& l) {l.sort();}

#include <windows.h//for GetTickCount()

template< class Cont >
void test(Cont& cont) {
const DWORD start = GetTickCount();
sort(cont);
std::cout << "...took " << GetTickCount()-start << "msecs." << std::endl;
}

outputs
filling a vector...
filling a list...
...done.
sorting a vector...
...took 47msecs.
sorting a list...
...took 1562msecs.
and thus agrees with everyone who disagreed with you.
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.
Right. It wouldn't do any good anyway as this

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>

const unsigned int kLimit = 1000000;

template< class Cont >
void fill(Cont& cont)
{
for( unsigned int u = 0; u < kLimit; ++u ) {
cont.push_back(Test());
}
}

template< class Cont >
void test(Cont& cont);

class Test {
public:
Test() : instance_(++id_), str_("test it!") {}
bool operator<(const Test& rhs) {return instance_>rhs.instance_;}
private:
unsigned int instance_;
static unsigned int id_;
std::string str_;
};

unsigned int Test::id_ = 0;

int main()
{
std::vector<Testv; v.reserve(kLimit);
std::list<Testl;

std::cout << "filling a vector..." << std::endl;
fill(v);
std::cout << "filling a list..." << std::endl;
fill(l);
std::cout << "...done.\n";

std::cout << "sorting a vector..." << std::endl;
test(v);
std::cout << "sorting a list..." << std::endl;
test(l);

return 0;
}

template< typename T, class Al >
inline void sort(std::vector<T,Al>& v) {std::sort(v.begin(),v.end());}

template< typename T, class Al >
inline void sort(std::list<T,Al>& l) {l.sort();}

#include <windows.h//for GetTickCount()

template< class Cont >
void test(Cont& cont) {
const DWORD start = GetTickCount();
sort(cont);
std::cout << "...took " << GetTickCount()-start << "msecs." << std::endl;
}

outputs

filling a vector...
filling a list...
...done.
sorting a vector...
...took 829msecs.
sorting a list...
...took 2437msecs.

and thus again disagrees with you.

Eagerly awaiting your counter example,

Scho-you-can-take-your-foot-out-of-your-mouth-now-bi
Oct 2 '08 #26

P: n/a
On Oct 1, 6:40*pm, Pete Becker <p...@versatilecoding.comwrote:
On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<ivra...@no.spam.nospamfreemail.grsaid:
Victor Bazarov wrote:
Ioannis Vranos wrote:
Victor Bazarov wrote:
>>Store first, then sort, then search (using 'std::binary_search'), you
could just use 'std::vector'.
>For that case, I think std::list is a better option, since the sorting
will be faster,
Do you have any proof of that?
Lists are implemented using pointers to point to the previous and to
the next elements, so list::sort(), is more efficient by changing
pointer values, while sorting a vector involves copying objects.

In other words, no. <gOne 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.
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>

--
Max
Oct 2 '08 #27

P: n/a
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<intTypeVector;

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<SomeClassVector;
typedef list<SomeClassList;
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[i]);

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[i]= rand();

sort(vec.begin(), vec.end());
}
Oct 2 '08 #28

P: n/a
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<intTypeVector;

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<SomeClassVector;
typedef list<SomeClassList;
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[i]);

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[i]= rand();

sort(vec.begin(), vec.end());
}
Oct 2 '08 #29

P: n/a
Ioannis Vranos wrote:
[...]
==The timings less than 1 second are not conclusive. Add 0s until you
exceed 1-2 seconds.
If I add a single one more, the program runsout of memory.

Schobi
Oct 2 '08 #30

P: n/a
Ioannis Vranos wrote:
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

Schobi
Oct 2 '08 #31

P: n/a
Ioannis Vranos wrote:
The program had a serious bug.
corrected:

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <cstddef>
#include <algorithm>
class SomeClass
{
typedef std::vector<intTypeVector;

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<SomeClassVector;
typedef list<SomeClassList;
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[i]);

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[i]= rand();

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


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$
Oct 2 '08 #32

P: n/a
Hendrik Schober wrote:
Ioannis Vranos wrote:
>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.
For example try

const size_t SIZE= 400000;
Oct 2 '08 #33

P: n/a
Victor Bazarov wrote:
>
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.


The specific code had a serious bug (list had double elements than
vector). Also differences in milliseconds have no point (are inconclusive).
Oct 2 '08 #34

P: n/a
Ioannis Vranos wrote:
>
>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

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$


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.
Oct 2 '08 #35

P: n/a
Ioannis Vranos wrote:
Hendrik Schober wrote:
>Ioannis Vranos wrote:
>>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.
For example try

const size_t SIZE= 400000;
-------------- a debug build:

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.203 seconds

The sorting of the list took 4.602 seconds

-------------- a release build:

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.016 seconds

The sorting of the list took 0.062 seconds

-------------- another release build:

Creating vector with 300000 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.125 seconds

---------------------------------------------------------

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.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 2 '08 #36

P: n/a
Victor Bazarov wrote:
What is it you're trying to prove? That your computer and your
implementation are dilapidated? Get a better compiler.

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.
Oct 2 '08 #37

P: n/a
Victor Bazarov wrote:
>
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.

Do you agree that sorting a list does not involve object creation, while
sorting a vector involves the copying of the object elements?
Oct 2 '08 #38

P: n/a
Ioannis Vranos wrote:
Victor Bazarov wrote:
>>
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.


Do you agree that sorting a list does not involve object creation
or assignment,
while
sorting a vector involves the copying of the object elements?
Oct 2 '08 #39

P: n/a
Ioannis Vranos wrote:
Ioannis Vranos wrote:
>>
>>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

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

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

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 2 '08 #40

P: n/a
Ioannis Vranos wrote:
Ioannis Vranos wrote:
>Victor Bazarov wrote:
>>>
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.


Do you agree that sorting a list does not involve object creation

or assignment,
>while sorting a vector involves the copying of the object elements?
Whatever it involves (and I'd think it would actually be *swapping* and
not assignment or copying), 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...

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 2 '08 #41

P: n/a
"Victor Bazarov" <v.********@comAcast.netwrote in message
news:gc**********@news.datemas.de...
Ioannis Vranos wrote:
>Ioannis Vranos wrote:
>>Victor Bazarov wrote:

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.
Do you agree that sorting a list does not involve object creation

or assignment,
>>while sorting a vector involves the copying of the object elements?

Whatever it involves (and I'd think it would actually be *swapping* and
not assignment or copying),

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...
;^)
Oct 2 '08 #42

P: n/a
In message <gc**********@ulysses.noc.ntua.gr>, Ioannis Vranos
<iv*****@no.spam.nospamfreemail.grwrites
>Juha Nieminen wrote:
>Ioannis Vranos wrote:
>>Lists are implemented using pointers to point to the previous and to the
next elements, so list::sort(), is more efficient by changing pointer
values, while sorting a vector involves copying objects.
The original poster talked about storing integer values. I highly
doubt sorting a list of integers will be faster than sorting an array of
integers. In fact, I'm pretty sure of the contrary.


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.
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.
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.
What would he have to change with a vector?

--
Richard Herring
Oct 2 '08 #43

P: n/a
Ioannis Vranos schrieb:
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<intTypeVector;

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<SomeClassVector;
typedef list<SomeClassList;
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[i]);

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[i]= rand();

sort(vec.begin(), vec.end());
}
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[i]= SomeClass();
lis.push_back(vec[i]);
}
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
Oct 2 '08 #44

P: n/a
In article <aeb09adf-92fc-45ce-aa7f-
80**********@l62g2000hse.googlegroups.com>, ma***************@gmail.com
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.
Instead, lists are normally sorted using merge sort.
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.
When applied to arrays/vectors, that's true. For a linked list, they
both require essentially the same extra memory.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Oct 2 '08 #45

P: n/a
Ioannis Vranos wrote:
list::sort is faster than any sort on vector, because it does not
involve the construction or destruction of any object.
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?
Oct 2 '08 #46

P: n/a
Jerry Coffin wrote:
You can't (efficiently) use a median-of-three (or whatever) pivot selection
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.
Oct 2 '08 #47

P: n/a
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.
Oct 2 '08 #48

P: n/a
Lars Tetzlaff wrote:
Ioannis Vranos schrieb:
>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<intTypeVector;

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<SomeClassVector;
typedef list<SomeClassList;
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[i]);

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[i]= 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[i]= SomeClass();
lis.push_back(vec[i]);
}

Why?
Oct 2 '08 #49

P: n/a
Ioannis Vranos schrieb:
Lars Tetzlaff wrote:
>Ioannis Vranos schrieb:
>>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<intTypeVector;

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<SomeClassVector;
typedef list<SomeClassList;
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[i]);

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[i]= 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[i]= SomeClass();
lis.push_back(vec[i]);
}


Why?
To get distinct elements. See above.
Lars
Oct 2 '08 #50

80 Replies

This discussion thread is closed

Replies have been disabled for this discussion.