CODEWITHSUNDEEP
c++algorithmiterator
Zizheng Tai
Zizheng Tai

Reputation: 6616

Does std::unique invalidate vector iterators?

For this code:

std::vector<int> v = {...};
std::sort(v.begin(), v.end());

// Does this work?
std::size_t unique_count = std::unique(v.begin(), v.end()) - v.cbegin();

In the last line, I think since std::unique just moves stuffs around inside the vector and does not insert anything into it, no iterators should be invalidated, and so the way I'm calculating unique_count should be correct. But I want to make sure that is the case. Is it?

Upvotes: 1

Views: 219

Answers (2)

Bhaal22
Bhaal22

Reputation: 719

std::unique return an iterator to one position past the last 'unique' element in the container.

auto last = std::unique(v.begin(), v.end());

Then the range [last, v.end()) contains whatever, you can't rely on v.cbegin(). Instead:

auto unique_count = std::distance(v.begin(), last);

will do the trick.

http://en.cppreference.com/w/cpp/algorithm/unique

Upvotes: 3

Richard Hodges
Richard Hodges

Reputation: 69882

std::unique is an algorithm. All stl algorithms operate on ranges, not containers.

Although the algorithm may swap element contents, the iterators to those elements remain unchanged.

This is a guarantee.

If it were not, then this could not work:

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

int main()
{

  auto unique_size = [](auto&& container)
  {
    std::sort(std::begin(container), std::end(container));
    return std::unique(std::begin(container), std::end(container)) - std::cbegin(container);
  };

  std::cout << unique_size(std::vector<int> {6,5,4,4,3,2,1}) << std::endl;
  std::cout << unique_size(std::array<int,7> {6,5,4,4,3,2,1}) << std::endl;
  int x[] = {6,5,4,4,3,2,1};
  std::cout << unique_size(x) << std::endl;

    // Does this work? yes.
}

mandated output:

6
6
6

Upvotes: 5

Related Questions