2

A std::maps iterators stay valid when inserting elements, eg:

std::map<std::string,int> my_map;
my_map["foo"] = 1;
my_map["bar"] = 2;

auto it_foo = my_map.find("foo");
auto it_bar = my_map.find("bar"); 

my_map["foobar"] = 3;

after inserting another element (in the last line) the two iterators are still valid. How about the end ? For example:

auto it_end = my_map.find("something that isnt in the map");

my_map["barfoo"] = 4; // does not invalidate iterators

assert(it_end == my_map.end()); // ??

In other words: If a method does not invalidate iterators (other than those explicitly mentioned, as for example in case of map::erase) does this mean that also the end is guaranteed to be the same before as after calling the method?

PS: I am aware that I could just try and see, but this wont tell me whether I can rely on this behaviour.

PPS: For example pushing into a std::vector invalidates all iterators, or only the end (when no reallocation took place), but in this case the docs explicitly mention the end. Following this reasoning, "no iterators are invalidated" should include end, but I am not 100% convinced ;)

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • 3
    "no iterators" means **no iterators**, why do you think otherwise? – Slava Nov 30 '17 at 14:41
  • "I am aware that I could just try and see" do not do that, you should rely on documented behavior, not deduced from particular implementation. – Slava Nov 30 '17 at 14:43
  • @Slava I dont think otherwise, I am just not 100% sure if my interpretation of the docs is correct. – 463035818_is_not_an_ai Nov 30 '17 at 14:43
  • 1
    @Slava That's specifically what he says in the question, in the second part of the line you quoted, which you left out. – François Andrieux Nov 30 '17 at 14:44
  • https://stackoverflow.com/questions/6438086/iterator-invalidation-rules What is missing in this answer? – lars Nov 30 '17 at 14:44
  • @lars it misses a clear statement on whether "all iterators" does include the `end`. On a quick scrollthrough I only found special mentions like: "no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ]" The fact that `end` is merely a note here makes me unsure again if it is included in general – 463035818_is_not_an_ai Nov 30 '17 at 14:46
  • @tobi303 in cases when `end()` is not included in "all iterators" category they explicitly mention that, you have convoluted logic that says "then the end() must be always mentioned explicitly". Don't you see that? – Slava Nov 30 '17 at 14:49
  • @lars also... same answer, next paragraph: "Other than the above caveat regarding swap(), it's not clear whether "end" iterators are subject to the above listed per-container rules; you should assume, anyway, that they are." ... so the question explicitly states that whehter "end" is included is unclear, and I want to clarify that for one specific example – 463035818_is_not_an_ai Nov 30 '17 at 14:49
  • @Slava I never claimed that my logic is sound. In fact it is just the opposite: I tried to make some sense of what I read, but I couldnt convince myself. Thats why I ask – 463035818_is_not_an_ai Nov 30 '17 at 14:50
  • @tobi303 in your example `end()` behavior is different than anything else, plus `end()` is not in category mentioned so author explicitly pointed to that. Why did you come to conclusion than cases, when end() behaves exactly the same as anything else also need explicit mention? – Slava Nov 30 '17 at 14:54
  • @Slava sorry but I dont understand. why "different than anything else" ? What "category" do you mean? Why do you keep trying to convince me that I have a conclusion? I didnt come to a conclusion other than: I dont have a conclusion ;) – 463035818_is_not_an_ai Nov 30 '17 at 14:57
  • @tobi303 in your example with `swap()` `end()` has different behavior that anything alse and author points to that explicitly. Yes in documentation for `std::vector` it is inclusive and mentioned explicitly, but in `std::map` it is inclusive and not mentioned and it inconsistent, but I do not think that should be a reason for your doubt. – Slava Nov 30 '17 at 14:59
  • @Slava that was not the only reason for my doubts. If that troubles you then please just ignore the PS & PPS, they arent really relevant for the question anyhow. Imho the question alone is quite clear, if I could explain you in logical terms what is the origin of my doubts, then most likely I didnt have the doubts in the first place.... – 463035818_is_not_an_ai Nov 30 '17 at 15:04
  • Maybe you should explain all reasons in your question, I just tried to understand what is the ground of your doubts. – Slava Nov 30 '17 at 15:06
  • maybe a better wording of my mis/non-understanding is: `end` is special anyhow, it doest not point to an element **in** the container, it cannot be dereferenced, etc.. so I wouldnt be surprised if a method that otherwise does not invalidate any iterator does invalidate end. On the other hand end is so special that even for a `std::vector` one could imagine an `end` that never gets invalidated (but of course we know it can get invalidated)... maybe i will edit the question later... – 463035818_is_not_an_ai Nov 30 '17 at 15:11

1 Answers1

4

N4140 23.2.4 Associative containers [associative.reqmts][1]

9 The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

Definitely the term iterators refers to all iterators including end.

Mihayl
  • 3,821
  • 2
  • 13
  • 32
  • 1
    if you change "should be.." to "definitely the term iterators refers to all iterators including `end`" I can accept the answer ;) – 463035818_is_not_an_ai Nov 30 '17 at 15:14
  • I'll definitely look again in the standard for places that mentin the `end` iterator. It's interesting to find out wether it's threated differently from the other iterators. – Mihayl Nov 30 '17 at 16:25