Re: STL container question
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 int> v; v.reserve(kLimit);
std::list<unsigned int> l;
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<Test> v; v.reserve(kLimit);
std::list<Test> l;
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