- Forum
- General C++ Programming
- Which container to use?
Which container to use?
Vector, deque and basic_string all seem to be very much alike. So, what are the capabilities, differences, pros and cons about each of those? I always used vector, but I never realy gave the other ones a try, so, which is better?
vector and string are both arrays, meaning you can take the address of any element and do pointer arithmetics with it, or pass it to a C library function. Strings have all those extra string-oriented member functions, and also small strings are typically allocated on stack.
This also means that vectors and strings stress the memory manager: if your memory is fragmented, it may be harder to find a contiguous chunk, especially if you're growing it by push_back/operator+=
deque, on the other hand, is a sequence of small arrays, each the size of a VM page, typically. It's faster to allocate, but it's not a single array, so it's not compatible with C. It may also be slightly slower to access.
And of course, the obvious, deque has a fast push_front, but inserting at the first position of a vector means moving every single element. deque's push_back never moves any elements (and never invalidates pointers and references to them), while vector's push_back may have to move every single element when vector's capacity() grows.
This also means that vectors and strings stress the memory manager: if your memory is fragmented, it may be harder to find a contiguous chunk, especially if you're growing it by push_back/operator+=
deque, on the other hand, is a sequence of small arrays, each the size of a VM page, typically. It's faster to allocate, but it's not a single array, so it's not compatible with C. It may also be slightly slower to access.
And of course, the obvious, deque has a fast push_front, but inserting at the first position of a vector means moving every single element. deque's push_back never moves any elements (and never invalidates pointers and references to them), while vector's push_back may have to move every single element when vector's capacity() grows.
Last edited on
I ran some tests that show that vector and string take excatly the smae amount of time to allocate, while deque take a bit more, at memebr acessing string is the fastest, vector is right behind it, but deque is MUCH slower, while at swapping(copying) vector and string are basicly almost equal(the difference is less than 0.05 sec at 20000000 elements when doing reverse()), and deque is slower by a a half. So, basicy, I should use vector for integral types and basic_string for character types(to avoid big names). So what's deque good for?
And, suprisingly, vector<bool> is faster that deque<bool> and string<bool> only at allocating, in everythign else it's like normal! What happened to all those modifications?
deque is good for anything that grows (benchmark a loop that does push_back between deque and vector), and for anything that's very large.
Topic archived. No new replies allowed.