Differences between Vector and List in C++

In this article, you will learn about the difference between Vector and List in C++. But before discussing the differences, you must know about the Vector and List.

What is Vector in C++?

In C++, a vector is a dynamic array-like container that can store a collection of elements of the same data type. Unlike arrays, vectors can grow or shrink in size during runtime. Vectors are part of the C++ Standard Template Library (STL) and are included in 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:

We can also specify an initial size for the vector by passing an integer argument to the corresponding constructor:

What is List in C++?

In C++, a list is a container that stores a collection of elements, similar to a vector or an array. However, unlike vectors and arrays, lists are implemented as doubly-linked lists, where each element is linked to both the previous and the next elements in the list. It allows for efficient insertion and deletion of elements at any position in the list but comes at the cost of slower random access to elements compared to vectors or arrays. Lists allocate memory efficiently since each element is stored as a separate node and can be dynamically resized without the need for 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:

Basic C++ code snippet that demonstrates the differences between a vector and a list:

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 code creates a vector and a list and inserts 1 million elements into each container using push_back(). After that, it randomly accesses 1000 elements in each container and measures the time taken for each operation. Finally, it sorts the elements in the vector using the sort() function and the elements in the list using the sort() member function and measures the time taken for each operation.

The results of this code will depend on the specific machine and environment where it is executed, but in general, it should illustrate some of the performance differences between vectors and lists for different types of operations.