2.7. Analysis of Vector Operators¶

Accessing data using an index and assigning to an index position that already exists both take the same amount of time no matter how large the vector is. When an operation like this is independent of the size then it is \(O(1)\).

As we have seen, one way to create a longer vector is to use the push_back() method. The push_back() method is typically \(O(1)\), provided there is adequate capacity in the underlying array.

First we'll use push_back() method. The following code shows the code for making our vector.

#include <vector>
using std::vector;

void test_push_back(int size){
    vector<int> vect;
    for (int i = 0; i < size; ++i){
        vect.push_back(i);
    }
}

And we can time how long it takes to push 10,000 values into a vector.

 1#include <chrono>
 2#include <iostream>
 3#include <vector>
 4using std::vector;
 5
 6void test_push_back(int size){
 7    vector<int> vect;
 8    for (int i = 0; i < size; i++){
 9        vect.push_back(i);
10    }
11}
12
13int main(){
14    using msec_t = std::chrono::duration<double, std::milli>;
15
16    auto begin = std::chrono::steady_clock::now();
17    test_push_back(10'000);
18    auto end = std::chrono::steady_clock::now();
19    msec_t elapsed_time = end - begin;
20
21    std::cout << "push_back (msec): " << elapsed_time.count() << '\n';
22
23    return 0;
24}

In the experiment above the statement that we are timing is the function call to test_push_back. From the experiment, we see the amount of time taken by the push_back operation. Not only is the push_back() function call duration being measured, but the time to allocate space is being measured.

We can improve the runtime a bit further by setting an adequate reserve for the vector in advance. Doing this will keep us from having to move the entire vector to an adequately sized space in memory as the vector grows.

 1#include <chrono>
 2#include <iostream>
 3#include <iomanip>
 4#include <vector>
 5using std::vector;
 6
 7void test_push_back(int size){
 8    vector<int> vect;
 9    for (int i = 0; i < size; ++i){
10        vect.push_back(i);
11    }
12}
13
14void test_reserve(int size){
15    vector<int> v(size);
16    for (int i = 0; i < size; ++i){
17        v[i] = i;
18    }
19}
20
21int main(){
22    using std::cout;
23    using std::chrono::steady_clock;
24    using msec_t = std::chrono::duration<double, std::milli>;
25
26    cout << std::setw(6) << "size\t"
27         << std::setw(8) << "push_back\t"
28         << std::setw(8) << "pre-allocated vector (all times in msec)\n";
29
30    for(int size = 1'000; size < 1'000'000; size += 50'000) {
31
32      auto begin = steady_clock::now();
33      test_push_back(size);
34      auto end = steady_clock::now();
35      msec_t elapsed_1 = end - begin;
36
37      auto begin2 = steady_clock::now();
38      test_reserve(size);
39      auto end2 = steady_clock::now();
40      msec_t elapsed_2 = end2 - begin2;
41
42      cout << std::setprecision(6) << std::fixed
43           << size << '\t'
44           << std::setw(8) << elapsed_1.count() << '\t'
45           << std::setw(8) << elapsed_2.count() << '\n';
46    }
47    return 0;
48}

A graph of the loops in the preceding code should look something like this:

Now that we have seen how performance can be measured concretely you can look at the table below to see the complexity of some basic vector operations. When pop_back() is called, the vector size is reduced by 1 and it takes constant time: \(O(1)\). However, when erase() is called the time is \(O(n)\). The reason for this lies in how C++ chooses to implement vectors. When an item is taken from the front of the vector, in C++ implementation, all the other elements in the vector are shifted one position closer to the beginning. This implementation also allows the index operation to be \(O(1)\). This is a trade-off that the C++ implementers thought was a good one.

**Complexity of C++ vector operations**¶
Operation	Complexity
index []	O(1)
index assignment =	O(1)
push_back()	amortized O(1)
pop_back()	O(1)
erase(i)	O(n)
insert(i, item)	O(n)
find(b, e, item)	O(n)
reserve()	O(n)
begin()	O(1)
end()	O(1)
size()	O(1)

The push_back() operation is \(O(1)\) unless there is inadequate capacity, in which case the entire vector is moved to a larger contiguous underlying array, which is \(O(n)\). However, since over the long term, as \(n\) grows large, then number of vector copies is small. So on average, even though there are some \(O(n)\) operations, it turns out that push_back() is constant time.

As a way of demonstrating the difference in performance between pop_back() and erase(), let's do another timing experiment. Our goal is to be able to verify the performance of the pop_back() operation on a vector of a known size when the program pops from the end of the vector using pop_back(), and again when the program pops from the beginning of the vector using erase(). We will also want to measure this time for vectors of different sizes. What we would expect to see is that the time required to pop from the end of the vector will stay constant even as the vector grows in size, while the time to pop from the beginning of the vector will continue to increase as the vector grows.

The following code shows one way to measure the difference between the pop_back() and erase().

 1#include <chrono>
 2#include <iostream>
 3#include <iomanip>
 4#include <numeric>
 5#include <vector>
 6using std::vector;
 7
 8int main(){
 9    using std::cout;
10    using std::chrono::steady_clock;
11    using msec_t = std::chrono::duration<double, std::micro>;
12
13    cout << std::setw(6) << "size\t"
14         << std::setw(8) << "pop_back\t"
15         << std::setw(8) << "erase\t\t"
16         << std::setw(8) << "how much faster is pop_back?\n";
17    cout << std::setw(19) << "(microsec)\t"
18         << std::setw(10) << "(microsec)\n";
19
20    for(int size = 10'000; size < 100'000; size += 10'000) {
21        // Create 2 identical vectors with values 0..N
22        vector<int> data1(size);
23        std::iota(data1.begin(), data1.end(), 0);
24        vector<int> data2(data1);
25
26
27      auto begin1 = steady_clock::now();
28      for (int i = 0; i < size; i++){
29        data1.pop_back();
30      }
31      auto end1 = steady_clock::now();
32      msec_t elapsed_1 = end1 - begin1;
33
34      auto begin2 = steady_clock::now();
35      for (int i = 0; i < size; i++){
36        data2.erase(data2.begin());
37      }
38      auto end2 = steady_clock::now();
39      msec_t elapsed_2 = end2 - begin2;
40
41      cout << std::setprecision(6) << std::fixed
42           << size << '\t'
43           << std::setw(8) << elapsed_1.count() << '\t'
44           << std::setw(8) << elapsed_2.count() << "\t"
45           << std::setprecision(0)
46           << std::setw(8) << elapsed_2.count() / elapsed_1.count() << " times\n";
47    }
48    return 0;
49}

Although erase is \(O(n)\), a graph showing how much faster pop_back() can be as the size of a vector grows can still be surprising.

Self Check

Select the complexity associated with the listed operation(s).

begin(), end()

erase(i), insert(i, item)

find(srt, stp, item)

index assignment =

push_back(), pop_back()

reserve()

size(), index []

More to Explore