adding pointers to keys in map in map

Question

struct ndptr_t {
    const pnode *ptr;

    ndptr_t(const pnode* _p = nullptr) : ptr(_p) {}

    ~ndptr_t() {
        // if no ndptr_t used outside map nid, clear nid
    }
};

static std::map<pnode, ndptr_t> nid;
 
pnode* ptrof(pnode &pn) {
    auto r = nid.emplace( pn, ndptr_t(nullptr) );
    if (r.second) r.first->second = ndptr_t(&(r.first->first));
    return r.first->second;
}

Above code tries to store pointer to a key in the map as a value against the key in the map.

Is it safe to assume that the pointers to the key remain valid through the lifetime of the map nid as long as the key itself is not removed or erased?

I implemented this and noted that it works.

Answer 1

Yes, std::map<K, T> is a node-based container in which each element (which is an object of type value_type, i.e. pair<const K, T>, is a separately allocated "node". Elements are never reallocated by the internal operation of a map, so the address of the entire element (both key and mapped data) are stable, and only invalidated by either erasing the element from the map or destroying the map.

The same is true for set, multiset, multimap, and the unordered_ versions thereof. (This is often a complaint about the standard library, since the node-based design is rather bad for performance, compared to a contiguous storage design that would require moving data around. However, if you want node stability, then it's precisely what you need.)

Additionally, as of C++17 (so not applicable to your question), you can also extract nodes and insert them into other maps, and the allocation is retained.

By the way, you can use the map API to simplify your code and make it more efficient by avoiding two repeated, completely unnecessary, traversals (since you already know the result!):

const pnode* ptrof(pnode &pn) {
    auto r = nid.emplace(pn, nullptr);
    if (r.first->second == nullptr) {
        r.first->second = &r.first->first;
    }
    return r.first->second;
}

Note that the map type needs to be map<pnode, const pnode*>, though (mind the const), since the key is const.