STL container question

[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!

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

You have to make a copy during the exchange of two elements:

SomeClass tmp = vec; // new value here
vec = vec[j];
vec[j] = tmp;

Lars

 

[Ioannis Vranos]

Ioannis Vranos schrieb:

You have to make a copy during the exchange of two elements:

SomeClass tmp = vec; // new value here
vec = vec[j];
vec[j] = tmp;

You are right, I will post a corrected version.


Thanks.

 

[Ioannis Vranos]

Third correction:


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


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

TypeVector vec;

enum { VectorSize= 1000 };

public:

void fillWithSortedRandomNumbers();

bool operator<(const SomeClass &) const;

SomeClass();
};



SomeClass::SomeClass():vec(VectorSize){}


inline void SomeClass::fillWithSortedRandomNumbers()
{
using namespace std;

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

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

inline bool SomeClass:perator<(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);

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

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";
}

 

[Rolf Magnus]

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

I didn't call them toy products, either.

No, you just claimed they were not "a real OS and a real compiler".

 

[Branimir Maksimovic]

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

You don;t need to know maximum value but aproximatelly
maximum number of integers that would be there.
If you are good guesser this hash class will suit your
needs. It has O(1) lookup and if there are more
numbers than table entries will do linear search,
but that shouldn't happen as much.

class HashT{
public:
HashT(unsigned max = 100):table_(max){}
bool find(unsigned num)const
{
unsigned index = num%table_.size();
if(table_[index].size()>0)
{
vector<int>::const_iterator
i = std::find(table_[index].begin(),table_[index].end(),num);
return i!=table_[index].end();
}
return false;
}
void insert(unsigned num)
{
unsigned index = num%table_.size();
if(table_[index].empty())
table_[index].push_back(num);
else
{
vector<int>::const_iterator
i = std::find(table_[index].begin(),table_[index].end(),num);
if(i == table_[index].end())
table_[index].push_back(num);
}
}
private:
vector<vector<int> > table_;
};

Greetings, Branimir.

 

[Jerry Coffin]

[ ... ]

A vector::swap() can be a shallow swap.

Not only can be, but basically _has_ to be. In particular, the _only_
situation in which vector::swap is allowed to throw is if the
container's allocator throws. This means that swap can't use _any_ of
the operators built into the type being contained. That leaves a shallow
swap as essentially the only option.

 

[aku ankka]

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?

The memory isn't contiguous on most common contemporary systems; it is
heavily fragmented and just appears contiguous (paged).

 

[Juha Nieminen]

The memory isn't contiguous on most common contemporary systems; it is
heavily fragmented and just appears contiguous (paged).

AFAIK that's completely inconsequential from the point of view of the
cache. The size of a cache block is much smaller than the size of a
memory page (which is probably a multiple of it).

 

[Hendrik Schober]

Third correction:
[...]

So it took you three tries and code that's just about as
far from the original requirement as possible while still
dealing with lists and vectors to come up with an example
where a list is actually faster than a vector.
Do you realize that you just proofed everyone else's point.
(Start with a vector, and measure whether a list is faster,
for it might happen, although not in general.)

Schobi

 

[Chris M. Thomasson]

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.

It takes some effort to maximize the use of the cache. I don't think one
could even use a `std::vector' in a cache-friendly manner. Well, first of
all, the memory for the vector would simply need to start on a cache-line
boundary; how can this be ensured? I think it would be impossible. Well,
perhaps with a custom allocator... Therefore, if you want to create highly
cache-friendly arrays and algorihtms, well, you need to "roll your own". I
don't quite see how one could use a `std::vector' and know that all the
caveats, such as false-sharing and proper data-alignment, have been
addressed...

 

[Hendrik Schober]

[...]

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.

It takes some effort to maximize the use of the cache. I don't think one
could even use a `std::vector' in a cache-friendly manner. Well, first of
all, the memory for the vector would simply need to start on a cache-line
boundary; how can this be ensured? I think it would be impossible. Well,
perhaps with a custom allocator... Therefore, if you want to create highly
cache-friendly arrays and algorihtms, well, you need to "roll your own". I
don't quite see how one could use a `std::vector' and know that all the
caveats, such as false-sharing and proper data-alignment, have been
addressed...

Actually the knowledge that 'std::vector' is more cache-friendly
than 'std::list' was obtained empirical: First people discovered
the fact and then found out (or rather speculated, I suppose
nobody ever went and really researched it) that processor caching
is the reason.

Schobi