Containers may be most useful C++ library components. As the standard grows, in C++11/14  sequential containers have evolved, though not as much as some other container categories. Two changes most worthy of attention are the addition of 2 new types, std::array and std::forward_list, to sequential containers.

 

1. std::array class template

std::array is similar to std::vector, but with limited container interfaces. The most notable feature of std::array is that its size cannot be changed; in contrast, std::vector may grow in storage when data exceeds its storage size. In fact the underlying storage allocated by std::array could be just as much as that of a C-style array. Unlike std::vector, whose interfaces like std::array::size do not return a value from private members, std::array::size returns a constant value at template instantiation. That avoids storage management overhead at run time. (Actually it does not require storage management.) The payment is that users must specify the size as an non-type template parameter to std::array at declaration.

 

Unlike std::vector, by default std::array allocates storage like the C-style array. The following example shows the condition:

 

#include <array>

#include <vector>

#include <iostream>

 

using namespace std;

 

int main() {

    int stack_var;

    array<int, 5> a;

    vector<int> v(5);

 

    cout << "stack area: 0x" << hex << (uintptr_t)&stack_var << endl;

    cout << "a[3] address: 0x" << hex << (uintptr_t)&a[3] << endl;

    cout << "b[3] address: 0x" << hex << (uintptr_t)&v[3] << endl;

 

    return 0;

}

 

The output on my local POWER8 Linux system is:

 

stack area: 0x3fffce0b9f34

a[3] address: 0x3fffce0b9f44

b[3] address: 0x1003837001c

 

It is obvious that std::array can be allocated from a stack area (together with stack_var), where std::vector might allocate storage elsewhere (probably to heap). Similarly, if we use std::new to create an std::array object, the array elements should be placed at heap. And global/static data will finally be placed in the binary data area. 

 

Like std::vector, std::array provides 2 interfaces, member "operator[]" and member "at", for element retrieval and modification. The latter will check the out-of-bound condition but not the operator version for higher performance. Furthermore, with iterator support std::array could work fine with the algorithm library. However, it is worth noticing that std::array::swap takes linear time to complete, while std::array::swap takes just constant time (through pointer exchange).

 

So for C++11/14 programmers, when you want to equip your fix-size array with rich C++-styled interfaces, std::array could be a better choice than the C-style array. When you need to fall back to the C-style array, std::array::data would guarantee code compatibility. 

 

2. std::forward_list class template

As described in the C++ standard, a forward_list container is a container that supports forward iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. The major difference between std::forward_list and std::list is that the former does not have chain back. Conceptually, std::forward_list, by saving pointers greatly, would consume less memory than std::list. 

 

And it is interesting that std::forward_list does not provide the size() operation at all. Among all known STL containers, it is the only container that does not provide size(). The reason that this interface is not provided is that library users would otherwise face the complexity of the size() of std::forward_list being linear.  All the other containers provide size() as an operation that can be finished in constant time (in C++11 and later; in C++98, linear is acceptable for std::list). To minimize memory usage, std::forward_list does not even track the length of the list. Suppose "l" is an std::forward_list<T> object, users should always use std:distance(l.begin(), l.end()) to calculate its size. It brings in some inconvenience, but hopefully will keep users away from the hot spot inside the size() operation. 

 

Another surprise is that std::forward_list does insertion/deletion AFTER the given position. Namely, these interfaces are std::forward_list::insert_after, std::forward_list::erase_after, std::forward_list::emplace_after, and splice_after. Meanwhile, all other known sequence containers insert elements before the given position (except std::array, which does not allow insertions).  Considering the nature of singly-linked list - it would cost O(N) to find an element before the given position, but O(1) to find the element after the given position, it is natural that AFTER operations are the first choice for std::forward_list. Similarly, the library does not provide BEFORE operations with the intention that programmers would be aware of costly insertions.

 

And also for performance considerations, std::forward_list does not provide any interface that std::list operates from the end of the list, including back(), push_back(), pop_back(), and emplace_back(). Such operations would cost at least O(N) to complete. 

 

Generally speaking, std::forward_list may have performance disadvantage against std::list as it can only be visited in a single direction iteratively. However, it does have advantage over std::list on memory usage. It could be acceptable to replace std::list with std::forward_list when memory consumption is of primary consideration, and also when the impact on the "back-and-forth" nodes access is limited. Anyway, how much memory can be saved by this change depends on the implementation of the library. And the potential performance impact should be evaluated by tuning if it is hard to figure out the node access.