Lære Sequence Containers: vector, deque, list

Understanding the differences between std::vector, std::deque, and std::list is essential for choosing the best container for your application's needs. These are the primary sequence containers in the C++ Standard Library, each with distinct memory layouts, access patterns, and typical use cases.

Vector

std::vector stores elements in a contiguous memory block, which allows for fast random access and efficient use of CPU cache. Accessing an element by index is a constant-time operation. However, inserting or deleting elements in the middle or at the beginning requires shifting all subsequent elements, making these operations potentially costly. Appending elements at the end is generally fast, except when the internal array needs to be resized;

main.cpp


              12345678910
            
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v = {1, 2, 3};
    v.push_back(4);  // Fast append
    v.insert(v.begin() + 1, 10);  // Slower insert (shift elements)
    std::cout << v[1];  // Fast random access
}

Deque

std::deque (double-ended queue) also provides fast random access, but its internal structure is a sequence of memory blocks rather than a single contiguous block. This design allows efficient insertion and deletion at both the front and back. However, random access is slightly slower than std::vector due to the segmented memory layout. Insertions or deletions in the middle are still relatively expensive;

main.cpp


              123456789
            
#include <deque>
#include <iostream>
int main()
{
    std::deque<int> d = {1, 2, 3};
    d.push_front(0);  // Fast front insertion
    d.push_back(4);   // Fast back insertion
    std::cout << d[2];  // Random access (slightly slower)
}

List

std::list is a doubly-linked list, where each element is stored in a separate node with pointers to the previous and next elements. This structure allows constant-time insertion and deletion anywhere in the list, provided you already have an iterator to the position. However, random access is not supported; you must traverse the list from the beginning or end, which is a linear-time operation. The memory overhead is also higher due to the storage of pointers.

main.cpp


              1234567891011
            
#include <list>
#include <iostream>

int main()
{
    std::list<int> l = {1, 2, 3};
    auto it = ++l.begin();
    l.insert(it, 10);  // Fast insert at known position
    l.erase(--l.end());  // Fast erase at known position
    for (int x : l) std::cout << x << ' ';  // Linear traversal
}

Choosing the right sequence container depends on your application's performance needs and typical access patterns. The code sample above demonstrates the practical consequences of each container's internal structure.

Note

Always consider the trade-offs between memory overhead, cache efficiency, and operation complexity when selecting a sequence container

Var alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 1

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Awesome!

Completion rate improved to 6.67

Stryg for at vise menuen

Vector

main.cpp


              12345678910
            
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v = {1, 2, 3};
    v.push_back(4);  // Fast append
    v.insert(v.begin() + 1, 10);  // Slower insert (shift elements)
    std::cout << v[1];  // Fast random access
}

Deque

main.cpp


              123456789
            
#include <deque>
#include <iostream>
int main()
{
    std::deque<int> d = {1, 2, 3};
    d.push_front(0);  // Fast front insertion
    d.push_back(4);   // Fast back insertion
    std::cout << d[2];  // Random access (slightly slower)
}

List

main.cpp


              1234567891011
            
#include <list>
#include <iostream>

int main()
{
    std::list<int> l = {1, 2, 3};
    auto it = ++l.begin();
    l.insert(it, 10);  // Fast insert at known position
    l.erase(--l.end());  // Fast erase at known position
    for (int x : l) std::cout << x << ' ';  // Linear traversal
}

Note

Always consider the trade-offs between memory overhead, cache efficiency, and operation complexity when selecting a sequence container

Var alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 1