C++ vector
Published:
This is a quick note for the Vector implemented in C++ STL library.
C++ STL Vector
std::vector is very common in coding problems, and it is fairly useful when I am writing small-scale homemade simulation programs. I always forget the correct format of vector interfaces, so writting a note might be a good way helping me to memorize and recall of the vector usage.
The following content is refering from https://www.cplusplus.com/reference/vector/vector/.
Vectors are sequence containers representing arrays that can change in size. Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.
Constructor
Default
// Initialize an empty vector of ints
std::vector<int> first;
Fill
// four ints with value 100
std::vector<int> second (4,100);
Range
// Copies second
std::vector<int> third (second.begin(),second.end());
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
Copy
// Copies third
std::vector<int> fourth (third);
Initializer
// Using initializer
std::vector<int> fifth{1, 2, 3};
Iterator
Begin() and end()
// vector::begin/end
#include <iostream>
#include <vector>
int main ()
{
std::vector<int> myvector;
for (int i=1; i<=5; i++) myvector.push_back(i);
std::cout << "myvector contains:";
for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
output:
myvector contains: 1 2 3 4 5
Capacity
Size()
vector<int> a(5, 20);
// 20
int s = a.size();
Capacity()
vector<int> a(5, 20);
// bigger than 20
int s = a.capacity();
Empty()
vector<int> a(5, 20);
// false
bool p = a.empty();
Element access
Operator[]
vector<int> a(5, 20);
// 20
int s = a[2];
Front() and Back()
vector<int> a{1, 2, 3};
// 1
int s = a.front();
// 3
int p = a.back();
Modifiers
Assign()
Time complexity: O(n)
// vector assign
#include <iostream>
#include <vector>
int main ()
{
std::vector<int> first;
std::vector<int> second;
std::vector<int> third;
first.assign (7,100); // 7 ints with a value of 100
std::vector<int>::iterator it;
it=first.begin()+1;
second.assign (it,first.end()-1); // the 5 central values of first
int myints[] = {1776,7,4};
third.assign (myints,myints+3); // assigning from array.
std::cout << "Size of first: " << int (first.size()) << '\n';
std::cout << "Size of second: " << int (second.size()) << '\n';
std::cout << "Size of third: " << int (third.size()) << '\n';
return 0;
}
Push_back() and pop_back()
Time complexity: O(1)
They are all in-place operation and return void.
Insert()
Time complexity: O(n) on average
// inserting into a vector
#include <iostream>
#include <vector>
int main ()
{
std::vector<int> myvector (3,100);
std::vector<int>::iterator it;
// insert one 300
it = myvector.begin();
it = myvector.insert ( it , 200 );
// insert two 300
myvector.insert (it,2,300);
// "it" no longer valid, get a new one:
it = myvector.begin();
// insert a slice by iterator
std::vector<int> anothervector (2,400);
myvector.insert (it+2,anothervector.begin(),anothervector.end());
// insert a slice by pointer
int myarray [] = { 501,502,503 };
myvector.insert (myvector.begin(), myarray, myarray+3);
std::cout << "myvector contains:";
for (it=myvector.begin(); it<myvector.end(); it++)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Erase()
Time complexity: O(n) on average
// erasing from vector
#include <iostream>
#include <vector>
int main ()
{
std::vector<int> myvector;
// set some values (from 1 to 10)
for (int i=1; i<=10; i++) myvector.push_back(i);
// erase the 6th element
myvector.erase (myvector.begin()+5);
// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);
std::cout << "myvector contains:";
for (unsigned i=0; i<myvector.size(); ++i)
std::cout << ' ' << myvector[i];
std::cout << '\n';
return 0;
}