std::vector and Dynamic Arrays recap

Congratulations! This section covered substantial ground and exposed some of C++'s rough edges. You've mastered the fundamentals of arrays and containers—powerful tools that unlock significant capabilities in your C++ programs.

Containers and Elements

Containers provide storage for collections of unnamed objects called elements. The number of elements is the container's length or size. C++ containers are homogeneous, requiring all elements to share the same type.

Arrays and Contiguous Storage

An array stores elements contiguously (in adjacent memory) and allows fast, direct element access.

std::vector as Dynamic Array

std::vector is a standard library container implementing a dynamic array. It's defined in <vector> as a class template with a template parameter for element type.

Initialization with List Constructors

Containers use list constructors for initialization. Use list initialization with initializer lists to construct containers with specific values.

Subscripting and Indexing

Subscripting accesses array elements via operator[]. Elements are zero-indexed, starting at 0. operator[] performs no bounds checking—invalid indices cause undefined behavior.

Random Access

Random access means every element is accessible directly with equal speed, regardless of container size.

Constructor Preferences

When constructing containers, list constructors are preferred over other constructors. For non-element-value initializers, use direct initialization.

const and constexpr Constraints

std::vector can be const but not constexpr.

size_type Typedef

Each standard container defines nested typedef size_type (often written T::size_type), aliasing the type used for lengths and indices. size_type almost always aliases std::size_t but can be customized.

Access size_type by scope-qualifying with the fully-templated container name: std::vector<int>::size_type.

Getting Container Length

Get container length using size() (member function) or std::size() (non-member function, C++17), both returning unsigned size_type. In C++20, std::ssize() returns length as a large signed integral type (usually std::ptrdiff_t).

Bounds-Checked Access with at()

The at() member function provides subscripting with runtime bounds checking, throwing std::out_of_range exceptions for invalid indices.

Sign Conversion Issues

Both operator[] and at() expect indices of type size_type (unsigned). This creates sign conversion issues with non-constexpr signed indices.

Passing Vectors Efficiently

Pass std::vector by (const) reference to avoid expensive copies. Use function templates to accept vectors of any element type.

Copy and Move Semantics

Copy semantics determines how objects are copied. Move semantics determines how data ownership transfers between objects. Move semantics moves movable data and copies unmovable data, offering potential performance benefits.

Move semantics automatically activates when the initializer is an rvalue of a move-capable type. std::vector and std::string support move semantics.

Return move-capable types by value—they'll inexpensively move instead of copy. Still pass them by const reference.

Traversal and Iteration

Traversal (or iteration) means accessing each container element in sequence.

Loops enable array traversal without explicit element enumeration. Templates parameterize element types. Together, templates, arrays, and loops create code working regardless of element type or count.

Range-Based For Loops

Range-based for loops (or for-each loops) traverse containers without explicit indexing, reducing errors. Use auto for type deduction. Use const auto& for read-only access to avoid copies.

Enumerations as Indices

Unscoped enumerations work as indices, providing self-documenting code. A count enumerator at the end automatically represents the preceding enumerator count. Assert that array length matches the count enumerator.

Fixed-Size vs Dynamic Arrays

Fixed-size arrays require compile-time lengths that cannot change. Dynamic arrays resize at runtime. std::vector is a dynamic array.

Resizing, Capacity, and Reallocation

Resize vectors using resize(). Capacity is allocated element count; length is elements in use. Get capacity via capacity().

Reallocation occurs when vectors change capacity—an expensive operation. Separating capacity from length avoids some reallocations. Valid indices depend on length, not capacity.

Use shrink_to_fit() to request capacity reduction (non-binding).

Stack Operations

A stack provides last-in, first-out (LIFO) ordering. Stack operations (push and pop) are available on std::vector.

push_back() and emplace_back() increment length and reallocate if needed. When pushing triggers reallocation, std::vector typically allocates extra capacity.

resize() vs reserve()

resize() changes length and capacity. reserve() changes only capacity. Use resize() for indexing, reserve() for stack operations.

push_back() vs emplace_back()

Prefer emplace_back() for temporaries or explicit constructors. Prefer push_back() otherwise.

std::vector Warning

std::vector<bool> is a specialized implementation that may compress booleans but is not a true container. Avoid it.

Best Practice Summary

Best practice: Use std::array for constexpr arrays, std::vector for non-constexpr arrays.

Key Terminology

  • Container: Storage for collections of unnamed objects
  • Element: Individual object stored in a container
  • Length/Size: Number of elements in a container
  • Homogeneous: All elements share the same type
  • Array: Container storing elements contiguously in memory
  • Contiguous: Elements stored in adjacent memory locations
  • Dynamic array: Array that can resize at runtime
  • Fixed-size array: Array with compile-time constant length
  • List constructor: Constructor accepting initializer list
  • Initializer list: Braced list of values for initialization
  • Subscripting: Accessing elements via operator[]
  • Zero-indexed: First element is at index 0
  • Bounds checking: Runtime verification that index is valid
  • Random access: Direct access to any element with equal speed
  • size_type: Unsigned type for container lengths and indices
  • Reference: Alias to another variable (avoids copying)
  • Copy semantics: Rules for copying objects
  • Move semantics: Rules for transferring data ownership
  • rvalue: Temporary value or expression result
  • Traversal/Iteration: Accessing each element in sequence
  • Range-based for loop: Loop traversing containers without explicit indices
  • Unscoped enumeration: Enumeration whose enumerators are in enclosing scope
  • Count enumerator: Final enumerator representing total count
  • Capacity: Number of elements allocated in memory
  • Reallocation: Changing a container's capacity
  • Stack: Last-in, first-out (LIFO) data structure
  • Push: Adding element to stack
  • Pop: Removing element from stack

Looking Forward

You've now mastered the fundamentals of arrays and containers in C++. The concepts covered in this section—std::vector, range-based for loops, move semantics, and stack operations—are essential tools you'll use throughout your C++ programming journey.

You'll build on this foundation by learning about additional container types like std::array, multi-dimensional arrays, and C-style arrays. You'll also explore algorithms that work with containers, enabling you to write more powerful and expressive code.

The combination of containers, templates, and loops gives you the ability to write flexible, reusable code that works with collections of any size and type. Practice these concepts thoroughly—they're fundamental to writing effective C++ programs.