Differences Between Vector And List In C++

In this tutorial, we will explore the variances between Vector and List in C++. However, prior to delving into the disparities, it is essential to understand the concepts of Vector and List.

What is Vector in C++?

In C++, a vector represents a resizable array-based container capable of holding a group of elements sharing a common data type. In contrast to traditional arrays, vectors have the flexibility to expand or contract in size dynamically while the program is running. Vectors are a fundamental component of the C++ Standard Template Library (STL) and are imported using the <vector> header file.

Some uses of vectors in C++:

• ✅ Storing collections of elements: Vectors can store collections of elements of the same data type, such as integers, floating-point numbers , or strings .
• ✅ Dynamically resizing containers: Vectors can grow or shrink in size during runtime, making them useful when you don't know the size of the collection beforehand or when the size of the collection may change during runtime.
• ✅ Fast random access: Elements in a vector are stored in contiguous memory locations, making it possible to access elements using their index in constant time.
• ✅ Efficient memory allocation: Vectors allocate memory efficiently, making it possible to add or remove elements from the end of the vector with minimal overhead.
• ✅ Interoperability with other libraries: Vectors are part of the C++ Standard Template Library , which means that they can be used in conjunction with other STL containers, algorithms, and iterators.

Syntax:

The basic syntax of declaring a vector:

#include <vector> // include the vector header file
std::vector<DataType>vectorName; // declare a vector of a specific data type

We can also define a starting size for the vector by providing an integer parameter to the relevant constructor:

std::vector<int>myVector(10); // declare a vector of 10 integers.

What is List in C++?

In C++, a list serves as a container that holds a group of elements, much like a vector or an array. Unlike vectors and arrays, lists are constructed as doubly-linked lists, where every element is connected to both the preceding and succeeding elements in the list. This structure enables swift insertion and removal of elements at any point in the list. However, it results in slower access to elements at random positions compared to vectors or arrays. Lists manage memory effectively by storing each element as an individual node, allowing for dynamic resizing without requiring contiguous memory allocation.

Key differences between Vector and List

Vector and list are container classes that allow the user to store a collection of elements, and there are some differences between the two, which are as follows:

• ✅ Implementation: Vectors are implemented as dynamic arrays , which means that the elements are stored in contiguous memory locations . In contrast, Lists are implemented as doubly-linked lists , meaning that the elements are not stored in contiguous memory locations but are linked by pointers.
• ✅ Accessing Elements: Since vectors store their elements in contiguous memory locations, they allow for random access of elements using the operator . On the other hand, Lists do not allow for random access and require iterating through the list to access elements.
• ✅ Insertion and Deletion Insertion and deletion of elements in a vector can be expensive if done in the middle or front of the vector, as it requires shifting all elements after the insertion or deletion point. In contrast, the insertion and deletion of elements in a list are relatively cheap, as they only require updating the pointers of adjacent elements.
• ✅ Memory allocation: Vectors are typically implemented as contiguous arrays, which means that they allocate a single block of memory for all their elements. On the other hand, Lists are typically implemented as linked lists , which means that they allocate individual memory blocks for each element. It can affect performance, as allocating and deallocating memory can be expensive.
• ✅ Iterators: Both vectors and lists support iterators, but the behavior of the iterators is different. Vector iterators behave like pointers to the elements in the vector, and they support random access (i.e., you can access any element in the vector directly. On the other hand, List iterators behave like pointers to nodes in the linked list, and they support bidirectional access (i.e., you can traverse the list in both directions, but you cannot access elements directly by index).
• ✅ Memory Overhead: Vectors have a higher memory overhead than lists because they need to store extra information, such as the capacity and the size of the vector, which is not required for lists.
• ✅ Cache Performance: Due to their contiguous memory layout, vectors tend to have better cache performance than lists because adjacent elements are more likely to be stored in the same cache line, which reduces cache misses and improves performance. In contrast, because lists are implemented as nodes with pointers, each element in a list may be stored in a different location in memory, which can result in more cache misses and slower performance.
• ✅ Sorting: Vectors can be sorted using the sort function in the <algorithm> header , which uses a variant of the quicksort algorithm, while lists do not have a built-in sorting function and need to be sorted manually using a custom comparator function.
• ✅ Copying: Copying a vector involves copying all the elements in the vector to a new block of memory, while copying a list involves copying the nodes and their pointers to a new list. It can have different performance characteristics depending on the size of the list and the efficiency of the memory allocator.

Example:

Below is a simple C++ code snippet showcasing the variances between a vector and a list:

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

int main() {
    // Creating a vector and a list
    std::vector<int> myVector = {1, 2, 3, 4, 5};
    std::list<int> myList = {1, 2, 3, 4, 5};

    // Accessing elements in a vector
    for (int i = 0; i < myVector.size(); ++i) {
        std::cout << "Vector Element at index " << i << ": " << myVector[i] << std::endl;
    }

    // Accessing elements in a list
    int index = 0;
    for (const auto& elem : myList) {
        std::cout << "List Element at index " << index << ": " << elem << std::endl;
        index++;
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <chrono>
#include <algorithm>
using namespace std;
using namespace chrono;
int main() {
    // Testing vector vs. list insertion performance
    vector<int> v;
    list<int> l;
    // Inserting 1 million elements into a vector
    auto start = high_resolution_clock::now();
    for (int i = 0; i< 1000000; i++) {
v.push_back(i);
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);
cout<< "Time taken by vector for insertion: " <<duration.count() << "ms" <<endl;
    // Inserting 1 million elements into a list
    start = high_resolution_clock::now();
    for (int i = 0; i< 1000000; i++) {
l.push_back(i);
    }
    stop = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(stop - start);
cout<< "Time taken by list for insertion: " <<duration.count() << "ms" <<endl;
    // Accessing elements randomly in a vector
    start = high_resolution_clock::now();
    for (int i = 0; i< 1000; i++) {
        int index = rand() % v.size();
        int value = v[index];
    }
    stop = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(stop - start);
cout<< "Time taken by vector for random access: " <<duration.count() << "ms" <<endl;
    // Accessing elements randomly in a list
    start = high_resolution_clock::now();
    for (int i = 0; i< 1000; i++) {
        int index = rand() % l.size();
        auto it = l.begin();
        advance(it, index);
        int value = *it;
    }
    stop = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(stop - start);
cout<< "Time taken by list for random access: " <<duration.count() << "ms" <<endl;
 
    // Sorting a vector
    start = high_resolution_clock::now();
    sort(v.begin(), v.end());
    stop = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(stop - start);
cout<< "Time taken by vector for sorting: " <<duration.count() << "ms" <<endl;
    // Sorting a list
    start = high_resolution_clock::now();
l.sort();
    stop = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(stop - start);
cout<< "Time taken by list for sorting: " <<duration.count() << "ms" <<endl;
 
    return 0;
}

Output:

Time taken by vector for insertion:  33ms
Time taken by list for insertion: 131ms
Time taken by vector for random access: 0ms
Time taken by list for random access: 3163ms
Time taken by vector for sorting: 346ms
Time taken by list for sorting: 704ms

Explanation:

This script generates a vector and a linked list, then adds one million items to each using the push_back method. Subsequently, it randomly retrieves 1000 items from both containers, recording the duration of each operation. Lastly, it arranges the items in the vector employing the sort function and in the linked list using the sort member function, measuring the time taken for each process.

The outcome of executing this code will vary based on the particular machine and setup, yet it is expected to demonstrate the performance differentials between vectors and lists for various kinds of operations.