Thread: Fastest STL container?

Using VC++ 7.1 Release build with Optimize for Speed (/O2) I got these timing averages:

Code:

container	operation	ave        |
vector		push_back	1.480520619
list		push_back	1.32201125
deque		push_back	1.272559963
vector		iteration	0.127701127
list		iteration	0.144835494
deque		iteration	0.139547216
vector		clear		0.116542555
list		clear		0.857515519
deque		clear		1.160317

with this code:

Code:

#include <windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

class CPrecisionTimer
{
public:
    double Stop() {
        LARGE_INTEGER curval;
        QueryPerformanceCounter(&curval);
        long double f = ToDouble(m_start);
        long double f1 = ToDouble(curval);
        long double f3 = ToDouble(m_freq);
        return (f1 - f)/f3;
    }
    long double ToDouble(LARGE_INTEGER& val) {
        long double f = val.u.HighPart;
        f = f * (DWORD)-1;//4294967296;
        f += val.u.LowPart;
        return f;
    }
    void Start() {
        QueryPerformanceCounter(&m_start);
    }
    CPrecisionTimer() {
        QueryPerformanceFrequency(&m_freq);
    }
private:
    LARGE_INTEGER m_start;
    LARGE_INTEGER m_freq;
};

struct my_struct
{
    int a;
    double b;
    std::string c;
    char d;
};

#define USE_VECTOR 1
#define USE_LIST 0
#define USE_DEQUE 0

#if USE_VECTOR
#include <vector>
typedef std::vector<my_struct> structlist;
const std::string container_name("vector");
#elif USE_LIST
#include <list>
typedef std::list<my_struct> structlist;
const std::string container_name("list");
#elif USE_DEQUE
#include <deque>
typedef std::deque<my_struct> structlist;
const std::string container_name("deque");
#endif

void use_struct(my_struct& m)
{
    m.a = m.c.empty() ? 3 : 2;
    m.c = "clear,";
    m.b = 1.0;
}

void push_data(structlist& mylist, const unsigned int size, std::ostream& out)
{
    CPrecisionTimer ct;
    ct.Start();
    for (unsigned i = 0; i < size; ++i)
    {
        mylist.push_back(my_struct());
    }
    out << "push_back," << size << ",";
    out << ct.Stop() << std::endl;
}

void iterate(structlist& mylist, const unsigned int size, std::ostream& out)
{
    CPrecisionTimer ct;
    ct.Start();
    for (structlist::iterator beg = mylist.begin(),
        end = mylist.end(); beg != end; ++beg)
    {
        use_struct(*beg);
    }
    out << "iteration," << size << ",";
    out << ct.Stop() << std::endl;
}

void run_test(structlist& mylist, const unsigned int size, std::ostream& out)
{
    push_data(mylist, size, out);
    iterate(mylist, size, out);
    out << mylist.begin()->c;
    CPrecisionTimer ct;
    ct.Start();
    mylist.clear();
    out << size << ",";
    out << ct.Stop() << std::endl;
}

int main()
{
    const int first_size = 500000;
    const int second_size = 2000000;
    const int third_size = 100000;
    const int fourth_size = 10000000;

    std::ostringstream out;
    out << container_name << std::endl;
    out << "operation,size,time" << std::endl;

    {
        structlist mylist;
        run_test(mylist, first_size, out);
        run_test(mylist, second_size, out);
        run_test(mylist, third_size, out);
        run_test(mylist, fourth_size, out);
    }

    std::ofstream ofile("cntrtimes.csv", std::ios_base::app);
    ofile << out.str() << std::endl;
}

The raw data is attached as a txt file but is really a csv file.

I think a vector is fast enough for what you need Shakti. And BTW we do know how many items will be in the vector. What we don't know is how many items will be in each Object's message vector.

If that is what you are referring to.