vector

Overview

In C/C++,  fixed size arrays can be allocated on the stack and variable size arrays are allocated on the heap. However this is inflexible and also managing  the array such as adding elements, removing elements or retrieving will require extra code.

 The standard library provides vector to address this. 

Details

vectors are basically resizable, contiguously arranged elements that can be treated as an array and pointer arithmetic can be performed. 

Syntax

The syntax is as below. Template parameter T represents the datatype to store and Alloc represents the allocator used for storage.

template < class T, class Alloc = allocator<T> > 
class vector;

Members

 It defines following types

Name	Description
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer
const_pointer	allocator_traits<allocator_type>::const_pointer
iterator	a random access iterator to value_type convertible to const_iterator
const_iterator	a random access iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	a signed integral type
size_type	an unsigned integral type

Operation

vector can be graphically represented as below.

New elements are stored in an  initially allocated buffer. After the full capacity is reached, i.e., capacity() == size, a new buffer is allocated with increased capacity and all the elements are copied to it.  However, all the iterators  will also be invalidated. reserve() can be used to pre allocate a bigger buffer to avoid this.

Complexity

The complexity of random access operation is O(1). Insertion or removal at the end is amortized O(1). Insertion or removal at the middle is O(n) and it will also include additional cost of shifting elements backwards from the insertion or deletion point.

Also, reallocation will happen for insertions if size() == capacity().

Functionality

Constructors

In following constructors use default allocator. Custom allocators can be used by passing them as an additional argument.

Name	Description
vector ()	Default Constructor. Example: //v:{} vector<int> v;
vector (size_type n)	Constructs a container with n elements initialized with T(). Example: //v:{0,0,0,0,0} vector<int> v(5);
vector (size_type n, const value_type& val)	Constructs a container with n elements initialized with with val. Example: //v:{10,10,10,10,10} vector<int> v(5,10);
vector (InputIterator first, InputIterator last)	Constructs a container and copies the elements in the range. Example: int a[5]{1,2,3,4,5}; //v:{1,2,3,4,5} vector<int> v(begin(a),end(a));
vector (const vector& x)	copy constructor
vector (vector&& x)	move constructor
vector (initializer_list<value_type> il)	initializer_list constructor. Example: //v:{1,2,3,4,5} vector<int> v{1,2,3,4,5};

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end. Example: vector<int> v{1,2,3,4,5}; //prints 1 2 3 4 5 for (auto itr=v.begin(); itr!=v.end(); ++itr) cout << *itr << ' ';
reverse_iterator rbegin() reverse_iterator rend()	Returns reverse_iterator  to reverse beginning and reverse end. Example: vector<int> v{1,2,3,4,5}; //prints 5 4 3 2 1 for (auto itr=v.rbegin(); itr!=v.rend(); ++itr) cout << *itr << ' ';
const_iterator cbegin const_iterator cend()	Returns const_iterator to beginning and end. Example: vector<int> v{1,2,3,4,5}; //prints 1 2 3 4 5 for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';
const_reverse_iterator crbegin() const_reverse_iterator crend()	Returns const_reverse_iterator  to reverse beginning and reverse end. Example: vector<int> v{1,2,3,4,5}; //prints 5 4 3 2 1 for (auto itr=v.crbegin(); itr!=v.crend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type size()	Returns the number of elements. Example: vector<int> v{1,2,3,4,5}; //prints 5 5 cout << v.size() << " " << v.capacity();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
void resize (size_type n) void resize (size_type n, const value_type& val )	Capacity is also changed to n. size is also changed to n. New elements are initialized to default value.  Capacity is also changed to n. size is also changed to n. New elements are initialized to val.
Example vector<int> v{1,2,3}; //(1) //v:{1,2,3,0,0} v.resize(5); //prints 5 5 cout << v.size() << " " << v.capacity(); //(2) //v:{1,2,3,0,0,9,9,9} v.resize(8,9); //prints 8 8 cout << v.size() << " " << v.capacity();
size_type  capacity()	Return size of allocated storage capacity. When it's equal to size(), storage is reallocated to add new elements.
bool empty()	Test whether vector is empty.
void reserve (size_type n)	changes capacity to n. size will not change. Example: vector<int> v{1,2,3,4,5}; v.reserve(10); //prints 5 10 cout << v.size() << " " << v.capacity();
void shrink_to_fit()	Reduces memory usage by freeing unused memory.  Example: vector<int> v{1,2,3,4,5}; v.reserve(10); //prints 5 10 cout << v.size() << " " << v.capacity(); v.shrink_to_fit(); //prints 5 5 cout << v.size() << " " << v.capacity();

Element Access

Name	Description
reference operator[](size_type n) value_type operator[](size_type n)	Returns reference  to the element at position n. No bounds check is done. In case of vector<bool>,  it returns value_type to the element at position n. No bounds check is done. Example: vector<int> v{1,2,3,4,5}; //prints 2 0. no exception checks cout << v[1] << " " << v[100];
reference at(size_type n)	Returns reference to the element at position n. Exception is thrown for invalid input. Example: vector<int> v{1,2,3,4,5}; //prints 2. exception is thrown. cout << v.at(1) << " " << v.at(100);
reference front()	Returns reference to the first element.  Exception is thrown for invalid input. Example: vector<int> v{1,2,3,4,5}; //prints 1. cout << v.front();
reference back()	Returns reference  to the last element.  Exception is thrown for invalid input. Example: vector<int> v{1,2,3,4,5}; //prints 5. cout << v.back();
value_type* data()	Returns value_type* pointing to the first element. Example: vector<int> v{1,2,3,4,5}; //prints 2. cout << *(v.data()+1);

Modifiers

Name	Description
void assign(InputIterator first, InputIterator last) void assign(size_type n, const value_type& val) void assign(initializer_list<value_type> il)	Replace vector content with the  elements in the range. Replace vector content  with n elements initialized with with val. Replace vector content with the contents of initializer_list
Example: int a[]{1,2,3,4,5}; vector<int> v{}; //(1) //v:{3,4,5} v.assign(begin(a)+2,end(a)); //(2) //v:{10,10,10,10,10} v.assign(5,10); //(3) //v:{1,2,3} v.assign({1,2,3});
void push_back(const value_type& val) void push_back(value_type&& val)	Adds element at the end. Example: vector<int> v{}; //v:{1} v.push_back(1);
void pop_back()	Delete the last element. Example: vector<int> v{1}; //v:{} v.pop_back();
iterator insert(const_iterator pos, InputIterator first, InputIterator last) iterator insert(const_iterator pos, size_type n, const value_type& val) iterator  insert(const_iterator pos, const value_type& val) iterator  insert(const_iterator pos, const value_type&& val) iterator  insert(const_iterator pos,, initializer_list<value_type> il)	At pos, insert the  elements in the range. At pos, insert n elements initialized with with val. At pos, insert an element with value val. At pos, insert an element with value val moved. At pos, insert an element with the contents of initializer_list. All these returns an iterator to the first inserted element.
Example: int a[]{1,2,3,4,5}; vector<int> v{}; vector<int>::iterator itr; //(1) //v:{1,2,3,4,5} //itr = begin(v) itr = v.insert(cbegin(v),begin(a),end(a)); //(2) //v:{1,2,3,4,5,6} //itr = begin(v)+5 itr = v.insert(cend(v),1,6); //(3) //v:{1,2,3,4,5,6,7} //itr = begin(v)+6 itr = v.insert(cend(v),7); //(4) //v:{1,2,3,4,5,6,7,8} //itr = begin(v)+7 itr = v.insert(cend(v),move(8)); //(5) //v:{1,2,3,4,5,6,7,8,9,10} //itr = begin(v)+8 itr = v.insert(cend(v),{9,10});
iterator erase(const_iterator pos) iterator erase(const_iterator first, const_iterator last)	Erases element at pos Erase elements in the range Returns an iterator that points to the element that was  located after the last erased element.
Example: vector<int> v{1,2,3,4,5}; vector<int>::iterator itr; //(1) // v:{2,3,4,5} // itr = begin(v) itr = v.erase(cbegin(v)); //(2) // v:{2,3} // itr = begin(v)+2 itr = v.erase(cbegin(v)+2,cend(v));
void swap(vector& v)	Swap content with v. Note T has to be same. Example: vector<int> v{1,2,3,4,5}; vector<int> v2{5,4,3,2,1}; //v2:{1,2,3,4,5} //v:{1,2,3,4,5} v2.swap(v);
void clear()	Clears the contents. Example: vector<int> v{1,2,3,4,5}; //v:{} v.clear();
iterator emplace(const_iterator pos, Args ...arg)	Construct and insert element in place using arg. Returns an iterator to the first element inserted. Example: vector<int> v{1,2,3,5}; //v:{1,2,3,4,5} //itr=begin()+3 auto itr = v.emplace(cbegin(v)+3,4);
void emplace_back(Args ...arg)	Construct and insert element at the end using arg. Example: vector<int> v{1,2,3,4}; //v:{1,2,3,4,5} v.emplace_back(5);