Vector and List are two of the most commonly used sequence containers in the C++ Standard Template Library (STL). They provide different trade-offs in terms of performance and flexibility, making them suitable for different scenarios.
Vector
A vector is a dynamic array that can grow or shrink in size. It provides random access to elements and is efficient for accessing elements by position, adding elements to the end, and removing elements from the end.
Characteristics of Vector
- Dynamic Size: Automatically resizes when elements are added or removed
- Contiguous Memory: Elements are stored in contiguous memory locations
- Random Access: Provides constant time access to any element using the index
- Efficient Back Operations: Adding or removing elements at the end is efficient
- Inefficient Middle/Front Operations: Inserting or removing elements from the middle or front requires shifting elements
Creating a Vector
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Different ways to create vectors
// Empty vector
vector<int> vec1;
// Vector with 5 elements, all initialized to 0
vector<int> vec2(5);
// Vector with 5 elements, all initialized to 42
vector<int> vec3(5, 42);
// Vector initialized with a list
vector<int> vec4 = {10, 20, 30, 40, 50};
// Vector copied from another vector
vector<int> vec5(vec4);
// Display vec4
cout << "vec4 elements: ";
for (int i = 0; i < vec4.size(); ++i) {
cout << vec4[i] << " ";
}
cout << endl;
return 0;
}Output:
vec4 elements: 10 20 30 40 50Basic Vector Operations
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> numbers;
// Adding elements
numbers.push_back(10); // Add to the end
numbers.push_back(20);
numbers.push_back(30);
// Accessing elements
cout << "First element: " << numbers[0] << endl; // Using operator[]
cout << "Second element: " << numbers.at(1) << endl; // Using at() method
cout << "Last element: " << numbers.back() << endl; // Get the last element
cout << "First element: " << numbers.front() << endl; // Get the first element
// Modifying elements
numbers[1] = 25; // Change the second element
// Size and capacity
cout << "Size: " << numbers.size() << endl; // Number of elements
cout << "Capacity: " << numbers.capacity() << endl; // Allocated space
cout << "Max size: " << numbers.max_size() << endl; // Maximum potential size
// Check if empty
cout << "Is empty? " << (numbers.empty() ? "Yes" : "No") << endl;
// Reserve capacity
numbers.reserve(10); // Reserve space for at least 10 elements
cout << "After reserve, capacity: " << numbers.capacity() << endl;
// Resize
numbers.resize(5); // Resize to 5 elements, new elements are initialized to 0
cout << "After resize, size: " << numbers.size() << endl;
// Shrink to fit
numbers.shrink_to_fit(); // Reduce capacity to fit size
cout << "After shrink_to_fit, capacity: " << numbers.capacity() << endl;
// Clear
numbers.clear(); // Remove all elements
cout << "After clear, size: " << numbers.size() << endl;
return 0;
}Iterating Through a Vector
There are several ways to iterate through a vector:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {10, 20, 30, 40, 50};
// Method 1: Using index
cout << "Using index: ";
for (size_t i = 0; i < nums.size(); ++i) {
cout << nums[i] << " ";
}
cout << endl;
// Method 2: Using iterators
cout << "Using iterators: ";
for (vector<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Method 3: Using auto with iterators (C++11)
cout << "Using auto iterators: ";
for (auto it = nums.begin(); it != nums.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Method 4: Using range-based for loop (C++11)
cout << "Using range-based for loop: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}Output:
Using index: 10 20 30 40 50
Using iterators: 10 20 30 40 50
Using auto iterators: 10 20 30 40 50
Using range-based for loop: 10 20 30 40 50Inserting and Removing Elements
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {10, 20, 30, 40, 50};
// Display original vector
cout << "Original vector: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
// Insert at the beginning
nums.insert(nums.begin(), 5);
// Insert at position 3 (4th element)
nums.insert(nums.begin() + 3, 25);
// Insert multiple copies
nums.insert(nums.begin() + 5, 2, 35); // Insert two 35s at position 5
cout << "After insertions: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
// Remove the last element
nums.pop_back();
// Remove the first element
nums.erase(nums.begin());
// Remove elements in a range (from index 2 to 4, exclusive)
nums.erase(nums.begin() + 2, nums.begin() + 4);
cout << "After removals: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}Output:
Original vector: 10 20 30 40 50
After insertions: 5 10 20 25 30 35 35 40 50
After removals: 10 20 35 35 40Vector Performance Considerations
- Fast Random Access: Accessing elements by index is O(1)
- Fast Push/Pop at the End: Adding or removing elements at the end is amortized O(1)
- Slow Insertions/Removals in the Middle: O(n) because elements need to be shifted
- Memory Reallocation: When a vector grows beyond its capacity, it allocates a new, larger block of memory and copies all elements, which can be expensive
Use Cases for Vector
- When you need random access to elements
- When most insertions and deletions are at the end
- When you need a dynamic array with automatic resizing
- When memory locality is important for performance
List
A list in C++ STL is implemented as a doubly-linked list. It allows for constant-time insertions and removals anywhere in the container, but does not provide direct random access to elements.
Characteristics of List
- Non-contiguous Memory: Elements are not stored in adjacent memory locations
- No Random Access: Cannot directly access elements by index
- Efficient Insertions/Removals: Constant time insertions and removals anywhere in the list
- Bidirectional Iteration: Can traverse forward and backward
- No Reallocation: Adding elements doesn’t cause memory reallocation
Creating a List
#include <iostream>
#include <list>
using namespace std;
int main() {
// Different ways to create lists
// Empty list
list<int> list1;
// List with 5 elements, all initialized to 0
list<int> list2(5);
// List with 5 elements, all initialized to 42
list<int> list3(5, 42);
// List initialized with a list
list<int> list4 = {10, 20, 30, 40, 50};
// List copied from another list
list<int> list5(list4);
// Display list4
cout << "list4 elements: ";
for (int num : list4) {
cout << num << " ";
}
cout << endl;
return 0;
}Output:
list4 elements: 10 20 30 40 50Basic List Operations
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> numbers;
// Adding elements
numbers.push_back(30); // Add to the end
numbers.push_front(10); // Add to the beginning
numbers.push_back(40);
numbers.push_front(5);
// Insert at a specific position
auto it = numbers.begin();
advance(it, 2); // Move iterator to the 3rd position
numbers.insert(it, 20);
// Display the list
cout << "List: ";
for (int num : numbers) {
cout << num << " ";
}
cout << endl;
// Accessing elements
cout << "First element: " << numbers.front() << endl;
cout << "Last element: " << numbers.back() << endl;
// Size
cout << "Size: " << numbers.size() << endl;
// Check if empty
cout << "Is empty? " << (numbers.empty() ? "Yes" : "No") << endl;
// Remove elements
numbers.pop_front(); // Remove from the beginning
numbers.pop_back(); // Remove from the end
cout << "After pop_front and pop_back: ";
for (int num : numbers) {
cout << num << " ";
}
cout << endl;
// Remove all occurrences of a specific value
numbers.push_back(20);
numbers.remove(20); // Remove all elements with value 20
cout << "After removing all 20s: ";
for (int num : numbers) {
cout << num << " ";
}
cout << endl;
// Remove elements that satisfy a condition
list<int> vals = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vals.remove_if([](int n) { return n % 2 == 0; }); // Remove even numbers
cout << "After removing even numbers: ";
for (int val : vals) {
cout << val << " ";
}
cout << endl;
// Clear
numbers.clear(); // Remove all elements
cout << "After clear, size: " << numbers.size() << endl;
return 0;
}List-Specific Operations
Lists support some operations that are not available for vectors:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> list1 = {10, 20, 30, 40, 20, 30, 50};
list<int> list2 = {5, 15, 25};
// Sort
list1.sort();
cout << "Sorted list1: ";
for (int num : list1) {
cout << num << " ";
}
cout << endl;
// Unique - removes consecutive duplicate elements
list1.unique();
cout << "After unique: ";
for (int num : list1) {
cout << num << " ";
}
cout << endl;
// Merge - merges two sorted lists
list2.sort(); // Both lists must be sorted
list1.merge(list2);
cout << "After merge: ";
for (int num : list1) {
cout << num << " ";
}
cout << endl;
// Splice - transfers elements from one list to another
list<int> list3 = {100, 200, 300};
list<int> list4 = {400, 500, 600};
// Transfer all elements from list4 to list3 at position 2
auto it = list3.begin();
advance(it, 2);
list3.splice(it, list4);
cout << "list3 after splice: ";
for (int num : list3) {
cout << num << " ";
}
cout << endl;
cout << "list4 after splice (should be empty): ";
for (int num : list4) {
cout << num << " ";
}
cout << endl;
// Reverse
list3.reverse();
cout << "Reversed list3: ";
for (int num : list3) {
cout << num << " ";
}
cout << endl;
return 0;
}Output:
Sorted list1: 10 20 20 30 30 40 50
After unique: 10 20 30 40 50
After merge: 5 10 15 20 25 30 40 50
list3 after splice: 100 200 400 500 600 300
list4 after splice (should be empty):
Reversed list3: 300 600 500 400 200 100Iterating Through a List
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> nums = {10, 20, 30, 40, 50};
// Method 1: Using iterators
cout << "Using iterators: ";
for (list<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Method 2: Using auto with iterators (C++11)
cout << "Using auto iterators: ";
for (auto it = nums.begin(); it != nums.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Method 3: Using range-based for loop (C++11)
cout << "Using range-based for loop: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
// Method 4: Using reverse iterators
cout << "Using reverse iterators: ";
for (auto rit = nums.rbegin(); rit != nums.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl;
return 0;
}Output:
Using iterators: 10 20 30 40 50
Using auto iterators: 10 20 30 40 50
Using range-based for loop: 10 20 30 40 50
Using reverse iterators: 50 40 30 20 10List Performance Considerations
- No Random Access: Cannot directly access elements by index
- Fast Insertions/Removals: Constant time (O(1)) insertions and removals anywhere in the list
- Slow Search: Finding an element requires traversing the list (O(n))
- More Memory Overhead: Each element requires extra memory for pointers
- Poor Cache Performance: Non-contiguous memory allocation can lead to more cache misses
Use Cases for List
- When you need frequent insertions and deletions in the middle
- When you don’t need random access
- When the order of elements matters
- When you need to splice lists together
Comparing Vector and List
Vector vs. List: Operations
| Operation | Vector | List |
|---|---|---|
| Random access | O(1) | O(n) |
| Insertion/removal at beginning | O(n) | O(1) |
| Insertion/removal at end | Amortized O(1) | O(1) |
| Insertion/removal in middle | O(n) | O(1) |
| Memory overhead | Low | High |
| Cache efficiency | High | Low |
When to Use Vector
- You need random access to elements
- You primarily add/remove elements at the end
- You need a dynamically sized array
- Memory usage and cache efficiency are important
- You want to minimize overhead
When to Use List
- You frequently insert/remove elements in the middle
- You don’t need random access
- You need to transfer elements between containers
- You need efficient splicing, sorting, and merging
- You need stable iterators (iterators to list elements remain valid after insertions/removals)
Practical Examples
Example 1: Using Vector for Numerical Computation
#include <iostream>
#include <vector>
#include <numeric> // For accumulate, inner_product
#include <algorithm> // For transform
using namespace std;
int main() {
// Create vectors for calculation
vector<double> v1 = {1.0, 2.0, 3.0, 4.0, 5.0};
vector<double> v2 = {5.0, 4.0, 3.0, 2.0, 1.0};
vector<double> result(5);
// Element-wise addition
transform(v1.begin(), v1.end(), v2.begin(), result.begin(),
[](double a, double b) { return a + b; });
cout << "Element-wise addition: ";
for (double val : result) {
cout << val << " ";
}
cout << endl;
// Dot product
double dotProduct = inner_product(v1.begin(), v1.end(), v2.begin(), 0.0);
cout << "Dot product: " << dotProduct << endl;
// Sum of elements
double sum = accumulate(v1.begin(), v1.end(), 0.0);
cout << "Sum of v1: " << sum << endl;
// Mean value
double mean = sum / v1.size();
cout << "Mean of v1: " << mean << endl;
return 0;
}Output:
Element-wise addition: 6 6 6 6 6
Dot product: 35
Sum of v1: 15
Mean of v1: 3Example 2: Using List for a To-Do List Application
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Task {
private:
string description;
bool completed;
int priority;
public:
Task(const string& desc, int prio = 1) :
description(desc), completed(false), priority(prio) {}
string getDescription() const { return description; }
bool isCompleted() const { return completed; }
int getPriority() const { return priority; }
void markCompleted() { completed = true; }
void setPriority(int prio) { priority = prio; }
friend ostream& operator<<(ostream& os, const Task& task) {
os << "[" << (task.completed ? "X" : " ") << "] "
<< "(" << task.priority << ") " << task.description;
return os;
}
};
class ToDoList {
private:
list<Task> tasks;
public:
void addTask(const Task& task) {
tasks.push_back(task);
}
void displayTasks() const {
if (tasks.empty()) {
cout << "No tasks in the list." << endl;
return;
}
cout << "To-Do List:" << endl;
int i = 1;
for (const Task& task : tasks) {
cout << i++ << ". " << task << endl;
}
}
void markTaskCompleted(int index) {
if (index <= 0 || index > tasks.size()) {
cout << "Invalid task index." << endl;
return;
}
auto it = tasks.begin();
advance(it, index - 1);
it->markCompleted();
}
void removeCompletedTasks() {
tasks.remove_if([](const Task& task) { return task.isCompleted(); });
}
void sortByPriority() {
tasks.sort([](const Task& a, const Task& b) {
return a.getPriority() > b.getPriority();
});
}
};
int main() {
ToDoList todoList;
// Add tasks
todoList.addTask(Task("Buy groceries", 2));
todoList.addTask(Task("Pay bills", 3));
todoList.addTask(Task("Call mom", 1));
todoList.addTask(Task("Work on project", 3));
cout << "Initial to-do list:" << endl;
todoList.displayTasks();
// Sort by priority
todoList.sortByPriority();
cout << "\nAfter sorting by priority:" << endl;
todoList.displayTasks();
// Mark some tasks as completed
todoList.markTaskCompleted(1);
todoList.markTaskCompleted(3);
cout << "\nAfter marking tasks as completed:" << endl;
todoList.displayTasks();
// Remove completed tasks
todoList.removeCompletedTasks();
cout << "\nAfter removing completed tasks:" << endl;
todoList.displayTasks();
return 0;
}Example 3: Combining Vector and List for a Music Playlist
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
class Song {
private:
string title;
string artist;
int duration; // in seconds
public:
Song(const string& t, const string& a, int d) :
title(t), artist(a), duration(d) {}
string getTitle() const { return title; }
string getArtist() const { return artist; }
int getDuration() const { return duration; }
friend ostream& operator<<(ostream& os, const Song& song) {
int minutes = song.duration / 60;
int seconds = song.duration % 60;
os << song.title << " - " << song.artist << " ("
<< minutes << ":" << (seconds < 10 ? "0" : "") << seconds << ")";
return os;
}
};
class MusicLibrary {
private:
vector<Song> songs; // Vector for efficient storage and lookup
public:
void addSong(const Song& song) {
songs.push_back(song);
}
void displayAllSongs() const {
cout << "Music Library (" << songs.size() << " songs):" << endl;
for (size_t i = 0; i < songs.size(); ++i) {
cout << (i + 1) << ". " << songs[i] << endl;
}
}
const Song& getSong(size_t index) const {
if (index >= songs.size()) {
throw out_of_range("Song index out of range");
}
return songs[index];
}
size_t getSize() const {
return songs.size();
}
void sortByTitle() {
sort(songs.begin(), songs.end(),
[](const Song& a, const Song& b) { return a.getTitle() < b.getTitle(); });
}
void sortByArtist() {
sort(songs.begin(), songs.end(),
[](const Song& a, const Song& b) { return a.getArtist() < b.getArtist(); });
}
};
class Playlist {
private:
string name;
list<Song> queue; // List for efficient insertions and removals
public:
Playlist(const string& n) : name(n) {}
string getName() const { return name; }
void addSong(const Song& song) {
queue.push_back(song);
}
void displayPlaylist() const {
cout << "Playlist: " << name << " (" << queue.size() << " songs)" << endl;
int i = 1;
for (const Song& song : queue) {
cout << i++ << ". " << song << endl;
}
}
void skipCurrentSong() {
if (!queue.empty()) {
cout << "Skipped: " << queue.front() << endl;
queue.pop_front();
} else {
cout << "Playlist is empty." << endl;
}
}
void addToFront(const Song& song) {
queue.push_front(song);
cout << "Added to front: " << song << endl;
}
void shuffle() {
// Convert to vector for random access
vector<Song> temp(queue.begin(), queue.end());
random_shuffle(temp.begin(), temp.end());
// Convert back to list
queue.clear();
for (const Song& song : temp) {
queue.push_back(song);
}
cout << "Playlist shuffled." << endl;
}
void clear() {
queue.clear();
cout << "Playlist cleared." << endl;
}
};
int main() {
MusicLibrary library;
// Add songs to the library
library.addSong(Song("Bohemian Rhapsody", "Queen", 354));
library.addSong(Song("Hotel California", "Eagles", 390));
library.addSong(Song("Imagine", "John Lennon", 183));
library.addSong(Song("Sweet Child O' Mine", "Guns N' Roses", 356));
library.addSong(Song("Billie Jean", "Michael Jackson", 294));
// Sort the library by title
library.sortByTitle();
cout << "Library sorted by title:" << endl;
library.displayAllSongs();
// Create a playlist
Playlist myPlaylist("My Favorites");
// Add songs to the playlist
myPlaylist.addSong(library.getSong(0)); // Billie Jean
myPlaylist.addSong(library.getSong(2)); // Hotel California
myPlaylist.addSong(library.getSong(4)); // Sweet Child O' Mine
cout << "\nInitial playlist:" << endl;
myPlaylist.displayPlaylist();
// Skip the current song
cout << "\n";
myPlaylist.skipCurrentSong();
// Add a song to the front
myPlaylist.addToFront(library.getSong(1)); // Bohemian Rhapsody
cout << "\nPlaylist after changes:" << endl;
myPlaylist.displayPlaylist();
// Shuffle the playlist
myPlaylist.shuffle();
cout << "\nShuffled playlist:" << endl;
myPlaylist.displayPlaylist();
return 0;
}Summary
Both Vector and List are powerful containers in the C++ STL, each with its own strengths and weaknesses:
-
Vector provides random access, efficient storage, and is generally faster for most operations, especially when elements are primarily accessed sequentially or added/removed at the end.
-
List excels in scenarios that require frequent insertions and removals at arbitrary positions, when the order of elements matters, and when you need to splice containers together.
The choice between Vector and List should be based on the specific requirements of your application, particularly how you plan to access and modify the data.