10

I would like to erase all the items less than v in C++11 standard container set, here is my code:

void delete_less_than(set<int> & ss, int const v) {
   for (auto item: ss) {
      if (item < v) {
        ss.erase(ss.find(item));
      } else break;
  }  
}

Will the code work properly? I seems okay on my computer (g++ 4.7.3), but loops infinitely on some online judge where I submit my code.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
notbad
  • 2,797
  • 3
  • 23
  • 34
  • Even i love the range for, a good example that convince might be no good (assume some function calls something modifying the container). –  Dec 01 '13 at 21:08

1 Answers1

31

That's not what the range-based loop is for. Don't use it; use a normal for loop instead. The range-based version is only if you want to do something with every element in the container, without mutating the container.

for (auto it = ss.begin(); it != ss.end(); )
{
    if (*it < v) { ss.erase(it++); }
    else         { ++it;           }
}

Even simpler:

ss.erase(ss.begin(), ss.lower_bound(v));
Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • thx, I also want to whether the behavior the my code is defined or not? Or does it dependent on the compiler? – notbad Dec 01 '13 at 20:53
  • 3
    @notbad: it's undefined. The standard defines the code which a range-based for is equivalent to. That code uses an iterator, and the iterator it uses is invalidated by the `erase`. – Steve Jessop Dec 01 '13 at 20:55
  • @notbad: What Steve said. Check 6.5.4 for the definition of the operational semantics of the range-based loop; you end up using invalid iterators with your code. – Kerrek SB Dec 01 '13 at 20:56
  • Surely `lower_bound`, we're deleting stuff less than `v` but not `v` itself if present. – Steve Jessop Dec 01 '13 at 21:58
  • @SteveJessop: Thanks - I was intent on deleting `v` for some reason... – Kerrek SB Dec 01 '13 at 22:29
  • 3
    Oh, that `lower_bound` solution is sexy! – fredoverflow Dec 01 '13 at 22:37
  • @FredOverflow: Why not use the efficient algorithms that your data structure affords :-) – Kerrek SB Dec 01 '13 at 22:46
  • 1
    I've worried whether `ss.erase(it++);` invalidates the `it` iterator. Is it okay, since `it` is incremented by the side-effect of `it++` _before_ `ss.erase()` is invoked, and hence the post-increment `++` is still operating on a valid iterator (and since iterators to non-erased elements are still valid after std::set::erase())? So, would swapping in two statements, `ss.erase(it); ++it;` then be using an invalid iterator? Could relying on a fine distinction like this be an issue for clarity or maintainability? – Anthony Hall Dec 02 '13 at 08:17
  • 2
    @anthrond: `erase(it++)` is fine; `erase(it); ++it;` is not fine, because `erase` invalidates the iterator. – Kerrek SB Dec 02 '13 at 08:51
  • But doesn't the `std::lower_bound`-solution need a sorted range? – Christian Rau Dec 02 '13 at 10:24
  • @ChristianRau: It's your lucky day: `std::set` *is* already sorted :-) – Kerrek SB Dec 02 '13 at 11:11
  • @KerrekSB Hah right, I totally missed that. I think I just read a question about `std::string` right before and must have messed that up. – Christian Rau Dec 02 '13 at 11:44
  • 5
    `ss.erase(it++);` is clever but relying on pre-/post-increment semantics is setting up future maintainers for trouble. `erase` returns the next iterator, so the usual recommended solution is `it = ss.erase(it);` – bug Sep 22 '17 at 17:17