53

Possible Duplicate:
Why would I prefer using vector to deque

I am curious why is it that std::vector is so much more popular than std::deque. Deque is almost as efficient in lookup, more efficient in insert (without vector::reserve)and allows for inserting/deleting in the front.

Herb Sutter once recommended that if you want to use vector, just prefer deque (I am paraphrasing). However in a recent talk on Writing Modern C++ he again strongly recommends thinking of std::vector as a default container. According to the GOTW I linked earlier, even the standard has similar wording.

Is there a reason for this disparity? Is it just that vector is simpler and more well known, or is there a technical reason? Or is it that vector is just a cooler name .. ?

Community
  • 1
  • 1
Karthik T
  • 31,456
  • 5
  • 68
  • 87
  • 1
    Just my opinion, but generally I don't think we use the front end as much as the back. – chris Dec 07 '12 at 07:10
  • 18
    IIRC both Scott Meyers and Bjarne recommend vector as "the default container". Also, afaik, it's the only standard container who's underlying memory model is compatible with C APIs (so I guess that's a plus over deque?) – Borgleader Dec 07 '12 at 07:10
  • More memory efficient, perhaps? Sounds like a linked list would eat a lot of memory. Is `deque` a linked list? – John Dvorak Dec 07 '12 at 07:13
  • @chris It is a very rare use I agree – Karthik T Dec 07 '12 at 07:14
  • @Borgleader very good point! – Karthik T Dec 07 '12 at 07:17
  • @JanDvorak - You can think of it as a linked list of vectors (very roughly speaking). Vector stores all elements in 1 block and has to reallocate if your inserts overflow this block. In deque, its stored in several blocks, so if a block overflows, a new block is allocated. – Karthik T Dec 07 '12 at 07:19
  • @KarthikT then `deque` seems like a great data structure. – John Dvorak Dec 07 '12 at 07:21
  • 1
    @JanDvorak: No, [follow the white rabbit](http://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl). – Matthieu M. Dec 07 '12 at 07:21
  • @MatthieuM. yes this appears to be an exact duplicate, stack overflow needs a better "similar questions" search, I will vote to close this question, thanks for all your views guys! – Karthik T Dec 07 '12 at 07:24
  • @JanDvorak: A `deque` is an "unrolled" linked list. That is, instead of each node holding one element, each node holds some large, but finite number of elements. – Billy ONeal Dec 07 '12 at 07:27
  • @MatthieuM. Do you know if the Java Deque is implemented similarly? – John Dvorak Dec 07 '12 at 07:29
  • Even http://stackoverflow.com/questions/139824/vector-or-deque is similar – Karthik T Dec 07 '12 at 07:32
  • @BillyONeal: Not quite. The O(1) access could not be achieved with an unrolled linked list. – Matthieu M. Dec 07 '12 at 08:40
  • 1
    @JanDvorak: No idea, I don't care much about Java ;) – Matthieu M. Dec 07 '12 at 08:40
  • 1
    Also `vector` easily fits into CPU cache and arithmetic operations on vector's elements can easily be vectorized. Doing this with `deque` is not that easy if it all possible –  Dec 07 '12 at 09:18
  • To be honest, until now I didn't know that a deque offers random access! I always thought it was just a queue you could push and pop from both ends. – jdm Dec 07 '12 at 11:23
  • @Matthieu: I don't believe `deque` requires `O(1)` access. But I can't seem to find anything in the standard to conform or deny that. – Billy ONeal Dec 07 '12 at 20:28
  • @BillyONeal: They do, otherwise they would not have a `operator[]` and `at()` methods which are trademarks of Random Access Containers. *§23.3.3.1/1 A deque is a sequence container that, like a vector (23.3.6), supports random access iterators.* – Matthieu M. Dec 07 '12 at 20:44
  • @Matthieu: I can't find anything that requires random access iterators to be `O(1)`; only that they be "efficient". Even an unrolled linked list the size of available memory is going to be really fast. – Billy ONeal Dec 07 '12 at 20:46
  • @BillyONeal: It may be a term of the art (I do not find its definition either). Indirectly, in §25.4.3 Binary Search we get *They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure.* which is only feasible if `it + n` is O(1). – Matthieu M. Dec 08 '12 at 13:39

5 Answers5

58

I can't speak for anybody else, but I can for myself.

When I first read about std::deque, I thought it was cool enough that for a while, I treated it not only as the default container, but as nearly the only container I used.

Then somebody asked about why, and I expounded at length on its virtues and why it was the best container to use for practically everything, and how it was much more versatile than std::vector.

Fortunately, the guy questioning my decision on it was persuasive enough that I did some testing. Testing showed that in nearly every case, std::deque was slower than std::vector -- often by a substantial factor (e.g., around 2). In fact, of the code I'd written using std::deque, just replacing std::deque with std::vector gave a speedup in all but a handful of cases.

I have used std::deque in a few cases since then, but definitely don't treat it as the default any more. The simple fact is that in the usual implementation it's noticeably slower than std::vector for most purposes.

I should add, however, that I'm reasonably certain that with the right implementation, it could be nearly equivalent to std::vector in virtually all cases. Most use a representation that's undoubtedly great from an asymptotic viewpoint, but doesn't work out quite so wonderfully (for many purposes) in the real world.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
14

std::vector is very well understood, simple and is compatible with C (both in terms of the memory layout, and in terms of using pointers as iterators).

For some operations it is also more efficient than std::deque. Accessing elements by index is one example.

For a given task, it makes sense to use the simplest container that does the job well. In many cases that simplest container is std::vector.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
5

Apart from std::vector being the most commonly known container class, it also has several advantages over std::deque, namely:

  • A typical std::deque requires an additional indirection to access the elments unlike as in case of std::vector.
  • Iterators in case of std::deque must be smart pointers and not pointers as in case of std::vector.
  • Elements of an std::vector are guaranteed to be contiguous and hence it is compatible with c-style functions which take arrays as parameters.
  • std::deque provide no support to control the capacity and the moment of reallocation.

Especially, the last point is noteworthy.

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
Alok Save
  • 202,538
  • 53
  • 430
  • 533
  • 2
    `Iterators in case of std::deque must be smart pointers and not pointers as in case of std::vector.` <-- Erm, this doesn't make any sense. Iterators aren't smart pointers. – Billy ONeal Dec 07 '12 at 07:25
  • 1
    @BillyONeal: In a semantic senses, the iterator for `std::vector` does not need to be smart since elements are guaranteed to be contiguous. While in case of `std::deque` the iterator implementation has to be smart enough to jump to the next block and detect the next element. Ofcourse, standard does not say anything about implementation of the iterator class, but that is how things would usually be. – Alok Save Dec 07 '12 at 07:28
  • Possible -- but I don't see why that affects *users* of the library. A conformant C++ implementation has to provide both `vector` and `deque` to the user -- implementation complexities are up to the implementation. I don't think users care about such things. (It should also be noted that at least one popular compiler (MSVC++) always uses real objects for iterator types anyway, not pointers) – Billy ONeal Dec 07 '12 at 07:32
5

People use std::vector over std::deque for a simple reason. They interface with a lot of C libraries and they have functions with parameters which require a pointer to contiguous storage, which std::deque doesn't (can't) guarantee.

Another reason is when you build code according to std::deque and your requirements change so that you have to support contiguous access, you will have a bit of refactoring to do.

I am compelled to mention that there are libraries out there whose authors claim to have created more efficient vector implementations in order to overcome inefficiencies when capacity is increased.

nurettin
  • 11,090
  • 5
  • 65
  • 85
5

The structure of std::deque is a bit more complex which makes naive iteration quite a bit more expensive than std::vector. The insertions into std::vector with its reallocations tend not to be big problem, especially when using reserve() and only appending to the end. Also, there are easier to understand invalidation rules for std::vector although it is actually an advantage of std::deque that objects stay put when inserting/removing only at either end (note that std::deque iterators get invalidate upon each insertion, independent of where the insertion happens). Another plus for std:vector is the guarantee that the values are contiguous in memory causing it to make fewer memory allocations.

I guess, I would recommend use of std::deque algorithms were consistently optimized to use segmented sequences (I'm not aware that any standard C++ library does this optimization) and users were accessing sequences consistently using algorithms (as far as I can tell, only a tiny fraction of users considers the option to use algorithms). Otherwise I would suspect that std::deque is the better option with respect to performance only if you take advantage of its specific properties (e.g., that objects stay put and that you can insert/remove at the end). It is worth profiling the two alternatives, though.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • +1 -- but I wouldn't say that vector has much advantage over deque for memory allocation count. Sure, deque might allocate a larger number; but usually the allocations made by deque are large enough compared to the size of the objects in question that it's almost a non-issue. – Billy ONeal Dec 07 '12 at 07:25
  • The number of allocations clearly don't matter for small instances. For large instances, `std::vector` makes `O(log(c.size()))` allocations while `std::deque` makes `O(c.size())` allocations. Of course, it may have a better chance to distribute its multiple blocks rather than the one big chunk... – Dietmar Kühl Dec 07 '12 at 07:27
  • Yes, but I don't think at the scales we are talking that asymptotic are useful here. Even one of these structures the size of physical memory are peanuts in comparison to actually filling any such structure with data and performing useful work with said data. (That is, I don't think `n` ever becomes large enough on real hardware) The fragmentation problem of having to support a single huge memory block seems like the bigger deal when `n` gets large, and that's an advantage to `deque`. – Billy ONeal Dec 07 '12 at 07:30