Chapter 20: Dynamic Arrays: `std::vector`

Basic Usage

#include <vector>
std::vector<int> empty{}; // vector containing 0 int elements
std::vector<int> primes{ 2, 3, 5, 7 };          // vector containing 4 int elements with values 2, 3, 5, and 7
std::vector vowels { 'a', 'e', 'i', 'o', 'u' }; // vector containing 5 char elements with values 'a', 'e', 'i', 'o', and 'u'. Uses CTAD

std::vector<int> data(10); // vector containing 10 int elements, value-initialized to 0

primes.size();     // returns length as type `size_type` (alias for `std::size_t`)
std::size(primes); // C++17, returns length as type `size_type` (alias for `std::size_t`)
std::ssize(primes); // C++20, returns length as a large signed integral type

#include <vector>

struct Foo
{
    std::vector<int> v1(8); // compile error: direct initialization not allowed for member default initializers
    std::vector<int> v{ std::vector<int>(8) }; // ok
};

Vector can be const but can’t be constexpr (use std::array for constexpr).
Sign conversions are narrowing conversions, except when constexpr.

Accessing Elements

primes[2];
primes.at(3); // print the value of element with index 3
primes.at(9); // invalid index (throws exception)

at() is slower (but safer) than operator[].

Passing Vectors to Functions

void passByRef(const std::vector<int>& arr); // we must explicitly specify <int> here

void passByRef(const auto& arr); // C++20

template <typename T>
void passByRef(const T& arr); // will accept any type of object that has an overloaded operator[]

Copy and Move Semantics

Move semantics is an optimization that allows us, under certain circumstances, to inexpensively transfer ownership of some data members from one object to another object (rather than making a more expensive copy).
Data members that can’t be moved are copied instead.
We can return move-capable types (like std::vector and std::string) by value. Such types will inexpensively move their values instead of making an expensive copy (still better const reference).

Loops

std::size_t length { primes.size() };
for (std::size_t index{ 0 }; index < length; ++index)
{
    // Do something with primes[index]
}

Using Sign Values in Loops

Type
- Normal size: int
- Large:
  - std::ptrdiff_t
  - Your own type alias
```
using Index = std::ptrdiff_t;
for (Index index{ 0 };;)
```

Getting length of array

Static cast

auto length{ static_cast<Index>(arr.size()) };

std::ssize() C++20
```
auto index{ std::ssize(arr) - 1 }
```

Converting the signed loop variable to an unsigned index

Converting function

template <typename T>
constexpr std::size_t toUZ(T value)
{
    // make sure T is an integral type
    static_assert(std::is_integral<T>() || std::is_enum<T>());

    return static_cast<std::size_t>(value);
}

Operator overloading

// SignedArrayView.h
#ifndef SIGNED_ARRAY_VIEW_H
#define SIGNED_ARRAY_VIEW_H

#include <cstddef> // for std::size_t and std::ptrdiff_t

// SignedArrayView provides a view into a container that supports indexing
// allowing us to work with these types using signed indices
template <typename T>
class SignedArrayView
{
private:
    T& m_array;

public:
    using Index = std::ptrdiff_t;

    SignedArrayView(T& array)
        : m_array{ array } {}

    // Overload operator[] to take a signed index
    constexpr auto& operator[](Index index) { return m_array[static_cast<typename T::size_type>(index)]; }
    constexpr const auto& operator[](Index index) const { return m_array[static_cast<typename T::size_type>(index)]; }
    constexpr auto ssize() const { return static_cast<Index>(m_array.size()); }
};

#endif
// main.cpp
#include <iostream>
#include <vector>
#include "SignedArrayView.h"

int main()
{
    std::vector arr{ 9, 7, 5, 3, 1 };
    SignedArrayView sarr{ arr }; // Create a signed view of our std::vector

    for (auto index{ sarr.ssize() - 1 }; index >= 0; --index)
        std::cout << sarr[index] << ' '; // index using a signed type

    return 0;
}

Range-Based For Loops (For-Each Loop)

for (int /*auto*/ num : primes) // num same type as primes
    std::cout << num; // print the current value of num

for (const auto& word : words) // word is now a const reference

Auto vs Auto& vs Const Auto&

auto when you want to modify copies of the elements.
auto& when you want to modify the original elements.
const auto& otherwise (when you just need to view the original elements).

Using Unscoped Enumerators for Indexing

namespace Students
{
    enum Names : unsigned int // explicitly specifies the underlying type is unsigned int
    {
        kenny, // 0
        kyle, // 1
        stan, // 2
        butters, // 3
        cartman, // 4
        max_students // 5
    };
}

std::vector<int> testScores { 78, 94, 66, 77, 14 };
testScores[Students::stan] = 76; // we are now updating the test score belonging to stan

Students::Names name { Students::stan }; // non-constexpr
testScores[name] = 76; // may trigger a sign conversion warning if Student::Names defaults to a signed underlying type, enum Names : unsigned int -> no warning

// Ensure the number of test scores is the same as the number of students
assert(std::size(testScores) == Students::max_students);

Using Scoped Enumerators for Indexing

enum class StudentNames // now an enum class
{
    kenny, // 0
    kyle, // 1
    stan, // 2
    butters, // 3
    cartman, // 4
    max_students // 5
};

std::vector<int> testScores(static_cast<int>(StudentNames::max_students)); // use static_cast

// Overload the unary + operator to convert StudentNames to the underlying type
constexpr auto operator+(StudentNames a) noexcept
{
    return static_cast<std::underlying_type_t<StudentNames>>(a);
}

std::vector<int> testScores(+StudentNames::max_students);

Dynamic Array Operations

Resizing

v.resize(5);   // resize to 5 elements larger
v.resize(3);   // resize to 3 elements smaller

The length of a vector is how many elements are “in use”. The capacity of a vector is how many elements have been allocated in memory.

v.capacity();

When a std::vector changes the amount of storage it is managing, this process is called reallocation, which typically requires every element in the array to be copied. This can be expensive.

std::vector<int> v(1000); // allocate room for 1000 elements
v.resize(0);
v.shrink_to_fit(); // now room for 0, it can be ignored by the compiler

std::vector<int> stack(5); // direct set capacity

Stack Operations

Operation Name	Behavior	Required?	Notes
Push	Put new element on top of stack	Yes
Pop	Remove the top element from the stack	Yes	May return the removed element or void
Top or Peek	Get the top element on the stack	Optional	Does not remove item
Empty	Determine if stack has no elements	Optional
Size	Count of how many elements are on the stack	Optional
push_back()	Push	Put new element on top of stack	Adds the element to end of vector
pop_back()	Pop	Remove the top element from the stack	Returns void, removes element at end of vector
back()	Top or Peek	Get the top element on the stack	Does not remove item
emplace_back()	Push	Alternate form of push_back() that can be more efficient	Adds element to end of vector
reserve()		Changes just the capacity (if necessary)
resize()		Changes the length of the vector, and the capacity (if necessary)
emplace_back()	Push	When creating a new temporary object to add to the container, or when you need to access an explicit constructor

`std::vector<bool>`

std::vector<bool> is not a vector or container. Favor constexpr std::bitset, std::vector<char>, or 3rd party dynamic bitsets.

Chapter 20: Dynamic Arrays: std::vector