Fastest STL container?

This is a discussion on Fastest STL container? within the C++ Programming forums, part of the General Programming Boards category; Also, what libs does your code need? winmm.lib For an unknown number of elements, won't a vector have to resize ...

  1. #16
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Also, what libs does your code need?
    winmm.lib

    For an unknown number of elements, won't a vector have to resize itself often?
    It doubles the memory each time so it's not that bad (logarithmic, or something...).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.
    Attached Files Attached Files

  3. #18
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.

  4. #19
    Registered User
    Join Date
    Aug 2003
    Posts
    1,203
    Nope, this is my terrain rendering code. But I think I know what the problem is now, will see when I attempt to correct it.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to get the size of an STL container object?!!!
    By sam-j89 in forum C++ Programming
    Replies: 7
    Last Post: 05-12-2009, 02:56 PM
  2. stl container to store more than 1 type
    By sujeet1 in forum C++ Programming
    Replies: 7
    Last Post: 05-09-2007, 04:10 AM
  3. inherited classes and stl container
    By rahulsk1947 in forum C++ Programming
    Replies: 9
    Last Post: 05-05-2007, 02:27 PM
  4. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM
  5. include question
    By Wanted420 in forum C++ Programming
    Replies: 8
    Last Post: 10-17-2003, 03:49 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21