CODEWITHSUNDEEP
c++iteratorset
tglas
tglas

Reputation: 1010

Determine order of set iterators

I have two iterators (say it1 and it2) into the same std::set<int>. They are obtained through lower_bound and upper_bound, therefore they are not safe to dereference (they could equal end()). Is there an easy and safe way of telling which one goes first?

I could call std::distance(it1, it2) and std::distance(it2, it1), but that does not seem to help since if it1 != it2 then one of the calls is UB. I could test *it1 < *it2, but only if no iterator points to the end(). Finally, I could first test for the end iterator and then do the above comparison on values.

Is there an elegant solution based purely on iterators and not involving the values, i.e., dereferencing? I am willing to use up to c++14 and maybe boost.

EDIT (in reponse to comments): I use a set because I want fast lookup and insertion, in particular much faster than linear complexity. A sorted vector would be a possible alternative, it would trivially solve the problem, but insertion and removal are linear time operations.

Upvotes: 0

Views: 145

Answers (1)

Massimiliano Janes
Massimiliano Janes

Reputation: 5624

In my opinion, the best way is to fix your code logic and have [it1,it2) always be a valid range; if this turns out not possible (but how can it be ?), you may use something like

// O(N), forward iterators, it1, it2 should belong to range
template<class Iter>
bool precedes_or_is_equal( Iter it1, Iter it2, Iter end )
{
  while( it1 != end && it1 != it2 ) ++it1;

  return it1 == it2;
}

Upvotes: 3

Related Questions