STL - Vectors

Tags: cpp stl containers 

Contents:

Overview

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

CPP Reference: vector

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

More methods:

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 }

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

Vector Traversals
vector<int> v1{105, 48, 23, 6, 94, 52};


// Range-based for loop
cout << "{ ";
for (const auto &x : v1) cout << x << ", ";
cout << "}\n";
// { 105, 48, 23, 6, 94, 52, }


// For-loop with iterators
cout << "{ ";
for (auto itr = v1.begin(); itr != v1.end(); itr++) cout << *(itr) << ", ";
cout << "}\n";
// { 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 << "}\n";
// { 52, 94, 6, 23, 48, 105, }

Vector of custom data-type

void printVector (const vector<int> &v) {
    if (v.empty()) {
        cout << "Vector is empty\n";
        return;
    }
    cout << "{ ";
    for (const int &num : v) cout << num << ", ";
    cout << "}\n";
}


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


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


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


int main () {
    cout << "======== PROGRAM START ========\n";
    auto start = chrono::steady_clock::now();
    /* =========================================================================== */
    // Init Vector of objectsh (showing various object initialization ways):
    vector<Student> v1{
        Student(104, "Sai"),
        Student{102, "Ramesh"},
        Student(105, "Pankaj"),
        Student{101, "Nilesh"},
        {103, "Jatin"},
    };
    showStudents(v1);
    /*
        104  Sai
        102  Ramesh
        105  Pankaj
        101  Nilesh
        103  Jatin
    */


    sort(v1.begin(), v1.end(), compareIds);
    cout << "After Sorting:\n";
    showStudents(v1);
    /*
        101  Nilesh
        102  Ramesh
        103  Jatin
        104  Sai
        105  Pankaj
    */
}

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:

Some better alternatives to vector<bool> are:

Difference between .emplace_back() and .push_back()

struct Student {
    string name;
    int roll;
    float marks;
    Student(string _name, int _roll, float _marks) : name(_name), roll(_roll), marks(_marks) {}
};


int main () {
    vector<pair<char, int>> v1;
    v1.emplace_back('x', 12);
    v1.push_back({'y', 15});
    v1.push_back(make_pair('z', 17));
    for (const auto &p : v1) cout << p.first << ", " << p.second << "\n";
    // x, 12
    // y, 15
    // z, 17


    vector<Student> students;
    students.push_back(Student("Ram", 101, 87.25));
    students.emplace_back("Jack", 102, 65.81);
    students.push_back(Student{"Shyam", 103, 75.34});
    students.emplace_back(Student{"John", 104, 65.32});
    students.emplace_back(Student("Joe", 105, 35.26));
    for (const Student &st : students) {
        cout << st.roll << ". " << st.name << " got " << st.marks << "\n";
    }
    // 101. Ram got 87.25
    // 102. Jack got 65.81
    // 103. Shyam got 75.34
    // 104. John got 65.32
    // 105. Joe got 35.26
}

Difference between memset() and fill()

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

Further Learning:

Watch this video by Cherno for optimal memory and performant usage of vector with minimal resizing or copies or moves.