4

I am currently looking for container that provides some inserting (insert or push_back) and some removing (erase, pop_back is not sufficient) methods, and that does not invalidate iterators nor pointers when calling these two methods.

More clearly, I want a set of elements where I can add an element (I do not care where), and where I can remove any element (so I do care where). In addition, I would have external pointers to specific elements, and I want them to remain valid if I add or remove an element from the set.

There are, to my knowledge, two standard containers that answer my needs : set and list. However, generally speaking, I do not like to use such containers for such simple needs. Since a list is involving pointers internally and does not provide random access to its elements, I think it is not a good choice. A set has random access to its elements, but is also involving pointers, and the random access itself is not done in constant time. I think that a set would be a better solution than a list, but I have thought about something else.

What about a simple vector that does not try to keep the elements contiguous when an element is removed ? When removing an element in the middle of this container, its position would be empty, and nothing else would happen. This way, no iterator or pointer would be invalidated. Also, when adding an element, the container would search for an empty position, and use a simple push_back if there is no such hole.

Obviously, since push_back can invalidate iterators with a vector, I would use a deque as the basis of implementation. I would also use some sort of stack to keep track of the holes from removing elements. This way, adding, removing, and accessing an element would be done in constant time, in addition to satisfying my no-invalidation needs.

However, there is still one problem : when iterating over this container or simply accessing an element by index we would need to take the holes into account. And that is where the problems start to surpass the advantages.

Hence my question : what do you think about my idea for that container ? More importantly, what would you use for my original problem, a set, a list or something else ? Also, if you have a nice and clean solution to the last problem (iterating over my container), feel free to show me.

Nelfeal
  • 12,593
  • 1
  • 20
  • 39
  • _"When removing an element in the middle of this container, its position would be empty, and nothing else would happen."_ Define _empty_ please. – πάντα ῥεῖ Feb 08 '15 at 09:29
  • Using an iterator to delete something - surely that iterator becomes invalid – Ed Heal Feb 08 '15 at 09:30
  • 3
    So you want something like [`stable_vector` in boost](http://www.boost.org/doc/libs/1_57_0/doc/html/boost/container/stable_vector.html)? – T.C. Feb 08 '15 at 09:32
  • @πάνταῥεῖ I mean that the memory at this position is still inside (owned by) the container, but it does not contain an element that can be accessed. – Nelfeal Feb 08 '15 at 09:52
  • @EdHeal I did not say anything about using an iterator to delete something. Of course, the iterators corresponding to removed elements are invalidated. That is not really a problem. – Nelfeal Feb 08 '15 at 09:54
  • @T.C. This seems to be exactly what I want, thanks ! (_Are the implementation details (or the source code) available somewhere ? I am curious about what kind of storage is used behind the interface._) Nevermind I found it. – Nelfeal Feb 08 '15 at 10:04
  • boost sources are publicly available https://github.com/boostorg/boost – Mats Petersson Feb 08 '15 at 10:08
  • @Mats At the moment, it [doesn't look like](https://github.com/boostorg/boost/tree/master/libs) the repository is correctly configured. –  Feb 08 '15 at 10:09
  • @remyabel: I noticed the same, not sure how/why. – Mats Petersson Feb 08 '15 at 10:13
  • This page tells how you download it... https://svn.boost.org/trac/boost/wiki/TryModBoost – Mats Petersson Feb 08 '15 at 10:14
  • 2
    stable_vector works like this: it has a vector of pointers that point to separately-allocated data nodes. Each node, in addition to the data element, has a back pointer that points back to the pointer inside the vector that points to the node. Iterators point to these nodes. When an element is inserted or erased, all back-pointers in the nodes that come after it are adjusted. I was too fast to declare something like that is not possible; I apologise. – n. m. could be an AI Feb 08 '15 at 10:34
  • "A `set` has random access to its elements" - not in the C++ usage of the term "random access" it doesn't. The term you may be looking for here is "free list" - that's what's usually said when we talk about maintaining a container with holes and keeping track of the holes elsewhere. – John Zwinck Feb 08 '15 at 12:00
  • @JohnZwinck You are right, a `set` does not have random access to its elements, things got a bit messed up in my head. What I meant is that it does not have linear time access, which is better than a `list` in my case. But anyway, the concept of stable vector is perfect for me. – Nelfeal Feb 08 '15 at 12:32

1 Answers1

6

Requirement 1: inserting (insert or push back) and some removing (erase, and not only the last element)

  • Compliant candidates: deque, forward_list, list, map, multi_map, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset, and vector

  • Eliminated candidates: array (no insert or push_back), queue, priority_queue and stack (no erase, only pop)

Requirement 2: does not invalidate iterators nor pointers when calling these two methods

  • Compliant candidates from also satifying requirement 1: forward_list, list, map, multi_map, set, multiset,
  • Eliminated on erase: deque (iterator remain valid only when erasing first element), and vector (all elements after the start of erasure)
  • Eliminated on insert: dequeue (in most of the cases), unordered_map, unordered_multimap, unordered_set and unordered_multiset (in case the growth requires a rehash) and vector (in case growth requires of reallocation)

Requirement 3: External pointers shall remain valid

Approximaletly the same result than for requirement 2. However unordered_map, unordered_multimap, unordered_set and unordered_multiset would satifsy this requirements because references to elements remain valid.

Requirement 4: Random access to elements

  • Complying candidates satisfying requirement 1 and 2: map and multimap
  • Almost complying candidates: set and multiset do not have a random access, but can satisfy it using member find() (O(logn))
  • Non compliant: list (although algorithm find() could provide a workaround in O(n)).

Answer to question 1: Which is better, a set or a list ?

It depends on your other requirements. In a set each value can only be stored once. If your elements are all unique , choose the set. If not you'd better opt for the list or the multiset.

I do not know the elements that you're storing, but is the whole element the search argument ? Or is there a key ? In the latter case, you'd really go for a map.

Answer to question 2: What about alternative container ?

I wouldn't opt for deque for your alternative.

If you can foresee the maximum number of elements, you could simply reserve enough capacity to avoid reallocation. (satisfying requirement 1, 3 and 4). If you have an "empty element" to represent holes, you could then also satisfy requirement 2. In worst case you could opt for a vector sotring your element and an indicator if it's valid.

If such a maximum is not determinable, I'd rather go for a map which proves to be flexible and satisfy all your requirements.

Christophe
  • 68,716
  • 7
  • 72
  • 138