I've not found a tidy, all-in-one table of all the C++0x container iterator invalidation rules.
So, with references, here they are!
Insertion
| Container |
Rules |
n3242 ref. |
| 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) |
23.3.6.5/1 |
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) |
23.3.3.4/1 |
list |
all iterators and references unaffected |
23.3.5.4/1 |
forward_list |
all iterators and references unaffected (applies to insert_after) |
23.3.4.5/1 |
array |
(n/a) |
|
| Associative containers |
set |
all iterators and references unaffected |
23.2.4/9 |
multiset |
map |
multimap |
| Unordered associative containers |
unordered_set |
all iterators invalidated when rehashing occurs, but references unaffected |
23.2.5/8 |
unordered_multiset |
unordered_map |
unordered_multimap |
| Container adaptors |
stack |
inherited from underlying container |
|
queue |
priority_queue |
Erasure
| Container |
Rules |
n3242 ref. |
| Sequence containers |
vector |
every iterator and reference after the point of erase is invalidated |
23.3.6.5/3 |
deque |
erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) |
23.3.3.4/1 |
list |
only the iterators and references to the erased element is invalidated |
23.3.5.4/1 |
forward_list |
only the iterators and references to the erased element is invalidated (applies to erase_after) |
23.3.4.5/1 |
array |
(n/a) |
|
| Associative containers |
set |
only iterators and references to the erased elements are invalidated |
23.2.4/9 |
multiset |
map |
multimap |
| Unordered associative containers |
unordered_set |
only iterators and references to the erased elements are invalidated |
23.2.5/13 |
unordered_multiset |
unordered_map |
unordered_multimap |
| Container adaptors |
stack |
inherited from underlying container |
|
queue |
priority_queue |
Resizing
| Container |
Rules |
n3242 ref. |
| Sequence containers |
vector |
as per insert/erase |
23.3.6.5/12 |
deque |
as per insert/erase |
23.3.3.4/1 |
list |
as per insert/erase |
23.3.5.3/1 |
forward_list |
as per insert/erase |
23.3.4.5/25 |
array |
(n/a) |
|
Bootnote 1
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [23.2.1/11]
Bootnote 2
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 ] [23.2.1/10]
Bootnote 3
Other than the above caveat regarding swap() and the erasure rule for deque, it's not clear whether "end" iterators are subject to the above listed per-container rules; you should assume, anyway, that they are.
(this post can also be found on Stack Overflow)
(also see the same post regarding C++03)
I've not found a tidy, all-in-one table of all the C++ 2003 container iterator invalidation rules.
So, with references, here they are!
Insertion
| Container |
Rules |
2003 ref. |
| 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) |
23.2.4.3/1 |
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) |
23.2.1.3/1 |
list |
all iterators and references unaffected |
23.2.2.3/1 |
| Associative containers |
set |
all iterators and references unaffected |
23.1.2/8 |
multiset |
map |
multimap |
| Container adaptors |
stack |
inherited from underlying container |
|
queue |
priority_queue |
Erasure
| Container |
Rules |
2003 ref. |
| Sequence containers |
vector |
every iterator and reference after the point of erase is invalidated |
23.2.4.3/3 |
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) |
23.2.1.3/4 |
list |
only the iterators and references to the erased element is invalidated |
23.2.2.3/3 |
| Associative containers |
set |
only iterators and references to the erased elements are invalidated |
23.1.2/8 |
multiset |
map |
multimap |
| Container adaptors |
stack |
inherited from underlying container |
|
queue |
priority_queue |
Resizing
| Container |
Rules |
2003 ref. |
| Sequence containers |
vector |
as per insert/erase |
23.2.4.2/6 |
deque |
as per insert/erase |
23.2.1.2/1 |
list |
as per insert/erase |
23.2.2.2/1 |
Bootnote
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [23.1/11]
Bootnote 2
It's not clear in C++2003 whether "end" iterators are subject to the above rules; you should assume, anyway, that they are (as this is the case in practice).
(this post can also be found on Stack Overflow)
(also see the same post regarding C++0x)
A comment from a thread on Spotify/Pandora/Grooveshark:
[I] don't get the music industry. They're like a bunch of old people in a retirement home listening to LP records. Have they a clue how these streaming tools will be a bonanza for the music industry. Another example, are Ereaders. I have bought more books using the Kindle then I ever did in my life (i really need to get a handle on that btw). I still have no clue why Amazon is not jumping on this and create their own streaming player which would let me listen to music based on my likes and then just purchase it from there. I am currently using DoubleTwist but it does not stream music or have a 'radio' or 'similar music' feature. Pandora's IPO is nearly going underwater this morning so maybe investors just don't get how these companies will make money.
Perversely, with the law the way it's written at the moment (with copyright law being inappropriately applied to digital transfers), even if the record companies were happy to use the internet in this fashion for publicity, they actually have to be seen to actively police the distribution of their content. It's nigh-on impossible to defend your IP if you don't.
So when someone starts selling knock-off merchandise on eBay, making hundreds of thousands of dollars, and you can't do anything about it because you "allowed" people to copy the IP all over the internet anyway, you're screwed.
The solution here* isn't to sit back and do nothing, but to decouple digital transfer from copyright law and come up with new legislation to cover it… but, well, good luck with that.
Of course, IANAL, but this is what I think.
Related: https://kera.name/articles/2006/12/well-we-would-have-lost-244m/
- I'll leave it as an exercise to the reader to determine whether the problem is in fact lost revenue and missed opportunities, or in fact something more general.
