Aprenda Iterators in Sequence Containers | Iterators and Containers

Deslize para mostrar o menu

Definition

Sequence containers in C++ are containers that organize elements in a strict linear sequence. The primary sequence containers are std::vector, std::deque, and std::list. Each provides its own iterator type:

std::vector and std::deque supply random access iterators, which allow direct access to any element in constant time;
std::list offers bidirectional iterators, which support movement forward and backward but not direct random access.

C++ sequence containers like std::vector, std::deque, and std::list all store elements in order, but differ in internal structure and iterator behavior. These differences affect how efficiently you can access and modify elements.

std::vector stores elements contiguously, providing fast random access. std::deque also supports random access, though with a different internal layout. std::list is a doubly linked list that supports forward and backward traversal but not random access. As a result, random access is efficient for vector and deque, while list excels at efficient insertions and removals in the middle.

main.cpp


              123456789101112131415161718192021222324252627282930
            
#include <iostream>
#include <vector>
#include <deque>
#include <list>

int main()
{
    std::vector<int> v(10, 1);
    std::deque<int> d(10, 1);
    std::list<int> l(10, 1);

    // Random access iterators
    auto v_it = v.begin() + 5;
    auto d_it = d.begin() + 5;

    std::cout << "Vector element: " << *v_it << '\n';
    std::cout << "Deque element: " << *d_it << '\n';

    // Forward-only traversal
    auto l_it = l.begin();
    for (int i = 0; i < 5; ++i) ++l_it;
    std::cout << "List element: " << *l_it << '\n';

    // Iterator distance
    std::cout << "Vector size via iterators: " << (v.end() - v.begin()) << '\n';
    std::cout << "Deque size via iterators: " << (d.end() - d.begin()) << '\n';

    // Not allowed for std::list:
    // l.end() - l.begin();
}

This code shows how iterator capabilities differ between sequence containers. std::vector and std::deque support random access, allowing iterator arithmetic and distance calculation. std::list provides only bidirectional iterators, so advancing by n steps requires a loop and iterator subtraction is not supported.

Iteration is usually fastest with std::vector, followed by std::deque, then std::list, due to contiguous storage and better cache locality. Choose std::vector for fast access and iteration, and std::list when frequent middle insertions or deletions are required and random access is unnecessary.

main.cpp


              123456789101112131415161718192021
            
#include <iostream>
#include <vector>
#include <list>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::list<int> l = {10, 20, 30, 40, 50};

    // Random access in vector
    std::cout << "Third element in vector: " << v[2] << "\n";

    // Random access in list (not allowed)
    auto it = l.begin();
    // advance iterator to third element
    std::advance(it, 2);
    std::cout << "Third element in list: " << *it << "\n";
    // l[2]; // Error: list does not support operator[]

    return 0;
}

This example shows how container choice affects element access. Accessing the third element in a std::vector is a constant-time operation using indexing, while std::list requires advancing an iterator step by step, resulting in linear-time access. This distinction matters when elements are frequently accessed by position.

As summarized in the table above, choose your container based on iterator capabilities and access patterns. Use std::vector for frequent random access and cache-friendly performance. Choose std::list when efficient insertions or deletions in the middle are required and indexed access is unnecessary. std::deque provides random access with efficient operations at both ends, offering a practical compromise. Understanding these trade-offs helps you select the right container and avoid performance pitfalls.

Note

Iterator invalidation rules vary by container. In std::vector and std::deque, insertions or deletions can invalidate iterators, especially after resizing. In std::list, only iterators to modified elements are invalidated. Always check container documentation to avoid using invalid iterators.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 3. Capítulo 1

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 3. Capítulo 1