The simplest container: std::array<T, N>

The simplest standard container class is std::array<T, N>, which behaves just like a built-in ("C-style") array. The first template parameter to std::array indicates the type of the array's elements, and the second template parameter indicates the number of elements in the array. This is one of the very few places in the standard library where a template parameter is an integer value instead of the name of a type.

Normal C-style arrays, being part of the core language (and a part that dates back to the 1970s, at that!), do not provide any built-in operations that would take linear time to run. C-style arrays let you index into them with operator[], and compare their addresses, since those operations can be done in constant time; but if you want to assign the entire contents of one C-style array to another, or compare the contents of two arrays, you'll find that you can't do it straightforwardly. You'll have to use some of the standard algorithms we discussed in Chapter 3, The Iterator-Pair Algorithms, such as std::copy or std::equal (the function template std::swap, being an "algorithm" already, does work for C-style arrays. It would be a shame if it didn't work.):

    std::string c_style[4] = {
      "the", "quick", "brown", "fox"
    };
    assert(c_style[2] == "brown");
    assert(std::size(c_style) == 4);
    assert(std::distance(std::begin(c_style), std::end(c_style)) == 4);

    // Copying via operator= isn't supported.
    std::string other[4]; 
    std::copy(std::begin(c_style), std::end(c_style), std::begin(other));

    // Swapping IS supported... in linear time, of course.
    using std::swap;
    swap(c_style, other);

    // Comparison isn't supported; you have to use a standard algorithm.
    // Worse, operator== does the "wrong" thing: address comparison!
    assert(c_style != other);
    assert(std::equal(
      c_style, c_style + 4,
      other, other + 4 
    ));
    assert(!std::lexicographical_compare(
      c_style, c_style + 4,
      other, other + 4
   ));

std::array behaves just like a C-style array, but with more syntactic sugar. It offers .begin() and .end() member functions; and it overloads the operators =, ==, and < to do the natural things. All of these operations still take time linear in the size of the array, because they have to walk through the array copying (or swapping or comparing) each individual element one at a time.

One gripe about std::array, which you'll see recurring for a few of these standard container classes, is that when you construct a std::array with an initializer list inside a set of curly braces, you actually need to write two sets of curly braces. That's one set for the "outer object" of type std::array<T, N>, and another set for the "inner data member" of type T[N]. This is a bit annoying at first, but the double-brace syntax will quickly become second nature once you have used it a few times:

    std::array<std::string, 4> arr = {{
      "the", "quick", "brown", "fox"
    }};
    assert(arr[2] == "brown");

    // .begin(), .end(), and .size() are all provided.
    assert(arr.size() == 4);
    assert(std::distance(arr.begin(), arr.end()) == 4);

    // Copying via operator= is supported... in linear time.
    std::array<std::string, 4> other;
    other = arr;

    // Swapping is also supported... in linear time.
    using std::swap;
    swap(arr, other);

    // operator== does the natural thing: value comparison!
    assert(&arr != &other); // The arrays have different addresses... 
    assert(arr == other); // ...but still compare lexicographically equal.
    assert(arr >= other); // Relational operators are also supported.

One other benefit of std::array is that you can return one from a function, which you can't do with C-style arrays:

    // You can't return a C-style array from a function.
    // auto cross_product(const int (&a)[3], const int (&b)[3]) -> int[3];

    // But you can return a std::array.
    auto cross_product(const std::array<int, 3>& a,
     const std::array<int, 3>& b) -> std::array<int, 3>
    {
      return {{
        a[1] * b[2] - a[2] * b[1],
        a[2] * b[0] - a[0] * b[2],
        a[0] * b[1] - a[1] * b[0],
      }};
    }

Because std::array has a copy constructor and a copy assignment operator, you can also store them in containers: for example, std::vector<std::array<int, 3>> is fine whereas std::vector<int[3]> wouldn't work.

However, if you find yourself returning arrays from functions or storing arrays in containers very often, you should consider whether "array" is really the right abstraction for your purposes. Would it be more appropriate to wrap that array up into some kind of class type?

In the case of our cross_product example, it turns out to be an extremely good idea to encapsulate our "array of three integers" in a class type. Not only does this allow us to name the members (x, y, and z), but we can also initialize objects of the Vec3 class type more easily (no second pair of curly braces!) and perhaps most importantly for our future sanity, we can avoid defining the comparison operators such as operator< which don't actually make sense for our mathematical domain. Using std::array, we have to deal with the fact that the array {1, 2, 3} compares "less than" the array {1, 3, -9}--but when we define our own class Vec3, we can simply omit any mention of operator< and thus ensure that nobody will ever accidentally misuse it in a mathematical context:

    struct Vec3 {
      int x, y, z;
      Vec3(int x, int y, int z) : x(x), y(y), z(z) {}
    };

    bool operator==(const Vec3& a, const Vec3& b) {
      return std::tie(a.x, a.y, a.z) ==
         std::tie(b.x, b.y, b.z);
    }

    bool operator!=(const Vec3& a, const Vec3& b) {
      return !(a == b);
    }

    // Operators < <= > >= don't make sense for Vec3

    Vec3 cross_product(const Vec3& a, const Vec3& b) {
      return {
        a.y * b.z - a.z * b.y,
        a.z * b.x - a.x * b.z,
        a.x * b.y - a.y * b.x,
      };
    }

std::array holds its elements inside itself. Therefore, sizeof (std::array<int, 100>) is equal to sizeof (int[100]), which is equal to 100 * sizeof (int). Don't make the mistake of trying to place a gigantic array on the stack as a local variable!

    void dont_do_this()
    {
      // This variable takes up 4 megabytes of stack space ---
      // enough to blow your stack and cause a segmentation fault!
      int arr[1'000'000];
    }

    void dont_do_this_either()
    {
      // Changing it into a C++ std::array doesn't fix the problem.
      std::array<int, 1'000'000> arr;
    }

Working with "gigantic arrays" is a job for the next container on our list: std::vector.