Agenda
1. Vector Basics
- Vector definition
- Add an element to Vector
- Delete element in Vector
- Iterate Vector
- Clear Vector
- Pass Vector as a function parameter

2. Vector Optimization
- reserve()
- shrink_to_fit()
- emplace_back()
- capacity()

1. Vector Basics

std::vector is a dynamic array that doesn’t have a fixed size. From the perspective of memory, the dynamic array is stored continuously on memory.

Now, what happens when we extend the Vector?

Table 1

Vector definition

Create vector of simple data(int); vector of data structure(struct); vector of pointer(pointer of int)

std::vector<int> vectorOfInt;std::vector<MyStruct> vectorOfStruct;std::vector<int*> vectorOfPointerOfInt;

Add an element to Vector

vectorOfInt.push_back(1);

Delete element in Vector

// delete the second element
vectorOfInt.erase(vectorOfInt.begin() + 1);

Iterate Vector

for(int i = 0; i < vectorOfInt.size(); i++) {   // Method 1
std::cout << vectorOfInt[i] << std::endl;
}
for(int v: vectorOfInt) { // Method 2
std::cout << v << std::endl;
}

Clear Vector

vectorOfInt.clear()  // makes the size of vector = 0vectorOfInt.empty()  // return TRUE if empty

Pass Vector as a function parameter

Usually, we pass the reference-of-vector instead of Vector itself, to avoid copying the whole vector into the function.

void myfunc(const std::vector<int>& vectorOfInt){
...
}

2. Vector optimization

There are some functions of vector that could be used for optimization.

reserve()

The whole copy-paste process is quite costly, to avoid this effort. We could reserve some places for the Vector. The reserve() function reserve enough space in memory to hold 3 elements of vectorOfInt.

shrink_to_fit()

This function free the unused but reserved space.

emplace_back()

emplace_back() achieves the same goal as push_back(). The only difference is that emplace_back() could avoid unnecessary reallocation (a.k.a. the copy-paste-process in table 1).

capacity()

This function returns the number of elements the vector could save at the current memory address.

Let's see an example: we will create a vector of the following struct:

struct MyStruct {
int x, y, z;

MyStruct(int x, int y, int z) : x(x),y(y),z(z) {
}

MyStruct(const MyStruct& myStruct) : x(myStruct.x), y(myStruct.y), z(myStruct.z) {
std::cout << "call copy constructor" << std::endl;
}
};

Case 1: without optimization

- 3× “call copy constructor” generated by constructing MyStruct object in main(), then copy it to the address of vectorOfStruct
- 3× “call copy constructor” generated by resizing the vectorOfStruct from 0->1, 1->2 and 2->3

Case 2: use emplace_back()

- 3× “call copy constructor” generated by resizing the vectorOfStruct from 0->1, 1->2 and 2->3

Case 3: use emplace_back() and reserve()

Case 4: use emplace_back(), reserve() and shrink_to_fit()

If there is redundant space in memory, we use shrink_to_fit() to release the empty space.

Lebenslang lernen