STL - Vectors

Tags:  cpp  stl  containers 

C++ 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/middle is O(N)
DeletionDeletion from the end is O(1)
Deletion at the start/middle is O(N)

Declaration: vector<Type> v1;

Iterators

Element access

Size functions

Modifiers

Ways to initialize a vector

1. Declare and .push_back() each element:

vector<int> v1;
v1.push_back(10);
v1.push_back(20);
// { 10, 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 };
// { 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);
// { 10, 20, 30 }


// 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);
printVector(v1);
// { 12, 12, 12, 0, 0 }


vector<int> v2(7);
// fill_n(start_pos, count, val)
fill_n(v2.begin() + 3, 2, 4);
printVector(v2);
//  { 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 }

fill() vs memset() in C++

Criteriamemset()fill()
Signaturememset(void *obj, int ch, size_t N)<Itr,T> void fill(Itr first, Itr last, const T& val)
MeaningSets N bytes of obj to chAssigns the value val to all elements in range [first, last)
ValuesUsed when ALL bytes of element can be the same byte, such as 0 or -1Accepts all valid values of the data-type
Data-typeMostly used with int or char arraysPortable for vectors of various data types
ExecutionWorks at the byte level, setting each byte present to the given byte value. Thus no type-safety per elementHas an underlying loop initializing each element to the given value. So type-safe assignment
Import#include <cstring>#include <vector>
SpeedIt’s slightly faster as it’s written in assemblerBasic looping, so slightly slower than memset
Examplememset(arr, -1, n * sizeof(int));fill(arr.begin(), arr.end(), 42);

Below picture would illustrate why memset makes sense for values 0 or -1 when we want to set a certain number of bytes as the same byte-value

int value representation for memset

Initializing a 2D vector

// Creates 2D vector of 3 rows with 4 columns per row
// and all row values initialized to -1
vector<vector<int>> mat(3, vector<int>(4, -1));

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

void printVector (vector<int> &v) {
    if (v.empty()) {
        cout << "Vector is empty";


    } else {
        cout << "{ ";
        for (int &num : v) cout << num << ", ";
        cout << "}";
    }
    cout << endl;
}


struct Student {
    int id;
    string name;
    Student(int _id, string _name) : id(_id), name(_name) {}
};


bool compareIds (Student &s1, Student &s2) {
    return (s1.id < s2.id);  // Assuming unique ids
}


void showStudents (vector<Student> &students) {
    for (auto &s : students) cout << s.id << "\t" << s.name << endl;
}


int main () {
    // Constructor as well as List Initialization
    vector<Student> v1{
        Student(104, "Sai"),
        Student{101, "Ramesh"},
        Student(102, "Pankaj"),
        Student{103, "Shyam"},
    };


    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;
}

Difference between .emplace_back() and .push_back()