Standard C艹

C艹11 Standard Library Extensions — Containers and Algorithms

Algorithms improvements

The standard library algorithms are improved partly by simple addition of new algorithms, partly by improved implementations made possible by new language features, and partly by new language features enabling easier use:

New algorithms:

    bool all_of(Iter first, Iter last, Pred pred);
    bool any_of(Iter first, Iter last, Pred pred);
    bool none_of(Iter first, Iter last, Pred pred);

    Iter find_if_not(Iter first, Iter last, Pred pred);

    OutIter copy_if(InIter first, InIter last, OutIter result, Pred pred);
    OutIter copy_n(InIter first, InIter::difference_type n, OutIter result);

    OutIter move(InIter first, InIter last, OutIter result);
    OutIter move_backward(InIter first, InIter last, OutIter result);

    pair<OutIter1, OutIter2> partition_copy(InIter first, InIter last, OutIter1 out_true, OutIter2 out_false, Pred pred);
    Iter partition_point(Iter first, Iter last, Pred pred);

    RAIter partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last);
    RAIter partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last, Compare comp);
    bool is_sorted(Iter first, Iter last);
    bool is_sorted(Iter first, Iter last, Compare comp);
    Iter is_sorted_until(Iter first, Iter last);
    Iter is_sorted_until(Iter first, Iter last, Compare comp);

    bool is_heap(Iter first, Iter last);
    bool is_heap(Iter first, Iter last, Compare comp);
    Iter is_heap_until(Iter first, Iter last);
    Iter is_heap_until(Iter first, Iter last, Compare comp);

    T min(initializer_list<T> t);
    T min(initializer_list<T> t, Compare comp);
    T max(initializer_list<T> t);
    T max(initializer_list<T> t, Compare comp);
    pair<const T&, const T&> minmax(const T& a, const T& b);
    pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
    pair<const T&, const T&> minmax(initializer_list<T> t);
    pair<const T&, const T&> minmax(initializer_list<T> t, Compare comp);
    pair<Iter, Iter> minmax_element(Iter first, Iter last);
    pair<Iter, Iter> minmax_element(Iter first, Iter last, Compare comp);

    void iota(Iter first, Iter last, T value);  // For each element referred to by the iterator i in the range [first,last), assigns *i = value and increments value as if by ++value

Effects of move: Moving can be much more efficient than copying (see Move semantics. For example, move-based std::sort() and std::set::insert() have been measured to be 15 times faster than copy based versions. This is less impressive than it sounds because such standard library operations for standard library types, such as string and vector, are usually hand-optimized to gain the effects of moving through techniques such as replacing copies with optimized swaps. However, if your type has a move operation, you gain the performance benefits automatically from the standard algorithms. Consider also that the use of moves allows simple and efficient sort (and other algorithms) of containers of smart pointers, especially unique_ptr:

    template<class P> struct Cmp<P> {   // compare *P values
        bool operator() (P a, P b) const { return *a<*b; }
    }

    vector<std::unique_ptr<Big>> vb;
    // fill vb with unique_ptr's to Big objects

    sort(vb.begin(),vb.end(),Cmp<Big>());   // don't try that with an auto_ptr

Use of lambdas: For ages, people have complained about having to write functions or (better) function objects for use as operations, such as Cmp<T> above, for standard library (and other) algorithms. This was especially painful to do if you wrote large functions (don’t) because in C艹98 you could not define a local function object to use as an argument; now you can. However, lambdas allows us to define operations “inline”:

    sort(vb.begin(),vb.end(),[](unique_ptr<Big> a, unique_ptr<Big> b) { return *a<*b; });

Use of initializer lists: Sometimes, initializer lists come in handy as arguments. For example, assuming string variables and Nocase being a case-insensitive comparison:

    auto x = max({x,y,z},Nocase());

See also:

25 Algorithms library [algorithms]
26.7 Generalized numeric operations [numeric.ops]
Howard E. Hinnant, Peter Dimov, and Dave Abrahams: A Proposal to Add Move Semantics Support to the C艹 Language. N1377=02-0035.

Container improvements

Given the new language features and a decade’s worth of experience, what has happened to the standard containers? First, of course we got a few new ones: array (a fixed-sized container), forward_list (a singly-linked list), and unordered containers (the hash tables). Next, new features, such as initializer lists, rvalue references, variadic templates, and constexpr[cpp11-constexpr] were put to use. Consider std::vector.

Initializer lists: The most visible improvement is the use of initializer-list constructors to allow a container to take an initializer list as its argument:

    vector<string> vs = { "Hello", ", ", "World!", "\n" };
    for (auto s : vs ) cout << s;

Move operators: Containers now have move constructors and move assignments (in addition to the traditional copy operations). The most important implication of this is that we can efficiently return a container by value from a function:

    vector<int> make_random(int n)
    {
        vector<int> ref(n);
        for(auto& x : ref) x = rand_int(0,255); // some random number generator
        return ref;
    }

    vector<int> v = make_random(10000);
    for (auto x : make_random(1000000)) cout << x << '\n';

The point here is that no vectors are copied. Rewrite this to return a free-store-allocated vector and you have to deal with memory management. Rewrite this to pass the vector to be filled as an argument to make_random() and you have a far less obvious code (plus an added opportunity for making an error).

Improved push operations: Many people’s favorite container operation is push_back() that allows a container to grow gracefully:

    vector<pair<string,int>> vp;
    string s;
    int i;
    while(cin>>s>>i) vp.push_back({s,i});

This will construct a pair<string,int> out of s and i and move it into vp. Note “move” not “copy;” there is a push_back version that takes an rvalue reference argument so that we can take advantage of string’s move constructor. Note also the use of the uniform initializer syntax to avoid verbosity.

Emplace operations: The push_back() using a move constructor is far more efficient in important cases than the traditional copy-based one, but in extreme cases we can go further. Why copy/move anything? Why not make space in the vector and then construct the desired value in that space? Operations that do that are called “emplace” (meaning “putting in place”). For example emplace_back():

    vector<pair<string,int>> vp;
    string s;
    int i;
    while(cin>>s>>i) vp.emplace_back(s,i);

An emplace takes a variadic template argument and uses that to construct an object of the desired type. Whether the emplace_back() really is more efficient than the push_back() depends on the types involved and the implementation (of the library and of variadic templates). If you think it matters, measure. Otherwise, choose based on aesthetics: vp.push_back({s,i}); or vp.emplace_back(s,i);. For now, many prefer the push_back() version in part due to familiarity, but that might change over time.

Scoped allocators: Containers can now hold “real allocation objects (with state)” and use those to control nested/scoped allocation (e.g. allocation of elements in a container).

Obviously, the containers are not the only parts of the standard library that have benefited from the new language features. Consider:

Compile-time evaluation: constexpr is used to ensure compiler time evaluation in <numeric_limits>, bitset, duration, char_traits, array, atomic types, random numbers, complex, etc. In some cases, it means improved performance; in others (where there is no alternative to compile-time evaluation), it means absence of messy low-level code and macros.
Tuples: Tuples would not be possible without variadic templates

`unordered_*` containers

An unordered_* container is implemented using a hash table. C艹11 offers four standard ones:

unordered_map
unordered_set
unordered_multimap
unordered_multiset

They would have been called hash_map etc., but there are so many incompatible uses of those names that the committee had to choose new names and the unordered_* name nicely highlighted the key difference between (say) map and unordered_map: When you iterate over a map from begin() to end(), you do so in the order provided by its key type’s less-than comparison operator (by default <) whereas the value type of unordered_map is not required to have a less-than comparison operator and a hash table doesn’t naturally provide an order. The are other differences; in particular, conversely, the element type of a map is not required to have a hash function.

The basic idea is simply to use unordered_map as an optimized version of map where optimization is possible and reasonable. For example:

    map<string,int> m {
        {"Dijkstra",1972}, {"Scott",1976}, {"Wilkes",1967}, {"Hamming",1968}
    };
    m["Ritchie"] = 1983;
    for(auto& x : m) cout << '{' << x.first << ',' << x.second << '}';

    unordered_map<string,int> um {
        {"Dijkstra",1972}, {"Scott",1976}, {"Wilkes",1967}, {"Hamming",1968}
    };
    um["Ritchie"] = 1983;
    for(auto& x : um) cout << '{' << x.first << ',' << x.second << '}';

The iterator over m will present the elements in alphabetical order; the iteration over um will not (except through a freak accident). Lookup is implemented very differently for m and um. For m lookup involves log2(m.size()) less-than comparisons, whereas for um lookup involves a single call of a hash function and one or more equality operations. For a few elements (say a few dozen), it is hard to tell which is faster. For larger numbers of elements (e.g. thousands), lookup in an unordered_map can be much faster than for a map.

See also:

Standard: 23.5 Unordered associative containers.

`std::array`

The standard container array is a fixed-sized random-access sequence of elements defined in <array>. It has no space overheads beyond what it needs to hold its elements, it does not use free store, it can be initialized with an initializer list, it knows its size (number of elements), and doesn’t convert to a pointer unless you explicitly ask it to. In other words, it is very much like a built-in array without the problems.

    array<int,6> a = { 1, 2, 3 };
    a[3]=4;
    int x = a[5];       // x becomes 0 because default elements are zero initialized
    int* p1 = a;        // error: std::array doesn't implicitly convert to a pointer
    int* p2 = a.data(); // ok: get pointer to first element

Note that you can have zero-length arrays but that you cannot deduce the length of an array from an initializer list:

    array<int> a3 = { 1, 2, 3 };    // error: size unknown/missing
    array<int,0> a0;        // ok: no elements
    int* p = a0.data();     // unspecified; don't try it

The standard array’s features makes it attractive for embedded systems programming (and similar constrained, performance-critical, or safety critical tasks). It is a sequence container so it provides the usual member types and functions (just like vector):

    template<class C> typename C::value_type sum(const C& a)
    {
        return accumulate(a.begin(),a.end(),0);
    }

    array<int,10> a10;
    array<double,1000> a1000;
    vector<int> v;
    // ...
    int x1 = sum(a10);
    double x2 = sum(a1000);
    int x3 = sum(v);

Also, you don’t get (potentially nasty) derived to base conversions:

    struct Apple : Fruit { /* ... */ };
    struct Pear : Fruit { /* ... */ };

    void nasty(array<Fruit*,10>& f)
    {
        f[7] = new Pear();
    };

    array<Apple*,10> apples;
    // ...
    nasty(apples);  // error: can't convert array<Apple*,10> to array<Fruit*,10>;

If that was allowed, apples would now contain a Pear.

See also:

Standard: 23.3.1 Class template array

`forward_list`

The standard container forward_list, defined in <forward_list>, is basically a singly-linked list. It supports forward iteration (only) and guarantees that elements don’t move if you insert or erase one. It occupies minimal space (an empty list is likely to be one word) and does not provide a size() operation (so that it does not have to store a size member):

    template <ValueType T, Allocator Alloc = allocator<T> >
        // requires NothrowDestructible<T>
    class forward_list {
    public:
        // the usual container stuff
        // no size()
        // no reverse iteration
        // no back() or push_back()
    };

See also:

Standard: 23.3.3 Class template forward_list

C艹11 Standard Library Extensions — Containers and Algorithms

Algorithms improvements

Container improvements

unordered_* containers

std::array

forward_list

`unordered_*` containers

`std::array`

`forward_list`