0

Is there C++ container that guarantees a fixed pointer for items what ever changes happened?

For example, std::vector may change the address of an item if a push_back or erase happened. So the address of the item will be rubbish after this change. So, is there a container that does not change items address in memory while the container changing?

P.S. compile time size or fixed size is not an option

EDIT: As @Joachim Pileborg stated it is XY problem or in actual it is XYZ one! The Z is this question. The Y is the following one: Keeping vector of iterators of the data

The original one:

I have data which is set of Points(x,y). This Points will go into a pipeline. The result should be:

  • set of Lines
  • set of Points for each line... in other word, set of set of Points

I do not want to copy the point and return them by value. I know a Point with just x and y is nothing to worry about copying it. However, in my it is templated problem which may be much bigger object in some cases.

Community
  • 1
  • 1
Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160
  • [`array`](http://en.cppreference.com/w/cpp/container/array). But that's fixed size, of course. – DevSolar Nov 18 '15 at 11:51
  • There's `std::array` but I doubt it will really fit your needs. – πάντα ῥεῖ Nov 18 '15 at 11:51
  • thanks.. Unfortunately not an option – Humam Helfawi Nov 18 '15 at 11:52
  • 2
    If you need dynamic sizing, [`list`](http://en.cppreference.com/w/cpp/container/list) / [`forward_list`](http://en.cppreference.com/w/cpp/container/list) spring to mind. ("Adding, removing and moving the elements within the list, or across several lists, does not invalidate the iterators currently referring to other elements in the list.") – DevSolar Nov 18 '15 at 11:52
  • Check e.g. [this container reference](http://en.cppreference.com/w/cpp/container), I'm sure there might be a couple there that satisfies your requirement. But I personally think that you might want to check or rework the design, so you don't actually need such a requirement. – Some programmer dude Nov 18 '15 at 11:52
  • 3
    You can use `std::map` with pointers as the key. – The Apache Nov 18 '15 at 11:52
  • 1
    A linked list should work, or a map with pointers as keys? – Netwave Nov 18 '15 at 11:53
  • 2
    All node-based containers have this property. – Kerrek SB Nov 18 '15 at 11:53
  • [std::list](http://www.cplusplus.com/reference/list/list/) maintains iterator validity unless an item is erased (this includes clearing the entire list). In that case ONLY the iterator pointing to the erased item becomes invalid. – Mohamad Elghawi Nov 18 '15 at 11:54
  • Check `std::stack ` – Claudio Nov 18 '15 at 11:54
  • By the way, this is a very fine example of [the XY problem](http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem): You have a solution you want to use, and ask us for help fixing your solution. But you don't tell us what the *actual* problem is, there might be other (and possibly even better) solutions. – Some programmer dude Nov 18 '15 at 11:57
  • @JoachimPileborg edited! – Humam Helfawi Nov 18 '15 at 12:05
  • You could store all the points in a single vector and address them by indexes. A line would be a set of indexes (another vector). An address of a variable is a low-level concept. I advise avoiding it when solving tasks that say nothing about addresses. You can use better concept: indexes. – AlexStepanov Nov 18 '15 at 12:09
  • @HumamHelfawi about your source problem: may a point be part of several lines or not? Must the original container remain unmodified? If the original container may be modified, then is the iterator validity important only because the original container is modified during the partitioning, or is the validity also important if the original container is left unmodified during the partitioning? If the original container is allowed to be modified and point can only be part of a single line, then is it ok to *move* the elements instead of copying or must that be avoided as well? – eerorika Nov 18 '15 at 12:44
  • Point is belong to one and only one line. source must not be touched. container is not modified a copy of it is modified. – Humam Helfawi Nov 18 '15 at 12:46
  • @HumamHelfawi can you be more specific about the validity of the iterators. If you later remove an element from the original container, then what should happen to the iterator/pointer/whatever in the partition set? – eerorika Nov 18 '15 at 13:06
  • it should not be affected (no shift should happen for example). – Humam Helfawi Nov 18 '15 at 13:08
  • @HumamHelfawi but the iterator in the partition set can't possibly be valid if it pointed to an element that was later removed from the original container. Is that ok? – eerorika Nov 18 '15 at 13:14
  • an element that i have iterator to it should not be deleted. I mean I deleted elements that I do not care about pointing to them anymore. But this deletion should not affect other elements addresses. And many thanks for your patient in diving into my problem details – Humam Helfawi Nov 18 '15 at 13:16

2 Answers2

4

Is there C++ container that guarantees a fixed pointer for items what ever changes happened?

If by what ever you include erasing the item that is pointed to, then only std::array is such container because you cannot remove elements from it.

If you mean that anything else but erasing the pointed item, then all node based containers have that property, as pointed out in the comments. Such standard containers are std::list, std::forward_list, std::map std::multimap, std::set and std::multiset. Erasing or modifying (if modifying is possible) an item from any of those containers does not invalidate iterators nor pointers or references to elements.

Also, if you store pointers in std::vector or other containers that don't have the property, then the stored pointer to the object still remains valid even though indices, pointers, references and iterators to the stored pointer become invalid. There is a stable_vector template in boost that stores pointers to the element and does not invalidate iterators or pointers to the element when the container is modified. The indices do of course become invalid if elements are removed and obviously it doesn't have the advantage of contiguous memory.

About your original problem:

Given your requirements, returning a set of set of iterators/pointers to the original container seems indeed appropriate. And if the iterators must remain valid when the original container is be modified later, say by adding more points or by removing points that are not referred by any partition, then the type of the original container must indeed be such as discussed on this page.

Mike Kinghan
  • 55,740
  • 12
  • 153
  • 182
eerorika
  • 232,697
  • 12
  • 197
  • 326
0

You can use a std::map with the pointers as the key and since the keys are unique, no matter whatever changes you do, the addresses will not change.

eg: std::map<int*, list<int>> x;

The Apache
  • 1,076
  • 11
  • 28