C++
20 May 2023

Vector in C++

Vector in C++

Vector in C++

image

Keypoints

  • Vector conception and constructor/intialization
  • Vector assignment
  • Vector cpaacity and size
  • Vector inset and delete
  • Vector data access
  • Vector swap
  • Vector reserve

Vector conception and constructor

  • Vector is a dynamic and one-end array.
    • Dynamic expansion: When the number of elements exceeds the capacity of the vector, the vector will automatically copy the original vector to a new vector with a larger capacity, and then delete the original vector.
    • One-end array: The array can only be accessed from the beginning, and the end cannot be accessed.
      • v.begin(): Return the address of the first element in the vector
      • v.end(): Return the address after the last element in the vector
      • push_back(): Add an element to the end of the vector
  • Vector constructor/initilization
    • vector<T> v1;: Default constructor, create an empty vector.
    • vector(v1.begin(), v1.end());: Copy the elements of [v1.begin(), v1.end()) to the new vector
    • vector(n, elem);: Initialize the vector with n elements, and each element is elem
    • vector(const vector &vec);: Copy constructor
#include <iostream>
#include <vector>
using namespace std;

void test01(){
    // Default constructor
    vector<int> v1; 
    for (int i = 0; i < 10; i++){
        v1.push_back(i);
    }
    printVector(v1); // 0 1 2 3 4 5 6 7 8 9

    // Range constructor
    vector<int> v2(v1.begin(), v1.end());
    printVector(v2); // 0 1 2 3 4 5 6 7 8 9

    // n elements with value elem
    vector<int> v3(10, 100);
    printVector(v3); // 100 100 100 100 100 100 100 100 100 100

    // Copy constructor, usually used 
    vector<int> v4(v1);
    printVector(v4); // 0 1 2 3 4 5 6 7 8 9
}

void printVector(vector<int> &v){
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}

int main(){
    test01();
    return 0;
}

Vector assignment

  • =: Assign the vector on the right to the vector on the left
  • assign(beg, end): Assign the elements of [beg, end) to the vector
  • assign(n, elem): Assign n elements with value elem to the vector
#include <iostream>
#include <vector>
using namespace std;

void test01(){
    vector<int> v1;
    for (int i = 0; i < 10; i++){
        v1.push_back(i);
    }
    printVector(v1); // 0 1 2 3 4 5 6 7 8 9

    vector<int> v2 = v1;
    printVector(v2); // 0 1 2 3 4 5 6 7 8 9

    vector<int> v3;
    v3.assign(v1.begin(), v1.end());    // [v1.begin(), v1.end())
    printVector(v3); // 0 1 2 3 4 5 6 7 8 9

    vector<int> v4;
    v4.assign(10, 100);
    printVector(v4);
}

printVector(vector<int> &v){
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}

int main(){
    test01();
    return 0;
}

Vector capacity and size

  • empty(): Determine whether the vector is empty
  • capacity(): Return the capacity of the vector
  • size(): Return the number of elements in the vector. capacity >= size
  • resize(int num): Resize the size of the vector to num. If the size is expanded, the new element is initialized to 0. If the size is reduced, the element is deleted from the end of the vector.
  • resize(int num, elem): Resize the size of the vector to num. If the size is expanded, the new element is initialized to elem.
#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v){
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}

void test01(){
    vector<int> v1;
    for (int i = 0; i < 10; i++){
        v1.push_back(i);
    }
    printVector(v1); // 0 1 2 3 4 5 6 7 8 9

    if (v1.empty()){
        cout << "v1 is empty" << endl;
    }
    else{
        cout << "v1 is not empty" << endl;
        cout << "v1's capacity: " << v1.capacity() << endl; // 13
        cout << "v1's size: " << v1.size() << endl; // 10
    }

    v1.resize(15);
    printVector(v1); // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0

    v1.resize(18, 100);
    printVector(v1); // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 100 100 100

    v1.resize(5);
    printVector(v1); // 0 1 2 3 4
}

int main(){
    test01();
    return 0;
}

Vector insert and delete

  • push_back(elem): Add an element to the end of the vector
  • pop_back(): Delete the last element of the vector
  • insert(const_iterator pos, elem): Insert an element elem before the position pos in the vector and return the position of the inserted element
  • insert(const_iterator pos, int count, elem): Insert count elements with value elem before the position pos in the vector, and return the position of the first inserted element
  • erase(const_iterator pos): Delete the element at position pos in the vector and return the position of the next element
  • erase(const_iterator start, const_iterator end): Delete the elements in the range [start, end) in the vector and return the position of the next element
  • clear(): Delete all elements in the vector
#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v){
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}

void test01(){
    vector<int> v1;
    for (int i = 0; i < 10; i++){
        v1.push_back(10*i);
    }
    printVector(v1); // 0 10 20 30 40 50 60 70 80 90

    v1.pop_back();  // Delete the last element
    printVector(v1); // 0 10 20 30 40 50 60 70 80

    v1.insert(v1.begin(), 100); // Insert 100 before the first element
    printVector(v1); // 100 0 10 20 30 40 50 60 70 80

    v1.insert(v1.begin(), 2, 1000); // Insert 2 elements with value 1000 before the first element
    printVector(v1); // 1000 1000 100 0 10 20 30 40 50 60 70 80

    v1.erase(v1.begin()); // Delete the first element
    printVector(v1); // 1000 100 0 10 20 30 40 50 60 70 80

    v1.erase(v1.begin(), v1.end()); // Delete all elements
    printVector(v1); // 

    v1.clear(); // Delete all elements
}

int main(){
    test01();
    return 0;
}

Vector data access

  • at(int idx): Get the element at position idx in the vector
  • operator[]: Get the element at position idx in the vector
  • front(): Get the first element in the vector
  • back(): Get the last element in the vector
#include <iostream>
#include <vector>
using namespace std;

void test01(){
    vector<int> v1;
    for (int i = 0; i < 10; i++){
        v1.push_back(i);
    }

    for (int i = 0; i < v1.size(); i++){
        cout << v1[i] << " ";
    }   // 0 1 2 3 4 5 6 7 8 9

    for (int i = 0; i < v1.size(); i++){
        cout << v1.at(i) << " ";
    }   // 0 1 2 3 4 5 6 7 8 9

    cout << v1.front() << endl; // 0
    cout << v1.back() << endl; // 9
}

int main(){
    test01();
    return 0;
}

Vector swap

  • swap(v): Exchange the elements of the vector v with the elements of the current vector
  • With the swap function, to shrink the capacity of the vector, you can use the following code: vector<int>(v).swap(v)
#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int> &v){
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}

void test01(){
    vector<int> v1;
    for (int i = 0; i < 10; i++){
        v1.push_back(i);
    }

    printVector(v1); // 0 1 2 3 4 5 6 7 8 9

    vector<int> v2;
    for (int i = 10; i > 0; i--){
        v2.push_back(i);
    }

    printVector(v2); // 10 9 8 7 6 5 4 3 2 1

    v1.swap(v2);
    printVector(v1); // 10 9 8 7 6 5 4 3 2 1
    printVector(v2); // 0 1 2 3 4 5 6 7 8 9
}

void test02(){
    vector<int> v1;
    for (int i = 0; i < 100000; i++){
        v1.push_back(i);
    }
    cout << "v1's capacity: " << v1.capacity() << endl; // 131072
    cout << "v1's size: " << v1.size() << endl; // 100000

    v1.resize(3);
    cout << "v1's capacity: " << v1.capacity() << endl; // 131072
    cout << "v1's size: " << v1.size() << endl; // 3

    // vector<int>(v1) creates a temporary annoymous vector x, and then x is swapped with v1. x is initialized with v1, so the temporary vector capicity is the size of v1. After the swap, the temporary vector is destroyed, and v1 becomes a vector with a capacity of its original size.    
    vector<int>(v1).swap(v1);
    cout << "v1's capacity: " << v1.capacity() << endl; // 3
    cout << "v1's size: " << v1.size() << endl; // 3
}

int main(){
    test01();
    return 0;
}

Vector reserve

  • reserve(int len): Reserve a memory space of length len for the vector, the reserved memory space is not initialized or accessed. The capacity of the vector is greater than or equal to len
  • It can be used to reduce the number of vector expansions and improve the efficiency of the program
#include <iostream>
#include <vector>
using namespace std;

void test01(){
    vector<int> v1;
    int *p = NULL;
    int num = 0;
    for (int i = 0; i < 100000; i++){
        v1.push_back(i);
        if (p != &v1[0]){   // If the address of the first element of the vector changes, it means that the vector has been expanded
            p = &v1[0];
            num++;
        }
    }
    cout << "Dynamic expansion count is: " << num << endl; // Dynamic expansion count is: 17
}

void test02(){
    vector<int> v1;
    v1.reserve(100000); // Reserve a memory space of length 100000 for the vector
    int *p = NULL;
    int num = 0;
    for (int i = 0; i < 100000; i++){
        v1.push_back(i);
        if (p != &v1[0]){   
            p = &v1[0];
            num++;
        }
    }
    cout << "Dynamic expansion count is: " << num << endl; // Dynamic expansion count is: 1
}

int main(){
    test01();
    test02();
    return 0;
}
Tags:
0 comments