Sequential Containers in C++

Language:中文/EN

Overview

A container is a collection of objects of a specific type. Sequential containers provide the ability to control the order of element storage and access.

Types of sequential containers:

  • vector: A dynamically sized array that supports fast random access
  • deque: A double-ended queue that supports fast random access
  • list: A doubly linked list that only supports bidirectional sequential access
  • forward_list: A singly linked list that only supports unidirectional sequential access
  • array: A fixed-size array
  • string: Similar to vector, but used solely for storing characters

Guidelines for choosing sequential containers:

  1. Compared to built-in arrays, array is a safer and easier-to-use array type. Modern C++ programs should use standard library containers instead of more primitive data structures like built-in arrays.
  2. Use vector unless there is a strong reason to choose another container.
  3. Other selection criteria can be determined based on the nature of data structures like arrays, linked lists, queues, etc.

Container Library and Sequential Container Operations

Most operations on sequential containers can be found in the C++ API, so they won’t be repeated here. Instead, here are a few notes:

Regarding iterators:

  1. The iterator c.end() points to the position after the last element. The range of iterators like c.begin() and c.end() is a half-open interval [begin, end).
  2. The singly linked list forward_list does not support decrement operations on iterators, which is easily understood given the nature of its data structure.
  3. If begin and end are equal, the range is empty; if they are not, the range contains at least one element.
  4. When creating a container as a copy of another, both containers must have the same type and element type. When copying by passing an iterator range, the element types do not need to match as long as they can be converted to the corresponding element type.
  5. Except for string, iterators, references, and pointers to a container remain valid after a swap, still pointing to the elements from before the swap. However, for string, they all become invalid.

Regarding swap: To be continued Regarding forward_list: To be continued Regarding string: To be continued

About Vector Expansion

vector objects are stored contiguously. The standard library implementers have adopted strategies to reduce the number of times container space is reallocated. When new memory space must be acquired, the implementations of vector and string typically allocate more memory than immediately needed. With this strategy, their expansion is usually much faster than that of list and deque.

It’s important to note the difference between capacity and size: The size of a container refers to the number of elements it currently holds, while capacity is the maximum number of elements it can hold without allocating new memory space.

Container Adapters

In addition to sequential containers, the standard library also defines three sequential container adapters: stack, queue, and priority_queue. An adapter is a general concept in the standard library. Containers, functions, and iterators all have adapters. Essentially, an adapter is a mechanism that makes one entity behave like another.

For example, the stack adapter takes an existing container type and makes it behave like a stack. It can be understood as a stack class implemented using a certain sequential container, abstracting operations like pop() and push().

The difference between priority_queue and queue is that priority_queue can establish priorities for the elements in the queue. For specific operational details of stack, queue, and priority_queue, refer to the relevant C++ API.

#C++