21

Given an STL container (you may also take boost::unordered_map and boost::multi_index_container into account) that is non-contiguous, is it guaranteed that the memory addresses of the elements inside the container never changes if no element is removed, (but new ones can be added)?

e.g.

class ABC { };
//
//...
//
std::list<ABC> abclist;
ABC abc;
abclist.insert(abc);
ABC * abc_ptr = &(*abclist.begin());

In other word will abc_ptr be pointed to abc throughout the execution, if I do not remove abc from abc_list.

I am asking this because I am going to wrap the class ABC in C++/Cli, so I need pointers to the ABC instances in the wrapper class. ABC is a simple class and I want the container to handle the memory. If the answer is no then I will use std::list<ABC*>.

Matt
  • 22,721
  • 17
  • 71
  • 112
ali_bahoo
  • 4,732
  • 6
  • 41
  • 63

4 Answers4

30

std::list, std::set, and std::map guarantee that the iterators (including simple pointers) will not be invalidated when a new element is added or even removed.

Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
  • 1
    OP specified a non-contiguous container, so vector is out of the running. Also, was something supposed to come after "See"? – Matt K Mar 03 '11 at 14:44
  • 5
    And `deque` guarantees it for adding elements at the ends, which might be good enough for this sort of use. – Steve Jessop Mar 03 '11 at 15:09
5

As Armen mentioned std::list, std::set, and std::map are guaranteed to only invalidate the removed iterator. In the case of boost::unodered_map, the modifiers may indeed invalidate iterators.

http://www.boost.org/doc/libs/1_38_0/doc/html/boost/unordered_map.html

milky414
  • 306
  • 2
  • 3
  • Thanks for the link. Yes according to documentation, the modifiers may indeed invalidate iterators, also it says `Pointers and references to elements are never invalidated.` which I need to know. Also `boost::multi_index::hashed_unique` index is implemented like `boost::unordered_map`. – ali_bahoo Mar 03 '11 at 15:11
4

The C++ Standard places stringent rules on the validity of references / iterators. For each container, each method documents which elements may be moved (invalidating references and iterators).

The Node Based Containers: list, map, set, multimap and multiset guarantee that references and iterators to elements will remain valid as long as the element is not removed from the container.

Your use case is therefore one of the corner cases where using a list for storage is good, because of the invalidation guarantees that list offer.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
-1

I think it's better to use std::list <shared_ptr <ABC> > instead of passing a pointer. It's good practice to delegate memory management (see scott meyers effective c++)

This has mulitple advantages:

  • you can share them and pass them without the headache of freeing them
  • garbage collection of your pointers
  • you don't pass a pointer in the first place
count0
  • 2,537
  • 2
  • 22
  • 30
  • The code in the question is not handling memory management manually. Object lifetime is managed by the container. Note that the only pointers involved are *references* into objects that are handled by the container. – David Rodríguez - dribeas Mar 03 '11 at 14:50
  • You missed the point here: the OP requires a pointer (for a foreign interface), and he does not perform manual memory management... your solution does offer any bonus. – Matthieu M. Mar 03 '11 at 14:51
  • This is highly irrelevant to my question. With or without shared pointer, I ask whether the memory address of an element changes. – ali_bahoo Mar 03 '11 at 14:52