Thread: Fastest STL container?

  1. #1
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218

    Fastest STL container?

    Ok, which is the fastest STL container in regards to clearing, pushing stuff to the back of it and iterating from the beginning to the end? (I dont need random access to some part of it). If you want me to prioritize these criterias I would list them as
    1.iterating being the most important that it is fast
    2. pushing back stuff
    3. clearing
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Without random access I'd say std::list
    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.

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Ok, damn, and I hoped there was something faster
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Only if you use a pooled allocator, otherwise the many small allocations (and deallocations) will likely drag you down, compared to the few large allocation of a deque or vector.
    It mainly depends on this: if you can predict how many elements will be in the container from the start, then a vector with reserve() will almost always be faster. If you can't guess well, then list will outperform you, but probably only if you pool the allocations.
    Since you also want clearing, I suspect that you'll rebuild and clear the collection quite frequently. I recommend a list, but make sure you only once actually mention std::list and otherwise use a typedef, e.g.
    typedef std::list<my_data> data_list;
    This way you can later (if performance turns out to be a problem) easily switch to a different allocator and only need to change a single line of code (the typedef).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    If you know how many items will be added, or you have an upper bound that is reliable, I'd guess vector. If not, then it depends on how many elements you'll be adding, but I think it will be pretty close.

    I say guess because it depends on your implementation and the only way to know for sure is to test it (and even then it will be hard to tell unless you test it within your entire app).

    The reason vector may be faster despite the lack of a need for random access is that list allocates space for each node separately when you push_back. That's a lot of allocations and deallocations. Depending on your implementation, it could cause a greater slowdown than a vector reallocation.

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    constant time push_back/push_front/pop_back/pop_front, iteration only updates a pointer each step. How can that not be fast enough for you?
    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.

  7. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Ok, what I will mainly do is fill the container with alot of structs (unknown how many). This will be done quite frequently but more frequently I will iterate from the beginning to the end. That is why I need it to be as fast as possible during iterating.

    I have done some tests and it actually seems like a deque is faster than both vectors and lists but I will do some more testing in the actual application.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  8. #8
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    If you're willing to accept pushing back to be fast on average, with the occasional slow one, I'd say std::vector [edit: but I guess you've found a deque works too]. I don't think this is an STL container, but I'd prefer a linked list of vectors in the style of
    [n elements reserved] -> [2n elements reserved] -> [4n elements reserved] -> [8n elements reserved] -> ... expand and contract as needed. [Edit: come to think of it, this is probably similar to what a deque looks like [edit: maybe.]]

    Iterating should be faster for vectors than linked lists, because you need two memory accesses per node with a linked list, with the best possible implementation, but only one for a vector, plus you've got spatial locality, which won't hurt, but won't make much of a difference if you need to iterate over and over and over again. the datastructure described above gives you practically vector-speed iteration with O(1) pushing back.

    With datatypes that use destructors, clearing is O(n) with both vectors and linked lists, since you have to call every destructor. With a single vector of primitive datatypes or those which lack an explicit destructor, clearing would depend on the implementation of the STL and the compiler, but it could presumably be O(1), constant time. With that hybrid datatype, which you'd need to implement yourself, clearing would be O(log n) with a datatype that lacks an explicit destructor (presuming that O(1) is the time for a vector).

    Linked lists would take O(n) time to clear probably, but you could write your own linked list implementation that doesn't actually call delete on nodes, but instead keeps them in a separate list, waiting to be used for later pushes. Then clearing would be effectively O(1).
    Last edited by Rashakil Fol; 02-16-2006 at 01:54 PM.

  9. #9
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Well I think I am actually pushing the limits here now. I have not found any real difference betwean a list, vector or deque. What I think I really need is a normal C array to speed things up that little extra but since the number of elements in the array are unknown the overhead to expand it would probably be too much (but I will think about it, might have a good algorithm, since it doesnt really matter if I use all the memory or if the actual array is larger than what I need).

    Ill give it some thought.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  10. #10
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I did a test program timing some operations on std::list and std::vector. std::vector is way faster than std::list, not to mention I had to turn off optimization since std::vector got so optimized giving close to 0 ms in each of its tests (I fear the loops got totally optimized away). std::list may sound fast in theory (had me fooled) but std::vector does take home the gold medal.

    ...unless I made some serious mistake, I posted the source for the interested.

    The result (no optimization):
    List.push_back(), iterating 100000 times!
    Time: 179 ms

    List::iterator, iterating 1000 times!
    Time: 7669 ms

    List.pop_back(), iterating 100000 times!
    Time: 1375 ms

    Vector.push_back(), iterating 100000 times!
    Time: 10 ms

    Vector::iterator, iterating 1000 times!
    Time: 4886 ms

    Vector.pop_back(), iterating 100000 times!
    Time: 5 ms
    The result (optimization enabled):
    List.push_back(), iterating 100000 times!
    Time: 169 ms

    List::iterator, iterating 1000 times!
    Time: 2158 ms

    List.pop_back(), iterating 100000 times!
    Time: 1373 ms

    Vector.push_back(), iterating 100000 times!
    Time: 5 ms

    Vector::iterator, iterating 1000 times!
    Time: 0 ms

    Vector.pop_back(), iterating 100000 times!
    Time: 0 ms
    The source code:
    Code:
    #include <windows.h>
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <list>
    
    typedef void (*TaskPointer)(int);
    
    std::list<int> List;
    std::vector<int> Vector;
    std::ofstream File;
    
    void TaskListPushBack(int Times)
    {
    	while(Times > 0)
    	{
    		List.push_back(Times);
    		Times--;
    	}
    }
    
    void TaskListIterate(int Times)
    {
    	int Sum = 0;
    	std::list<int>::iterator i;
    
    	while(Times > 0)
    	{
    		i = List.begin();
    		while(i != List.end())
    		{
    			Sum += (*i);
    			i++;
    		}
    		Times--;
    	}
    }
    
    void TaskListPopBack(int Times)
    {
    	while(Times > 0)
    	{
    		List.pop_back();
    		Times--;
    	}
    }
    
    void TaskVectorPushBack(int Times)
    {
    	while(Times > 0)
    	{
    		Vector.push_back(Times);
    		Times--;
    	}
    }
    
    void TaskVectorIterate(int Times)
    {
    	int Sum = 0;
    	std::vector<int>::iterator i;
    
    	while(Times > 0)
    	{
    		i = Vector.begin();
    		while(i != Vector.end())
    		{
    			Sum += (*i);
    			i++;
    		}
    		Times--;
    	}
    }
    
    void TaskVectorPopBack(int Times)
    {
    	while(Times > 0)
    	{
    		Vector.pop_back();
    		Times--;
    	}
    }
    
    void TimeTask(const std::string& Title, TaskPointer Task, int Times)
    {
    	DWORD StartTime;
    	DWORD EndTime;
    
    	std::cout << "Attempting " << Title << "..." << std::endl;
    
    	File << Title << ", iterating " << Times << " times!" << std::endl;
    	StartTime = timeGetTime();
    
    	Task(Times);
    
    	EndTime = timeGetTime();
    	File << "Time: " << (EndTime - StartTime) << " ms" << std::endl << std::endl;
    
    	std::cout << Title << " done!" << std::endl << std::endl;
    }
    
    int main()
    {
    	int PushTimes = 100000;
    	int IterateTimes = 1000;
    
    	std::cout << "Warming up..." << std::endl << std::endl;
    
    	Sleep(2000);
    	timeBeginPeriod(1);
    	File.open("Result.txt");
    
    	TimeTask("List.push_back()", TaskListPushBack, PushTimes);
    	TimeTask("List::iterator", TaskListIterate, IterateTimes);
    	TimeTask("List.pop_back()", TaskListPopBack, PushTimes);
    	TimeTask("Vector.push_back()", TaskVectorPushBack, PushTimes);
    	TimeTask("Vector::iterator", TaskVectorIterate, IterateTimes);
    	TimeTask("Vector.pop_back()", TaskVectorPopBack, PushTimes);
    
    	File.close();
    	timeEndPeriod(1);
    
    	std::cout << "Done!" << std::endl;
    
    	return 0;
    }
    Last edited by Magos; 02-16-2006 at 02:07 PM.
    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.

  11. #11
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Ok, ive decided to go with a vector for now. I dont gain anything from either a list, deque or vector atm, no difference really. Same goes with C arrays, they proved to be as fast (or slow, which way you want it) as anything else.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I'd still use a typedef. Makes it easier to change later (until you begin to rely on container-specific features).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Yup, already taken your advice on that one
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  14. #14
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Based on my timing tests, it is doubtful that any one will be a huge improvement over another. However, I would use vector if there is a good value to call reserve with prior to filling the container. Otherwise I would use list with boost::fast_pool_allocator.

  15. #15
    Registered User
    Join Date
    Mar 2002
    Posts
    203
    @Magos: Try running your test using a struct or class and see how the results come out. Also, what libs does your code need? I'm getting linker errors when compiling it in VC++ 2005
    For an unknown number of elements, won't a vector have to resize itself often?

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