Using std::map::extract to modify key

Question

My implementation uses std::map to store data. When I started my code it seemed like the best option. Now I came to a point where I have to change the key values of all objects inside the map.

The problem is that each object points to another object inside the map:

class AND : public node{
    vector <node*> inputs;
    vector <node*> outputs;
}

And the map is declared like this:

map<unsigned int, AND> all_ANDs;

My question is: If I use map::extract from C++17 to modify the key values in all_ANDs map, will my pointers (E.g. the ones inside the attribute inputs) keep pointing to the right places?

In other words: If I change the value of "first" element with extract, the address of "second" will keep intact?

I noticed from this link that the string "papaya" stays the same (and works gracefully). But I wanted to be sure about pointers.

Answer 1

YES The reference you have already quoted in your posts clearly states that no elements are copied or moved. (This assumes that node in your code snippet does not refer to map::node_type).

The same holds for the insert operation of the map-node (after modifying its key):

If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid. (since C++17)

However, accessing the object between extract()ion and re-insert()ion has undefined behaviour and its address taken whilst in the extracted state is of limited use. Quoting from the standard:

The extract members invalidate only iterators to the removed element; pointers and references to the removed element remain valid. However, accessing the element through such pointers and references while the element is owned by a node_­type is undefined behavior. References and pointers to an element obtained while it is owned by a node_­type are invalidated if the element is successfully inserted.

Explanation

Essentially, a map<> is implemented as a tree of nodes, each holding a key and T (which are exposed as pair<const Key, T> to the user). Nodes are allocated (typically) on the heap and the address of your object is related to that of a node. map::extract() un-links a node from its tree and returns a node handle (an object holding a pointer to a map node), but AFAIK the node itself is not re-allocated, moved, or copied. Upon map::insert(handle), the node is re-linked into the tree according to its (new) key. Again, this involves no re-allocation, move, or copy of the node.

Remark

The above is a rough sketch. How things are actually done is likely more complex and also implementation defined. As explained here a node_handle does allow to alter the key through the member function

Key &node_handle::key() const;

How this is done under the hood is not specified and I speculate that the implementation uses a union or some cast to allow this. Of course, the map has to present to users a pair<const Key,T> in order to prevent them from changing the key and hence breaking the map, but this is not of any concern for an element extracted from the map.

Answer 2

Your map holds actual AND objects, not pointers to objects. So, if the AND* pointers stored inside your vectors are pointing at the map's AND objects, then those pointers WILL become invalid once those objects are erased from the map.

However, extraction merely unlinks a specified node from the map, the node and thus its key and value are still valid in memory. The node can be re-inserted into a map without affecting the addresses of the node's key and value. In this regard, the pointers in the vectors WILL NOT become invalid (although it is undefined to dereference them while the node is detached from the container).

Another option is to change your map to hold AND* pointers instead. Or better, consider using std::shared_ptr<AND> in the map and std::shared_ptr<node> in the vectors, instead of raw pointers. Then it won't matter whether the map entries are erased or extracted, the AND objects will remain valid as long as there are active shared_ptr references to them.

Answer 3

My above answer addresses your immediate question. However, as I have suggested in a comment, this appears to be a XY problem. What I suspect:

1. You have some structure of AND objects which are interlinked via their inputs and outputs fields. This linkage must not be broken by any re-allocation, so you cannot store them in a growing vector<AND> with re-allocation.

2. You also want to order these objects according to some key and have therefore stored them in a map<Key,AND>, which indeed does not re-allocate when grown.

3. You now want to order them according to another key (and/or change all the keys).

(If you're actually are not interested in ordering but merely in finding your objects by their key, you should have used unordered_map instead of map, which supports find() in O(n) rather than O(log(n)) operations.)

I suggest a different layout of your data:

1. You store your AND objects in a way that allows growing their number without re-allocation. An obvious choice here is deque<AND>, since

   insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements

   You may also make AND non-copyable and non-movable, ensuring that once allocated their address never changes (and pointers to them remain valid until destruction).

2. You can support any find-by-key or order-by-key operations by actually working on pointers to the stored objects, either by sorting a vector of pair<key,AND*> or by using a map<key,AND*> or unordered_map<key,AND*>. You can even simultaneously have various keys per object (and a map for each).

3. When you must re-key all objects, simply forget the old map and make a new one: since the map only stores pointers and not the objects, this does not affect your linkages.