Which STL container to use?

[Robert Hutchings]

http://homepages.e3.net.nz/~djm/cppcontainers.html

Do you agree with the flowchart at bottom of page?

[Ian Collins]

Robert Hutchings wrote:
> http://homepages.e3.net.nz/~djm/cppcontainers.html
>
> Do you agree with the flowchart at bottom of page?

While it leads to a correct solution for simple applications, it might
not lead too an optimal solution. Too few paths lead to vector.

--
Ian Collins

[Christopher Pisz]

Aye. There was some discussion a while back about all things implemented
with list should be implemented using vector for the contiguous memory
to take advantage if cache hits. Still need to test this out myself more
extensively.

[Richard]

[Please do not mail me a copy of your followup]

Robert Hutchings <rm.hut...@gmail.com> spake the secret code
<m5ihe6$fmh$1...@dont-email.me> thusly:

>http://homepages.e3.net.nz/~djm/cppcontainers.html
>
>Do you agree with the flowchart at bottom of page?

Seems pretty complicated and obscures the most important advice:

Use vector as your first choice for container.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Öö Tiib]

On Monday, 1 December 2014 22:01:49 UTC+2, Robert Hutchings wrote:
> http://homepages.e3.net.nz/~djm/cppcontainers.html
>
> Do you agree with the flowchart at bottom of page?

Generally it is OK chart. Few remarks.

* When people are first unsure about the performance characteristics yet
then they should take 'std::vector' and if later there's time then revisit
that choice. Being unsure is quite standard state of software developer's
mind and lack of time is also quite usual situation later so most
containers in C++ program should be 'std::vector'. ;)

* The logic that leads to some rather common choices like 'std_pair',
'std::tuple', 'std::array' and 'std::unordered_*' is entirely missing
from the chart.

* Some logic should lead to 'std::bitset' (it performs usually way
better than 'std::array<bool,?>' or 'std::set<some_enum_type>' ).

* Any such guide should at least mention some very well-performing
containers of Boost (that often outperform the 'std') like 'boost::flat_*'
and 'boost::intrusive::*'.

[Chris Vine]

No. If a container is never accessed concurrently in more than one
thread, and its contained elements are built-in types, then use
std::vector unless in extraordinary circumstances.

If the contained elements have non-throwing
move-constructor/move-assignment-operator then also strongly consider
std::vector unless the internal implementation of the element is mainly
constructed on the heap, in which case you will be suffering cache
misses anyway and if you are frequently inserting/removing elements
other than at the end of the vector you might get better performance
with another container. But profile first.

Don't use ordered associative containers unless profiling shows they are
better (they almost always aren't even when you think they should be).
There is a reason why smalltalk is slow. Treat the unordered
associative containers with suspicion, but they do have good use cases.

Use std::list with splicing/unsplicing to minimize contention if a
queue-type or stack-type container may be accessed/modified
concurrently by more than one thread, to minimize contention on locks,
particularly if the element has a non-throwing move constructor. The
gain from reduced contention will generally more than offset additional
cache misses if contention would otherwise cause scalability issues.

Chris