Introduction

The standard template library (STL) contains utility classes that make it easy to work with data. One area that the STL tries to address is the issue of containers. In the STL you find vectors, maps, unordered maps, arrays, queues and so on. One of the most commonly used containers is the vector.

Vector Basics

The vector class is basically a contiguous memory array of a specified type that can grow or shrink (kind of) during it’s use. Below is a snippet of basic usage:

#include <vector>

int main()
{
    std::vector<int> data;
    data.push_back(1);
    // data now holds 1 element.
}

Note the use of push_back() here. According to the documentation push_back() does the following:

  • Appends the given value to the end of the container.
  • Initializes the new value as copy.
  • Value is then moved into the new element.
  • If the size of the vector is greater than the capacity, all iterators and references are invalidated.

The most interesting part of the documentation is the last statement. The std::vector class tries to be memory efficient as much as possible and adopts a sort-of lazy allocation logic. Basically, the vector will only allocate memory when it needs it. So when the vector is empty, no memory is needed so no memory is allocated.

This means that when you call push_back() on a vector, you could be causing re-allocations to occur. Thankfully, std::vector doesn’t allocate only 1 extra position when it re-allocates; it allocates more memory than it needs so that when push_back() is called again, no re-allocation occurs until more space is needed at which point it will allocate even more memory. Still, there are more efficient ways of using this container. One better way to use std::vector is to pre-allocate space, and then just assign values. For example, consider this for loop:

std::vector<int> data;
for(int i = 0; i < 5; i++)
{
    data.push_back(i);
}

This loop could instead become:

std::vector<int> data(5, 0);
for(int i = 0; i < 5; i++)
{
    data[i] = i;
}

This second loop actually pre-allocates space for 5 int elements and then initializes the 5 values to 0. Then in the for loops, the 5 values are reassigned to i during each loop. This does not cause any re-allocation to occur thus making it more memory efficient.

Advanced Usage

I want to also touch briefly on the difference between push_back() and emplace_back(). As discussed in the earlier section, push_back() adds a new value to the end of the vector by doing a copy and a move. On the other hand, emplace_back() performs the same basic operation but avoid the extra copy or move. It basically creates the item in place inside the vector instead of constructing and then moving.

This becomes useful when passing rvalues to the emplace_back() function. For example, consider the example below:

#include <string>
#include <iostream>
#include <vector>

struct Data
{
    int id;
    std::string name;

    Data(int data_id, std::string data_name)
        : id(data_id), name(data_name)
    {
        std::cout << "data constructed" << std::endl;
    }

    Data(Data && other)
        : id(std::move(other.id)),  name(std::move(other.name))
    {
        std::cout << "data moved" << std::endl;
    }
};

int main()
{
    std::vector<Data> m_data;

    std::cout << "emplace" << std::endl;
    m_data.emplace_back(1, "test");

    std::cout << "push" << std::endl;
    m_data.push_back(Data(2, "test_2"));
}

The output of the above code:

emplace
data constructed
push
data constructed
data moved

This illustrates the point that data is created in place and not constructed and then moved which is obviously more efficient.

Conclusion

I hope this brief post on std::vector has given you more insight into how the class works and the basic ways to make the most of it. Questions, comments and suggestions are always welcome.

Leave a Comment

Your email address will not be published. Required fields are marked *

Loading...