How to Efficiently Select a Standard Library Container in C++11

How can I efficiently select a Standard Library container in C++11?

Not that I know of, however it can be done textually I guess. Also, the chart is slightly off, because list is not such a good container in general, and neither is forward_list. Both lists are very specialized containers for niche applications.

To build such a chart, you just need two simple guidelines:

Choose for semantics first
When several choices are available, go for the simplest

Worrying about performance is usually useless at first. The big O considerations only really kick in when you start handling a few thousands (or more) of items.

There are two big categories of containers:

Associative containers: they have a find operation
Simple Sequence containers

and then you can build several adapters on top of them: stack, queue, priority_queue. I will leave the adapters out here, they are sufficiently specialized to be recognizable.

Question 1: Associative ?

If you need to easily search by one key, then you need an associative container
If you need to have the elements sorted, then you need an ordered associative container
Otherwise, jump to the question 2.

Question 1.1: Ordered ?

If you do not need a specific order, use an unordered_ container, otherwise use its traditional ordered counterpart.

Question 1.2: Separate Key ?

If the key is separate from the value, use a map, otherwise use a set

Question 1.3: Duplicates ?

If you want to keep duplicates, use a multi, otherwise do not.

Example:

Suppose that I have several persons with a unique ID associated to them, and I would like to retrieve a person data from its ID as simply as possible.

I want a find function, thus an associative container

1.1. I couldn't care less about order, thus an unordered_ container

1.2. My key (ID) is separate from the value it is associated with, thus a map

1.3. The ID is unique, thus no duplicate should creep in.

The final answer is: std::unordered_map<ID, PersonData>.

Question 2: Memory stable ?

If the elements should be stable in memory (ie, they should not move around when the container itself is modified), then use some list
Otherwise, jump to question 3.

Question 2.1: Which ?

Settle for a list; a forward_list is only useful for lesser memory footprint.

Question 3: Dynamically sized ?

If the container has a known size (at compilation time), and this size will not be altered during the course of the program, and the elements are default constructible or you can provide a full initialization list (using the { ... } syntax), then use an array. It replaces the traditional C-array, but with convenient functions.
Otherwise, jump to question 4.

Question 4: Double-ended ?

If you wish to be able to remove items from both the front and back, then use a deque, otherwise use a vector.

You will note that, by default, unless you need an associative container, your choice will be a vector. It turns out it is also Sutter and Stroustrup's recommendation.

C++ standard container and STL container in c++

Nothing in the C++ Standard Library "belongs" to the STL. STL is a different library that only influenced many parts in the C++ Standard Library. From the tag wiki:

[STL] is a C++ library of generic containers, iterators, algorithms,
and function objects. When C++ was standardised, large parts of the
STL were adopted into the Standard Library, […]

However, many people refer to the C++ Standard Library as the Standard Template Library, which is not entirely correct. I'm guessing that if you're not allowed to use the STL, they actually mean that you're not allowed to use the C++ Standard Library. But you'd have to ask them to know what they really mean.

For more information, see What's the difference between "STL" and "C++ Standard Library"?

std::list of objects efficiency

This is always a though question.

First of all, it really depends whether your compiler supports C++11 move semantics or not, as this dramatically change the aspects of the problem.

For those stuck in C++03

There are multiple choices:

std::list<MyClass> list;
list.push_front(MyClass());

Even though semantically there is a copy, the optimizer might remove most of the redundant/dead stores. Most optimizers will require that the definition of the default constructor and copy constuctor be available.

boost::ptr_deque<MyClass> deque;
std::auto_ptr<MyClass> p(new MyClass());
deque.push_front(p);

ptr_vector could be used should you replace push_front with push_back, otherwise it's a bit wasteful. This avoids most of the memory overhead of a std::list<MyClass*> and has the added bonus of automatically handling memory.

boost::stable_vector<MyClass> svec;
svec.push_back(MyClass());
//        ~~~~

There is one copy (as with list) but a guarantee that no further copy should be made within the container (as with list). It also allows a few more operations than list (for example, random access), at the cost of being slower for insertion in the middle for large containers.

For those enjoying C++11

std::list<MyClass> list;
list.push_front(MyClass());

does not generate any copy, instead a move operation occurs.

It is also possible to use the new operations provided to construct objects in place:

std::list<MyClass> list;
list.emplace_front();

will create a new MyClass directly within the node, no copy, no move.

And finally, you may wish for a more compact representation or other operations on the container, in which case:

std::vector<std::unique_ptr<MyClass>> vec;
vec.emplace_back(new MyClass());

Offers you random access and a lower memory overhead.

Container version of C++ sort

He wrote that himself, it is not standard. Thus you cannot find it in the standard library. You could implement it like this:

template <class Container, class Comp>
void sort (Container& cont, Comp comp) {
    using std::begin;
    using std::end;
    std::sort(begin(cont), end(cont), comp);
}

As Clukester pointed out, there is also boost::sort that offers this functionality.

Which STL container should I use? C++

We can give you guidelines, but no definitive answer – you need to benchmark that yourself because it crucially depends on your collection and object size:

For small objects and/or a relatively small collection, std::vector will be faster because even though you need to copy more data, the better random access time (O(1) vs O(n) for std::list) and the cache locality will dominate.
For large objects and/or a large collection, std::list will be faster because although you need O(n) to pick a random object, insertion will be much faster since the copying of many large objects is very slow.

But where exactly the cut-off between these two scenarios lies I cannot say.

Furthermore, if you can get away with swapping the elements instead of insertion, this is a no-brainer: always use a std::vector.

How to implement a SQL like container in C++

I'd use Boost MultiIndex containers. Let me draw up a sample:

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <vector>

enum class color_t { NB, PP, DP, O };

struct Record {
    int     ID;
    int     Type;
    color_t Color;
    double  Weight;
    uint8_t Hex;
};

namespace bmi = boost::multi_index;

using Table = boost::multi_index_container<
    Record,
    bmi::indexed_by<
        bmi::sequenced<bmi::tag<struct byInsertion> >,
        bmi::ordered_unique<bmi::tag<struct byID>, bmi::member<Record, int, &Record::ID> >,
        bmi::hashed_non_unique<bmi::tag<struct byType>, bmi::member<Record, int, &Record::Type> >,
        bmi::ordered_non_unique<bmi::tag<struct byDetails>,
            bmi::composite_key<Record,
                bmi::member<Record, color_t, &Record::Color>,
                bmi::member<Record, uint8_t, &Record::Hex>,
                bmi::member<Record, double,  &Record::Weight>
            >
        >,
        bmi::random_access<bmi::tag<struct byCustomRandomAccess> >
    >
>;

#include <boost/range/adaptors.hpp>  // lazy demo purposes
#include <boost/range/algorithm.hpp> 
#include <boost/range/algorithm_ext.hpp> 
#include <iostream>

using namespace boost::adaptors;


int main() {
    auto getId = [](auto& r) { return r.ID; };

    auto dump = [](auto&& range) -> auto& { 
        for (auto&& v:range) std::cout << v << " ";
        return std::cout;
    };

    Table table {
       Record { 4, 1, color_t::PP, 4.0, 0x10 },
       Record { 3, 1, color_t::NB, 3.8, 0x03 },
       Record { 7, 2, color_t::O,  6.0, 0x09 },
       Record { 1, 1, color_t::NB, 3.5, 0x12 },
       Record { 2, 1, color_t::NB, 3.5, 0x14 },
       Record { 5, 2, color_t::DP, 3.5, 0x15 },
       Record { 6, 2, color_t::O,  5.0, 0x12 },
    };

    using namespace boost;

    std::cout << "Insertion order: ";
    dump(table | transformed(getId)) << "\n";

    std::cout << "byID: ";
    dump(table.get<byID>() | transformed(getId)) << "\n";

    std::cout << "Type 2: ";
    dump(
        make_iterator_range(table.get<byType>().equal_range(2))
      | transformed(getId)) << "\n";

    auto& query = table.get<byDetails>();

    std::cout << "Color == NB, Hex = [0x00..0x0f]: ";
    {
        auto lb = query.upper_bound(make_tuple(color_t::NB, 0x00));
        auto ub = query.upper_bound(make_tuple(color_t::NB, 0x0f));

        dump(make_iterator_range(lb, ub) | transformed(getId)) << "\n";
    }

    std::cout << "Color == NB: ";
    dump(make_iterator_range(query.equal_range(make_tuple(color_t::NB))) | transformed(getId)) << "\n";

    // adhoc order:
    {
        auto& adhoc = table.get<byCustomRandomAccess>();

        std::vector<reference_wrapper<Record const>> tmp(adhoc.begin(), adhoc.end());

        // random shuffle, e.g.:
        std::random_shuffle(tmp.begin(), tmp.end());

        // OR: use some crazy order
        auto craziness =  [](Record const& a, Record const& b) 
                { return (a.ID - 10*a.Type) < (b.ID - 10*b.Type); };

        sort(tmp, craziness);

        // optionally, reflect that order back into the `byCustomRandomAccess` index:
        adhoc.rearrange(tmp.begin());
    }

    std::cout << "Custom order persisted: ";
    dump(table.get<byCustomRandomAccess>() | transformed(getId)) << "\n";
}

Prints:

Insertion order: 4 3 7 1 2 5 6 
byID: 1 2 3 4 5 6 7 
Type 2: 6 5 7 
Color == NB, Hex = [0x00..0x0f]: 3 
Color == NB: 3 1 2 
Custom order persisted: 5 6 7 1 2 3 4

In which scenario do I use a particular STL container?

This cheat sheet provides a pretty good summary of the different containers.

See the flowchart at the bottom as a guide on which to use in different usage scenarios:

_{Created by David Moore and licensed CC BY-SA 3.0}

Best STL container to use

I'd say just create a SongLibrary to encapsulate the song storage implementation and the container used. Having the container exposed to the main class will pollute it, make it harder to test and more difficult to extend (e.g. shuffling).

And by doing so, you can later more easily change the container used without changes to the callers.

As for the container, there's a lot to consider, e.g.: do you need faster read time or write time? Usually we prefer the former, so in that case index-based containers would be better. Anyways, this might just end up being premature optimization so I'd say just choose the std::set since it already handles duplicates, which makes your life easier. Then, if that proves to be not enough, you can always modify your library class.

Which C++20 standard library containers have a .at member access function?

I ended up grepping libstdc++ include directory for \bat( and that has given me:

std::basic_string
std::basic_string_view
std::array
std::vector
std::vector<bool>
std::unordered_map
std::map
std::dequeue

I'm not sure if this is exhaustive.

There is also rope and vstring but I don't think these are standard.