[C++/STL] Vector

This post is written by YoungJ-Baek

1. Preface

In this post, I wrote summary of vector STL. You can see the meaning of vector container, functions in vector STL, and some tips of vector.

2. Vector

2.1. What’s Vector container

In C, there are some problems using array because of memory allocation. However, in C++, you can use vector STL which allocate memory automatically itself. You don’t have to worry about size of array and deletion of memory because vector deletes memory itself after usage. Also, you can use any value type because it is based on template.

It is similar to stack architecture while it adds and deletes element in back of array. You can add element in the middle of array, but it is not efficient because vector STL is based on array.

2.2. Prior knowledge

You have to know difference between size and capacity of vector array. Size is a number of elements, and capacity is available memory space. Vector container reallocate memory when size == capacity.

2.2.1. Simple example of ‘size’ and ‘capacity’

#include <vector>
#include <iostream>
using namespace std;

int main()
{
	vector<int> v;

	for (int i = 0; i <= 100; i++)
	{
		v.push_back(i + 1);
		cout << "[" << v[i] << "," << v.size() << "," << v.capacity() << "]" << endl;
	}
	return 0;
}

[1,1,1] [2,2,2] [3,3,3] [4,4,4] [5,5,6] [6,6,6] [7,7,9] [8,8,9] [9,9,9] [10,10,13] [11,11,13] [12,12,13] [13,13,13] [14,14,19] [15,15,19] [16,16,19] [17,17,19] [18,18,19] [19,19,19] [20,20,28] [21,21,28] [22,22,28] [23,23,28] [24,24,28] [25,25,28] [26,26,28] [27,27,28] [28,28,28] [29,29,42] [30,30,42] [31,31,42] [32,32,42] [33,33,42] [34,34,42] [35,35,42] [36,36,42] [37,37,42] [38,38,42] [39,39,42] [40,40,42] [41,41,42] [42,42,42] [43,43,63] [44,44,63] [45,45,63] [46,46,63] [47,47,63] [48,48,63] [49,49,63] [50,50,63] [51,51,63] [52,52,63] [53,53,63] [54,54,63] [55,55,63] [56,56,63] [57,57,63] [58,58,63] [59,59,63] [60,60,63] [61,61,63] [62,62,63] [63,63,63] [64,64,94] [65,65,94] [66,66,94] [67,67,94] [68,68,94] [69,69,94] [70,70,94] [71,71,94] [72,72,94] [73,73,94] [74,74,94] [75,75,94] [76,76,94] [77,77,94] [78,78,94] [79,79,94] [80,80,94] [81,81,94] [82,82,94] [83,83,94] [84,84,94] [85,85,94] [86,86,94] [87,87,94] [88,88,94] [89,89,94] [90,90,94] [91,91,94] [92,92,94] [93,93,94] [94,94,94] [95,95,141] [96,96,141] [97,97,141] [98,98,141] [99,99,141] [100,100,141] [101,101,141]

3. Functions of Vector STL

3.1. Constructor

Basic form : vector<{data type}> {value name}

• vector<{data type}> {value name}

  make empty vector container

• vector<{data type}> {value name}(n)

  make n size vector container initialized by 0

• vector<{data type}> {value name}(n, v)

  make n size vector container initialized by v

• vector<{data type}> {value name1}(value name2)

  make vector container(value name1) copying vector container(value name2)

3.2. Relational Operator

• ==

  if two vectors are same in size and elements, return true. Ohterwise, return false.

• !=

  if two vectors are different in size or elements, return true. Ohterwise, return false.

• >, >=, <, <=

  search elements from beginning index 0 and compare two elements when find difference. If one vector container is shorter while searching is keep going, it is considered that the longer one is bigger than shorter one.

  It is similar with string comparison.

• Plus

  • =

    copy right vector container to left vector. Original elements of left one are destroyed. If you want to copy some parts of vector, use assign member function.

  • []

    you can use index operator in vector same as array.

3.3. Member Function

• at(idx)

  refer idx-th element. This function checks range of vector, so it is slower than [] but more safe than []

• front(), back()

  refer first and last element. These can be used without iterator.

• begin(), end()

  point first element and next to last element( last element -> end point ). These must be used with iterator.

• rbegin(), rend()

  same as begin(), end(), but start from the last element. So rend() points next to first element( end point -> first element ). These must be used with iterator.

• push_back(n)

  add n right after last element.

• pop_back()

  eliminate last element.

• clear()

  delete all elements. However, it doesn’t delete memory allocation which means it makes size to 0 while capacity is still not 0.

  If you don’t use cleared vector anymore, it is not efficient to keep unused vector to have memory allocated. In this situation, use swap() instead. More explanation is under this post.

• reserve()

  reserve memory so that program can allocate memory before reallocation. It is useful because vector STL reallocate capacity automatically, but it costs much time.

• size(), capacity(), max_size()

  return size, capacity and max size( memory size ) of vector.

• empty()

  return true if vector is empty. It is only related with size of vector, not capacity of vector.

• erase(iter), erase(start, end)

  If you use erase function with one iterator parameter, delete element which iter points at.

  If you use erase function with two iterator parameter, delete elements between start and end. End element is not included in elimination which means [start, end).

  erase function decrease size of vector, but it keeps capacity of vector same as before deletion.

  Return iter’s next element.

• insert(idx, n), insert(idx, x, n), insert(idx, start, end)

  If you use insert function with two parameters, insert n into idx-th element and return idx-th iterator.

  If you use insert function with three parameters without iterator, insert n x times started from idx-th element.

  If you use insert function with three parameters with iterator, insert elements between start and end. End element is not included in insertion which means [start, end).

• resize(x), resize(x, n)

  If you use resize function with one parameter, resize vector in x size and initialize extended space with default value 0.

  If you use resize function with two parameter, resize vector in x size and initialize extended space with n.

• swap(vector)

  Swap everything( elements and capacities) between two vectors.

  It is helpful when you want to deallocate vector memory before program ends. You can make one temporary vector with 0 capacity and use swap.

  vector<int>(vector2).swap(vector1)

4. Summary