Road to C++ Programmer #9 - Sequence Containers

C++DSA

Last Edited: 9/27/2024

The blog post introduces the sequence containers like arrays, vectors, and lists in C++.

C++ Seq Con

A container is an object that stores multiple objects, implemented as class templates with various useful methods. In this article, we will cover some sequence containers, whose elements are stored sequentially.

Standard Arrays

Standard arrays differ from the normal arrays we're used to in that they are class templates with access to methods like size(), begin(), end(), empty(), at(), and the [] operator.

#include <array>
 
using namespace std;
 
int main() {
    // std::array<dtype, num_elements>
    array<int, 3> arr = {1, 3, 2};
 
    cout << "Size of arr: ";
    cout << arr.size() << endl;
 
    cout << "arr[2]: ";
    cout << arr[2] << endl; // arr.at(2) alternatively
 
    cout << "It starts with " << arr.front();
    cout << " and ends with " << arr.back() << "." << endl;
 
    array<int, 3>arr2;
    arr2.fill(4);
    arr.swap(arr2);
    cout << "arr[0] is now" <<arr.at(0) << endl;
 
    return 0;
}

The actual data is accessible using the data() method, and it is stored in a contiguous space on the stack. When iterating over and working with the elements of a standard array, it is recommended to use an iterator object, which is a reference object set up for all containers to abstract away the details of how to iterate over the elements, regardless of how the data is stored.

int main () {
    array<int, 3>arr = {1, 3, 2};
    
    cout << "arr: ";
    for (array<int, 3>::iterator i = arr.begin(); i != arr.end(); i++) {
        cout << " " << i;
    }
    cout << endl;
 
    // Alternative 1: Auto
    cout << "arr: ";
    for (auto i = arr.begin(); i != arr.end(); i++) {
        cout << " " << i;
    }
    cout << endl;
 
    // Alternative 2: Ranged For-Loop
    cout << "arr: ";
    for (auto i : arr) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
}

The auto keyword can automatically identify the iterator, shortening the syntax. If you are going through all the elements, a ranged for-loop is convenient. There are already multiple container operations available, such as sort(c.begin(), c.end()), which is a sorting function provided in the <algorithm> package.

Vectors

Standard arrays are useful, but their size needs to be specified and fixed. For more flexibility, you can use vectors, which utilize dynamic arrays instead of static arrays. Vectors are similar to the ArrayList discussed in the article Road to C Programmer #8 - Linked List, where a dynamically allocated contiguous array is used for faster indexing, but vectors come with more functionalities.

#include <vector>
 
int main () {
    vector<int> vec;
    vec.assign(5, 1); // Fill 1 for 5 times
    vec.push_back(5); // Push 5 at the back
    vec.insert(vec.begin(), 5); // Insert 5 at the beginning
    vec.pop_back(); // Remove the last element
    vec.resize(10); // Resize vec to store 10 ints
    vec.shrink_to_fit(); // Resize to fit all the elements (to 6)
    cout << vec[0] << endl; 
 
    cout << "vec: ";
    for (auto i : vec) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
}

Since vectors use dynamically allocated arrays, we can access member functions like resize() and shrink_to_fit(). As discussed in the previous article on arrays vs linked lists, contiguous memory is efficient for indexing, though insertion and deletion may require more shfits and reallocation to a different memory space in the heap.

Lists

The standard list provided by C++ is a class template for a doubly-linked list, where elements store pointers to the preceding and succeeding nodes (a singly-linked list is implemented as forward_list).

#include <list>
 
int main () {
    list<int> li;
    li.push_front(10); // Add node to the front
    li.push_back(5); // Add node to the back
    li.insert(li.begin(), 1); // Inser 1 at the beginning
    li.sort();
 
    cout << "li: ";
    for (auto i : li) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
};

Since there is no shifting of memory or reallocation of nodes, insertion and deletion are typically faster. However, you cannot use the [] operator, and it is generally slower to index elements and count the size, as the memory is not stored contiguously and there is a higher chance of cache misses.

Deque

We can see the benefits of both vectors and lists, so how can we combine them? The deque achieves this by combining vectors and lists, where individual nodes are small contiguous arrays. This increases the chance of a cache hit while minimizing the shifts and reallocations during insertion and deletion.

#include <deque>
 
int main () {
    deque<int> deq;
    deq.assign(5, 1); // Fill 1 for 5 times
    deq.push_back(5); // Push 5 at the back
    deq.insert(vec.begin(), 5); // Insert 5 at the beginning
    deq.pop_back(); // Remove the last element
    deq.resize(10); // Resize vec to store 10 ints
    deq.shrink_to_fit(); // Resize to fit all the elements (to 6)
    cout << deq[0] << endl;
 
    cout << "vec: ";
    for (auto i : deq) {
        cout << " " << i;
    }
    cout << endl;
 
    return 0;
}

The supported operations are nearly the same as those for vectors, except that a deque allows insertion and deletion from both the front and the back. This means the [] operator is available, even though a deque does not guarantee contiguous memory. The deque tracks a table mapping index numbers to their locations, which is convenient but generally slower than vectors and more costly in terms of memory usage.

Conclusion

We can observe that arrays, vectors, lists, and deques each have unique advantages and disadvantages. Arrays are efficient when the size is known but require many shifts during insertion and deletion. Vectors are more flexible but still face the same issues as arrays in terms of shifting and may require memory reallocation. Lists avoid shifting and reallocation during insertion and deletion, but indexing and determining the size are less convenient and slower because they require traversal. Deques perform relatively well across the board but tend to use more memory.

Understanding these characteristics is essential for making decisions about which sequence container to use. However, it's always important to measure performance when choosing one over the other. Fortunately, the sequence containers have nearly identical interfaces, making it easier to test different solutions with minimal changes to the code. (Here, we can see the benefits of classes and class templates.) In the next article, we will continue discussing containers, but of a different kind.

Resources

Back to Top↑