I need to insert values into std::map (or it's equivalent) to any free position and then get it's key (to remove/modify later). Something like:
std::map<int, std::string> myMap;
const int key = myMap.insert("hello");
Is it possibly to do so with std::map or is there some appropriate container for that?
Thank you.
In addition to using a set, you can keep a list of allocated (or free)
keys, and find a new key before inserting. For a map indexed by
int, you can simply take the last element, and increment its key. But
I rather think I'd go with a simple std::vector; if deletion isn't
supported, you can do something simple like:
int key = myVector.size();
myVector.push_back( newEntry );
If you need to support deletions, then using a vector of some sort of
"maybe" type (boost::optional, etc.—you probably already have
one in your toolbox, maybe under the name of Fallible or Maybe) might be
appropriate. Depending on use patterns (number of deletions compared to
total entries, etc.), you may want to search the vector in order to
reuse entries. If your really ambitious, you could keep a bitmap of the
free entries, setting a bit each time you delete and entry, and
resetting it whenever you reuse the space.
push_back the vector as above), or else use an index popped off the stack.
You can add object to an std::set, and then later put the whole set into a map. But no, you can't put a value into a map without a key.
The closest thing to what you're trying to do is probably
myMap[myMap.size()] = "some string";
The only advantage this has over std::set is that you can pass the integer indexes around to other modules without them needing to know the type of std::set<Foo>::iterator or similar.
prec(myMap.end())->first (assuming the map isn't empty) would solve that (and of course, if the application doesn't require deletions, your trick works out of the box).It is impossible. Such an operation would require intricate knowledge of the key type to know which keys are available. For example, std::map would have to increment int values for int maps or append to strings for string maps.
You could use a std::set and drop keying altogether.
int, so we know how to do it.
std::vector approach won't work. In that case, you could just use the index of the last element + 1 for a new element. Or you could iterate to find a hole (possibly caching the results of the iteration as a range, so you don't have to iterate every time). Or maybe something else---as you say, the problem is seriously underspecified.If you want to achieve something similar to automatically generated primary keys in SQL databases than you can maintain a counter and use it to generate a unique key. But perhaps std::set is what you really need.
map, being usually implemented as an RB tree, doesn't have a "default key" associated with any free slot. What exactly are you trying to achieve?map<uint32_t>you have over 4 billion "unoccupied keys"...