STL container question

[Boltar]

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

[Rolf Magnus]

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.

[Jeff Schwab]

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

[Ioannis Vranos]

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.

[Ioannis Vranos]

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.

[Ioannis Vranos]

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::co nst_iterator p= ilist.begin(); p!= ilist.end(); ++p)
cout<< *p<< endl;
binary_search(i list.begin(), ilist.end(), 50);
}

[Hendrik Schober]

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<uns igned intv; v.reserve(kLimi t);
std::list<unsig ned 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::vecto r<T,Al>& v) {std::sort(v.be gin(),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.i nstance_;}
private:
unsigned int instance_;
static unsigned int id_;
std::string str_;
};

unsigned int Test::id_ = 0;

int main()
{
std::vector<Tes tv; v.reserve(kLimi t);
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::vecto r<T,Al>& v) {std::sort(v.be gin(),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

[Maxim Yegorushkin]

On Oct 1, 6:40*pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<[e-mail] m.nospamfreemai l.grsaid:

Victor Bazarov wrote:

Ioannis Vranos wrote:
Victor Bazarov wrote:

>>Store first, then sort, then search (using 'std::binary_se arch'), 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

[Ioannis Vranos]

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 &argSomeClas s) const
{
return vec[0]< argSomeClass.ve c[0];
}
};

int main()
{
using namespace std;

srand(time(0));

const size_t SIZE=10000;

typedef vector<SomeClas sVector;
typedef list<SomeClassL ist;
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::siz e_type i= 0; i< vec.size(); ++i)
lis.push_back(v ec[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<dou ble>((timeEndVe ctor- timeBeginVector ))/
CLOCKS_PER_SEC
<< " seconds\n\n";

cout<< "The sorting of the list took "
<< static_cast<dou ble>((timeEndLi st- timeBeginList))/
CLOCKS_PER_SEC
<< " seconds\n\n";
}

SomeClass::Some Class():vec(Vec torSize)
{
using namespace std;

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

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

[Hendrik Schober]

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

[Hendrik Schober]

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