List and Vector Comparisions in C++

In C++, both list and vector are container classes provided by the Standard Template Library (STL). However, they differ in several key aspects, such as their underlying data structures, performance characteristics, and use cases. Here’s a comparison:

Underlying Data Structure

vector: Implemented as a dynamic array. It stores elements in a contiguous memory block, similar to an array.

list: Implemented as a doubly linked list. Each element is stored in a separate node, and each node contains pointers to the next and previous nodes.

Memory Allocation

vector: Allocates memory contiguously. When the size exceeds capacity, a vector doubles its size, reallocating memory and copying the elements to a new location. This may involve some overhead when resizing.

list: Allocates memory for each element separately. No reallocation is required when adding elements, but each node has additional memory overhead due to the pointers to the next and previous nodes.

Access Time

vector: Provides constant time (O(1)) random access to elements, as the elements are stored contiguously in memory.

list: Provides linear time (O(n)) random access, as you need to traverse the list to access elements.

Insertion and Deletion

vector

Inserting or deleting elements at the end is fast (amortized O(1)).

Inserting or deleting elements anywhere else (e.g., at the beginning or middle) requires shifting elements, which takes linear time (O(n)).

list

Inserting or deleting elements anywhere is fast (O(1)) if you already have an iterator to the location (i.e., no need for shifting).

However, you need to traverse the list to reach the desired position, which can make the overall operation O(n).

Iterator Invalidation

vector: When elements are inserted or removed, iterators to elements after the insertion or removal point are invalidated due to potential memory reallocation and shifting of elements.

list: Insertion or deletion of elements does not invalidate iterators to other elements, as the memory layout remains unaffected.

When to Use

vector

• When you need fast random access.
• When you expect to add or remove elements primarily at the end of the container.
• When cache performance is important (because elements are contiguous in memory).

list

• When you need to insert or remove elements frequently at arbitrary positions.
• When you don’t need fast random access, and iterating through the container is sufficient.
• When constant-time insertion and deletion in the middle of the container is needed.

Sample code of using std::vector

std::vector: We use indexing to access elements and push_back to add elements at the end. Inserting at specific positions (vec.insert) or deleting (vec.erase) elements takes linear time (O(n)) due to shifting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <vector>
 
int main() {
    // Create a vector of integers
    std::vector<int> vec;
 
    // Add elements to the vector
    vec.push_back(1); // Inserting at the end
    vec.push_back(2);
    vec.push_back(3);
 
    // Access elements using index
    std::cout << "Vector elements: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " "; // Random access is O(1)
    }
    std::cout << std::endl;
 
    // Insert element at a specific position
    vec.insert(vec.begin() + 1, 10); // Insertion at middle, O(n)
 
    // Output the modified vector
    std::cout << "After insertion: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
 
    // Delete an element
    vec.erase(vec.begin() + 2); // Erasing at specific position, O(n)
 
    // Output the modified vector
    std::cout << "After deletion: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

#include <iostream>
#include <vector>

int main() {
    // Create a vector of integers
    std::vector<int> vec;

    // Add elements to the vector
    vec.push_back(1); // Inserting at the end
    vec.push_back(2);
    vec.push_back(3);

    // Access elements using index
    std::cout << "Vector elements: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " "; // Random access is O(1)
    }
    std::cout << std::endl;

    // Insert element at a specific position
    vec.insert(vec.begin() + 1, 10); // Insertion at middle, O(n)

    // Output the modified vector
    std::cout << "After insertion: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    // Delete an element
    vec.erase(vec.begin() + 2); // Erasing at specific position, O(n)

    // Output the modified vector
    std::cout << "After deletion: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Sample code of using std::list

std::list: There is no random access, so we use an iterator to navigate to the desired position. Once the iterator is positioned, insertions (lst.insert) and deletions (lst.erase) are constant time (O(1)) operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <list>
 
int main() {
    // Create a list of integers
    std::list<int> lst;
 
    // Add elements to the list
    lst.push_back(1); // Inserting at the end
    lst.push_back(2);
    lst.push_back(3);
 
    // Output the list elements
    std::cout << "List elements: ";
    for (const auto& elem : lst) {
        std::cout << elem << " "; // Traversing is O(n)
    }
    std::cout << std::endl;
 
    // Insert element at a specific position
    auto it = lst.begin();
    std::advance(it, 1); // Move iterator to the second position
    lst.insert(it, 10); // Insertion at any position, O(1) once iterator is there
 
    // Output the modified list
    std::cout << "After insertion: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    // Delete an element
    it = lst.begin();
    std::advance(it, 2); // Move iterator to the third position
    lst.erase(it); // Deletion at any position, O(1) once iterator is there
 
    // Output the modified list
    std::cout << "After deletion: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

#include <iostream>
#include <list>

int main() {
    // Create a list of integers
    std::list<int> lst;

    // Add elements to the list
    lst.push_back(1); // Inserting at the end
    lst.push_back(2);
    lst.push_back(3);

    // Output the list elements
    std::cout << "List elements: ";
    for (const auto& elem : lst) {
        std::cout << elem << " "; // Traversing is O(n)
    }
    std::cout << std::endl;

    // Insert element at a specific position
    auto it = lst.begin();
    std::advance(it, 1); // Move iterator to the second position
    lst.insert(it, 10); // Insertion at any position, O(1) once iterator is there

    // Output the modified list
    std::cout << "After insertion: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Delete an element
    it = lst.begin();
    std::advance(it, 2); // Move iterator to the third position
    lst.erase(it); // Deletion at any position, O(1) once iterator is there

    // Output the modified list
    std::cout << "After deletion: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Summary

vector: Better for random access, efficient resizing at the end, and cache performance.

list: Better for frequent insertions and deletions in the middle or beginning of the container without random access needs.

vector is more efficient for random access, while list excels at constant-time insertions and deletions.

–EOF (The Ultimate Computing & Technology Blog) —