Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I like Matthieu's answer, but I'm going to restate the flowchart as this:</p> <h2>When to NOT use std::vector</h2> <p>By default, if you need a container of stuff, use <code>std::vector</code>. Thus, every other container is only justified by providing some functionality alternative to <code>std::vector</code>.</p> <h3>Constructors</h3> <p><code>std::vector</code> requires that its contents are move-constructible, since it needs to be able to shuffle the items around. This is not a terrible burden to place on the contents (note that default constructors are <em>not required</em>, thanks to <code>emplace</code> and so forth). However, most of the other containers don't require any particular constructor (again, thanks to <code>emplace</code>). So if you have an object where you absolutely <em>cannot</em> implement a move constructor, then you will have to pick something else.</p> <p>A <code>std::deque</code> would be the general replacement, having many of the properties of <code>std::vector</code>, but you can only insert at either ends of the deque. Inserts in the middle require moving. A <code>std::list</code> places no requirement on its contents.</p> <h3>Needs Bools</h3> <p><code>std::vector&lt;bool&gt;</code> is... not. Well, it is standard. But it's not a <code>vector</code> in the usual sense, as operations that <code>std::vector</code> normally allows are forbidden. And it most certainly <em>does not contain <code>bool</code>s</em>.</p> <p>Therefore, if you need real <code>vector</code> behavior from a container of <code>bool</code>s, you're not going to get it from <code>std::vector&lt;bool&gt;</code>. So you'll have to make due with a <code>std::deque&lt;bool&gt;</code>.</p> <h3>Searching</h3> <p>If you need to find elements in a container, and the search tag can't just be an index, then you may need to abandon <code>std::vector</code> in favor of <code>set</code> and <code>map</code>. Note the key word "<em>may</em>"; a sorted <code>std::vector</code> is sometimes a reasonable alternative. Or Boost.Container's <a href="http://www.boost.org/doc/libs/1_49_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx" rel="noreferrer"><code>flat_set/map</code></a>, which implements a sorted <code>std::vector</code>.</p> <p>There are now four variations of these, each with their own needs.</p> <ul> <li>Use a <code>map</code> when the search tag is not the same thing as the item you're looking for itself. Otherwise use a <code>set</code>.</li> <li>Use <code>unordered</code> when you have a <em>lot</em> of items in the container and search performance absolutely needs to be <code>O(1)</code>, rather than <code>O(logn)</code>.</li> <li>Use <code>multi</code> if you need multiple items to have the same search tag.</li> </ul> <h3>Ordering</h3> <p>If you need a container of items to always be sorted based on a particular comparison operation, you can use a <code>set</code>. Or a <code>multi_set</code> if you need multiple items to have the same value.</p> <p>Or you can use a sorted <code>std::vector</code>, but you'll have to keep it sorted.</p> <h3>Stability</h3> <p>When iterators and references are invalidated is sometimes a concern. If you need a list of items, such that you have iterators/pointers to those items in various other places, then <code>std::vector</code>'s approach to invalidation may not be appropriate. Any insertion operation may cause invalidation, depending on the current size and capacity.</p> <p><code>std::list</code> offers a firm guarantee: an iterator and its associated references/pointers are only invalidated when the item itself is removed from the container. <code>std::forward_list</code> is there if memory is a serious concern.</p> <p>If that's too strong a guarantee, <code>std::deque</code> offers a weaker but useful guarantee. Invalidation results from insertions in the middle, but insertions at the head or tail causes only invalidation of <em>iterators</em>, not pointers/references to items in the container.</p> <h3>Insertion Performance</h3> <p><code>std::vector</code> only provides cheap insertion at the end (and even then, it becomes expensive if you blow capacity).</p> <p><code>std::list</code> is expensive in terms of performance (each newly inserted item costs a memory allocation), but it is <em>consistent</em>. It also offers the occasionally indispensable ability to shuffle items around for virtually no performance cost, as well as to trade items with other <code>std::list</code> containers of the same type at no loss of performance. If you need to shuffle things around <em>a lot</em>, use <code>std::list</code>.</p> <p><code>std::deque</code> provides constant-time insertion/removal at the head and tail, but insertion in the middle can be fairly expensive. So if you need to add/remove things from the front as well as the back, <code>std::deque</code> might be what you need.</p> <p>It should be noted that, thanks to move semantics, <code>std::vector</code> insertion performance may not be as bad as it used to be. Some implementations implemented a form of move semantic-based item copying (the so-called "swaptimization"), but now that moving is part of the language, it's mandated by the standard.</p> <h3>No Dynamic Allocations</h3> <p><code>std::array</code> is a fine container if you want the fewest possible dynamic allocations. It's just a wrapper around a C-array; this means that its size must be known at <em>compile-time</em>. If you can live with that, then use <code>std::array</code>.</p> <p>That being said, using <code>std::vector</code> and <code>reserve</code>ing a size would work just as well for a bounded <code>std::vector</code>. This way, the actual size can vary, and you only get one memory allocation (unless you blow the capacity).</p>
    singulars
    1. This table or related slice is empty.
    1. POHow can I efficiently select a Standard Library container in C++11?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNicol Bolas
    1. USNicol Bolas
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWell, I like your answer a lot too :) WRT keeping a vector sorted, apart from `std::sort`, there is also `std::inplace_merge` which is interesting to easily place new elements (rather than a `std::lower_bound` + `std::vector::insert` call). Nice to learn about `flat_set` and `flat_map`!
      singulars
      1. PO
      1. USMatthieu M.
    2. COYou also cannot use a vector with 16-byte aligned types. Also also a good replacement for `vector<bool>` is `vector<char>`.
      singulars
      1. PO
      1. USInverse
    3. CO@Inverse: "You also cannot use a vector with 16-byte aligned types." Says who? If `std::allocator<T>` doesn't support that alignment (and I don't know why it wouldn't), then you can always use your own custom allocator.
      singulars
      1. PO
      1. USNicol Bolas
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload