STL - Vectors


Tags:  cppstlcontainers

CPP Reference: vector

Present inside the <vector> header, vectors are dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted

OperationTime
Element AccessO(1) always
InsertionInsertion at the end is O(1) on average but O(N) when resizing
Insertion at the start or middle is O(N)
DeletionDeletion from the end is O(1)
Deletion at the start or middle is O(N)

Declaration: vector<Type> v1;

Iterators

Element access

Size functions

Modifiers

Difference between .emplace_back() and .push_back()

Ways to initialize a vector

1. Declare and .push_back() each element:

vector<int> v1;
v1.push_back(10);
v1.push_back(20);

2. Specify size and value (all elements will have same value):

vector<int> v1(4, 7);
// {7, 7, 7, 7}

3. List-initialization:

vector<int> v1{ 10, 20, 30 };

4. From another array or vector via (start_pos, end_pos):

// From another array
int arr[] = { 10, 20, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v1(arr, arr + n);
// From another vector
vector<int> v2{10, 20, 30, 40, 50, 60};
vector<int> v3(v2.begin() + 2, v2.end());
// {30, 40, 50, 60}

5. Using fill() or fill_n() to set values:

vector<int> v1(5);
// fill(start_pos, end_pos, val)
fill(v1.begin(), v1.begin()+3, 12);
// {12, 12, 12, 0, 0}
vector<int> v2(7);
// fill_n(start_pos, count, val)
fill_n(v2.begin()+3, 2, 4);
// {0, 0, 0, 4, 4, 0, 0}

6. Using iota() to set values as increments:

vector<int> v1(10);
// iota(start_pos, end_pos, start_val)
iota(v1.begin()+2, v1.end()-3, 20);
// { 0, 0, 20, 21, 22, 23, 24, 0, 0, 0 }

Initialising 2D vector

vector<vector<int>> mat(3, vector<int>(4, -1));

Above line initializes a 2D matrix mat of 3 rows and 4 columns with the default value -1 at each cell

Traversal

Traversals demo
vector<int> v1{105, 48, 23, 6, 94, 52};
// Range-based for loop
cout << "{ ";
for (auto &x : v1)
{
cout << x << ", ";
}
cout << "}" << endl;
// { 105, 48, 23, 6, 94, 52, }
// for loop with iterators
cout << "{ ";
for (auto itr = v1.begin(); itr != v1.end(); itr++)
{
cout << *(itr) << ", ";
}
cout << "}" << endl;
// { 105, 48, 23, 6, 94, 52, }
// Reverse traversal: for loop with reverse iterators
cout << "{ ";
for (auto itr = v1.rbegin(); itr != v1.rend(); itr++)
{
cout << *(itr) << ", ";
}
cout << "}" << endl;
// { 52, 94, 6, 23, 48, 105, }

More functions:


Beware of vector<bool>

vector<bool> in C++ is a specialization of the standard vector container class that allows you to store a sequence of boolean values. Unlike a regular vector<T> where T can be any data type, vector<bool> doesn’t store each bool value as a full byte in memory. Instead, it utilizes bit manipulation techniques to pack multiple boolean values (typically 8) into a single byte. Due to the bit-packing optimization, operations like element access and modification are not as straightforward as with other types:

Better alternatives:


Vector of custom data-type

struct Student
{
int id;
string name;
Student(int _id, string _name) : id(_id), name(_name) {}
};
bool compareIds(Student &s1, Student &s2)
{
// Assuming unique ids
return (s1.id < s2.id);
}
void showStudents(vector<Student> &students)
{
for (auto &s : students)
{
cout << s.id << "\t" << s.name << endl;
}
}
int main()
{
vector<Student> v1{
// List-initialization
Student{101, "Ramesh"},
Student{103, "Shyam"},
// Constructing Object
Student(102, "Pankaj"),
Student(104, "Sai")
};
showStudents(v1);
// 101 Ramesh
// 103 Shyam
// 102 Pankaj
// 104 Sai
sort(v1.begin(), v1.end(), compareIds);
showStudents(v1);
// 101 Ramesh
// 102 Pankaj
// 103 Shyam
// 104 Sai
return 0;
}