Tag Archives: vector

Erasing from a vector by index

Use the vector::erase function to erase an element, or range of elements from a vector. It returns an iterator pointing to the element after the last one erased:

v.erase(v.begin() + pos);
v.erase(v.begin() + start, v.begin() + end);

For example, this program populates a vector with the numbers 0 to 9 and then erases 8, before erasing 3 to 5:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    typedef std::vector<int> intvec;
    intvec v(10);
    std::iota(v.begin(), v.end(), 0);
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    std::cout << "erase 8:\n";
    intvec::const_iterator it = v.erase(v.begin() + 8);
    std::cout << "next element is " << *it << "\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    std::cout << "erase 3 to 5:\n";
    it = v.erase(v.begin() + 3, v.begin() + 6);
    std::cout << "next element is " << *it << "\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

You can make a generic function to erase from a container by index by using std::advance to move to the first (and optionally last) element to remove and then calling the container’s own erase method:

template <class Container>
typename Container::iterator erase(Container& cont, size_t pos, size_t len = 1)
{
    typename Container::iterator it1 = cont.begin();
    std::advance(it1, pos);
    typename Container::iterator it2 = it1;
    std::advance(it2, len);
    return cont.erase(it1, it2);
}

Use it like this:

erase(vec, 8);    // erase 8
erase(vec, 3, 3); // erase 3 to 5

Note that this will be O(n) for lists because their iterators are not RandomAccessIterators.

Dynamically allocated 2-d array in C++

Method 1: Use an array of arrays

#include <iostream>

int main()
{
    const size_t rows = 10, columns = 10;
    unsigned int r, c;

    /* Initialize */
    int** array1 = new int*[rows];
    for (r = 0; r < rows; ++r) {
        array1[r] = new int[columns];
    }

    /* Write */
    for (r = 0; r < rows; ++r) {
        for (c = 0; c < columns; ++c) {
            array1[r] = r * c;
        }
    }

    /* Read */
    std::cout << "7 times 8 equals " << array1[7][8] << "\n";

    /* Delete */
    for (r = 0; r < rows; ++r) {
        delete[] array1[r];
    }
    delete[] array1;
}

Method 2: Use a single array

#include <iostream>

int main()
{
    const size_t rows = 10, columns = 10;
    unsigned int r, c;

    /* Initialize */
    int* array2 = new int[rows * columns];

    /* Write */
    for (r = 0; r < rows; ++r) {
        for (c = 0; c < columns; ++c) {
            array2[r * columns + c] = r * c;
        }
    }

    /* Read */
    std::cout << "7 times 8 equals " << array2[7 * columns + 8] << "\n";

    /* Delete */
    delete[] array2;
}

Note that the formula for accessing a cell is row * columns + row.

Method 3: Use a vector of vectors

#include <iostream>
#include <vector>

int main()
{
    const size_t rows = 10, columns = 10;
    unsigned int r, c;

    /* Initialize */
    std::vector<std::vector<int> > array3(rows,
            std::vector<int>(columns));

    /* Write */
    for (r = 0; r < rows; ++r) {
        for (c = 0; c < columns; ++c) {
            array3[r] = r * c;
        }
    }

    /* Read */
    std::cout << "7 times 8 equals " << array3[7][8] << "\n";
}

Notice the use of the vector constructor that makes rows copies of a row vector.

Method 4: Use Boost.MultiArray

#include <iostream>
#include <boost/multi_array.hpp>

int main()
{
    const size_t rows = 10, columns = 10;

    /* Initialize */
    boost::multi_array<int, 2> array4(boost::extents[rows][columns]);
    boost::multi_array<int, 2>::index r, c;

    /* Write */
    for (r = 0; r < rows; ++r) {
        for (c = 0; c < columns; ++c) {
            array4[r] = r * c;
        }
    }

    /* Read */
    std::cout << "7 times 8 equals " << array4[7][8] << "\n";
}

Reference:The Boost Multidimensional Array Library

std::vector::emplace_back()

The emplace_back() method is a C++11 addition to vector that makes it more efficient to add an object to the back of a vector.

Consider the following code:

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

class X
{
public:
    X(std::string s, int i)
        : s_(s), i_(i)
    {
        std::cout << "Constructor called for " << s_ << i_ << "\n";
    }
    X(const X& other)
        : s_(other.s_), i_(other.i_)
    {
        std::cout << "Copy constructor called for " << s_ << i_ << "\n";
    }
private:
    std::string s_;
    int i_;
};

int main()
{
    std::vector<X> v;
    std::cout << "push_back:" << "\n";
    v.push_back(X("A", 1));
}

An object of a class with 2 member variables initialised in the constructor is first constructed, and added to the end of a vector with push_back().

This is a 2-step process:

  1. Construct the object
  2. Copy it into the vector’s storage

The output from the program shows this process:

push_back:
Constructor called for A1
Copy constructor called for A1

Constructing an object, copying it, and then destroying it when it goes out of scope is not very efficient, and it’s this inefficiency that emplace_back is designed to remove.

emplace_back takes a variable list of arguments, which must match those of one of the object’s constructors, and these are forwarded to that constructor so that the object is constructed in-place.

    std::cout << "emplace_back:" << "\n";
    v.emplace_back("A", 1);

This produces the following output:

emplace_back:
Constructor called for A1

So the unnecessary copy has not happened.

Populate a vector with literal values

Method 1: Use an array and the range constructor

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    typedef std::vector<int> intvec;

    int arr[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    const size_t n = sizeof(arr) / sizeof(int);
    intvec vec1(arr, arr + n);
    
    std::copy(vec1.begin(), vec1.end(), std::ostream_iterator<int>(std::cout, " "));
}

Method 2: Use boost::assign::list_of

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/assign/list_of.hpp>
#include <boost/range/algorithm/copy.hpp>

int main()
{
    typedef std::vector<int> intvec;

    int arr[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    const size_t n = sizeof(arr) / sizeof(unsigned int);
    
    intvec vec2 = boost::assign::list_of(31)(28)(31)(30)(31)(30)(31)(31)(30)(31)(30);
    
    boost::copy(vec2, std::ostream_iterator<int>(std::cout, " "));
}

Method 3: Use boost::assign

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/assign/std/vector.hpp>
#include <boost/range/algorithm/copy.hpp>
using namespace boost::assign; // bring 'operator+=()' into scope

int main()
{
    typedef std::vector<int> intvec;

    intvec vec3;
    vec3 += 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30;
    
    boost::copy(vec3, std::ostream_iterator<int>(std::cout, " "));
}

Method 4: Use a C++11 initializer

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    typedef std::vector<int> intvec;

    intvec vec4 = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    
    std::copy(vec4.begin(), vec4.end(), std::ostream_iterator<int>(std::cout, " "));
}

Concatenate two vectors in C++

Method 1: Use std::vector::insert()

    vector1.insert(vector1.end(), vector2.begin(), vector2.end());

Method 2: Use std::copy with a std::back_inserter()

    std::copy(vector2.begin(), vector2.end(), std::back_inserter(vector1));

Method 3: Use std::reserve() and then std::copy()

This means that the vector won’t need to be reallocated during the copy, so may be faster.

    vector1.reserve(vector1.size() + vector2.size());
    std::copy(vector2.begin(), vector2.end(), vector1.end());

Method 4: Use std::transform() with std::back_inserter()

This means you can use a functor on the elements of vector2 to modify them or change their type before adding them.

    std::transform(vector2.begin(), vector2.end(), vector1.begin(), transformer());

Method 5: Use std::reserve() and then std::transform()

    vector1.reserve(vector1.size() + vector2.size());
    std::transform(vector2.begin(), vector2.end(), vector1.begin(), transformer());

In all cases you can use the new C++11 std::begin() and std::end() functions to get the beginnings and endings of the vectors.