Tag Archives: Containers

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.

Related

Iterator invalidation rules for C++ containers

If you need to worry about iterator invalidation it may be that you should be using an existing algorithm so that you do not need to modify the container’s contents directly.
You definitely need to understand invalidation however, if you want to write an algorithm.

Insertion

Sequence containers

vector

All iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated).
Reason: A vector is a contiguous array, so an insertion causes a block shift which moves all elements after the point of insertion. If the capacity is increased, the whole block is reallocated, potentially changing its address, and so the addresses of all elements.

deque

All iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected).
Reason: A deque is an array of fixed-size arrays (see Deque in C). Addition to the either end (i.e., to the free space in one of the arrays on an end), cannot cause elements to move, so references remain valid. However, as iterators are based on counting, they are all invalidated by addition.

list

All iterators and references unaffected.
Reason: A list is a linked list. Only the connections between nodes are affected by addition, not the nodes themselves.

Associative containers

set, map, multiset, multimap

All iterators and references unaffected.
Reason: They are all binary trees. Only the connections between nodes are affected by addition, not the nodes themselves.

Container adaptors

stack and queue

Inherited from underlying container.

priority_queue

Inherited from underlying container.

Erasure

Sequence containers

vector

Every iterator and reference after the point of erase is invalidated.
Reason:An erasure causes a block shift leftwards of the succeeding elements, so iterators to them become invalid.

deque

All iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated)
Reason:Removing from the end arrays cannot affect the other elements.

list

Only the iterators and references to the erased element is invalidated
Reason: As per addition.

Associative containers

set, map, multiset, multimap

Only iterators and references to the erased elements are invalidated.
Reason: As per addition.

Container adaptors

stack, queue, and priority_queue

Inherited from underlying container.

Resizing

vector, deque, and list

As per insert/erase.

Related

Finding an element in a container

To find an element in a C++ container, or indeed between any pair of InputIterators, use find or find_if.

Use find to find an element with a value you specify. It will return an iterator pointing to the element being sought if successful, and the end of the range if it isn’t found.


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

int main()
{
    std::vector<unsigned int>numbers(3);
    std::iota(numbers.begin(), numbers.end(), 4); // Populate with 4, 5, 6
    if (std::find(numbers.begin(), numbers.end(), 5) != numbers.end()) {
        std::cout << "Found 5" << "\n";
    }
    else {
        std::cout << "5 not found" << "\n";
    }
}

Use find_if to find an element that satisfies a predicate.

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

struct divides_by_3
{
public:
    bool operator()(int i)
    {
        return i % 3 == 0;
    }
};

int main()
{
    std::vector<unsigned int>numbers(3);
    std::iota(numbers.begin(), numbers.end(), 4); // Populate with 4, 5, 6
    std::vector<unsigned int>::const_iterator it = 
            std::find_if(numbers.begin(), numbers.end(), divides_by_3());
    if (it != numbers.end()) {
        std::cout << "Found a number that divides by 3: " << *it << "\n";
    }
    else {
        std::cout << "Not found" << "\n";
    }
}