CODEWITHSUNDEEP
c++
packetie
packetie

Reputation: 5069

Remove a node in unordered_map based on the address fof a node

Given a unordered_map object, wonder if it's possible to erase a node by the reference (or address) of a node. In another word, in the following code snippet, wonder if it's possible to remove the node for "UK" by the address of variable x or something similar. 

std::unordered_map<std::string,int> mymap;

// populating container:
mymap["US"] = 10;
mymap["UK"] = 9;
mymap["US"] ++;
mymap["France"] = 8;
int &x = mymap["UK"];

This is useful in an app, where I need to keep track of the frequencies of various strings in a time interval (say, the last 3 hours). The strings can have size from a few bytes to thousands of bytes. Each time a string expires (based on its arrival time and size of time interval), I will reduce the frequency for this string. If the frequency is 0, I will need to remove the node for the string. Don't want to allocate space to store the strings in timer queue, that would be a waste of space.

Any ideas? Thanks.

Upvotes: 0

Views: 622

Answers (3)

Jack
Jack

Reputation: 133567

unordered_map supports two erase overloads:

  • by key
  • by iterator

There is no such "erase through address of mapped value". Basically you have two ways of doing it:

int main() {
    unordered_map<string, int> data;

    data["UK"] = 10;
    data["UK"]++;
    data["US"] = 8;

    cout << data.size() << endl;
    auto it = data.find("UK");
    data.erase(it);
    cout << data.size() << endl;
    data.erase("US");
    cout << data.size() << endl;
    return 0;
}

Using the iterator is more efficent because you can obtain the value (through second member) and together erase it without the need to do two lookups.

By your comment you can't take the address of an iterator which is obtained by value on a local variable. That would yield a local address in any case, but the standard guarantees you that iterators in an unordered_map are not invalidated upon insertion and on delete only the affected one is invalidated, so storing them somewhere is allowed, something like:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
using map_type = unordered_map<string, int>;

map_type data;
vector<map_type::iterator> timer_queue;

void timeTick()
{
  for_each(begin(timer_queue), end(timer_queue), [](map_type::iterator& it) {
    --it->second;

    if (it->second == 0)
    {
      cout << "pair " << it->first << " has expired" << endl;
      data.erase(it);
      cout << "map size: " << data.size() << endl;
    }
  });
}

template<typename... Args> void addElement(Args... args)
{
  auto it = get<0>(data.emplace(args...));
  timer_queue.push_back(it);
}

int main() {

  addElement("IT", 5);
  addElement("US", 10);
  addElement("UK", 8);

  while (!data.empty())
  {
    cout << "time tick" << endl;
    timeTick();
  }

    return 0;
}

Upvotes: 2

Jeremy Friesner
Jeremy Friesner

Reputation: 73051

I wouldn't recommend this for production code, but if you are okay with making the assumption that your STL's implementation of unordered_map is storing keys and values together in a struct, and that therefore the memory locations of the key and value in a given key/value pair will always be at a fixed offset from each other, you could use the GetKeyFromValue() function below to retrieve the key associated with your reference-to-a-value. Then you could use that pass that key in to erase() or whatever, as usual.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

/** Given a reference to a value in (map), returns a reference to the associated key.
  * @param map Reference to the unordered_map object.
  * @param value Reference to a value in (map).  If this reference is to some object that is
  *              not actually stored in (map), then this function's behavior is undefined, so be careful!
  * @returns A reference to the key associated with (value).
  */
template<typename KeyType, typename ValueType> const KeyType & GetKeyFromValue(const unordered_map<KeyType, ValueType> & map, const ValueType & value)
{
   if (map.size() == 0) throw invalid_argument("Called GetKeyFromValue() on an empty map!?");

   auto it = map.begin();
   const KeyType   * firstKey = &it->first;
   const ValueType * firstVal = &it->second;

   const char * cFirstKey = reinterpret_cast<const char *>(firstKey);
   const char * cFirstVal = reinterpret_cast<const char *>(firstVal);
   ptrdiff_t diff = cFirstVal-cFirstKey;

   const char * cUserVal = reinterpret_cast<const char *>(&value);
   cUserVal -= diff;
   return *(reinterpret_cast<const KeyType *>(cUserVal));
}

// Quick unit test for the above
int main(int, char **)
{
   unordered_map<string, int> mymap;
   mymap["US"] = 10;
   mymap["UK"] = 9;
   mymap["US"]++;
   mymap["France"]=8;

   int & x = mymap["UK"];
   const string & uk = GetKeyFromValue(mymap, x);
   cout << "keyForX=[" << uk << "]" << endl;

   int & y = mymap["France"];
   const string & france = GetKeyFromValue(mymap, y);
   cout << "keyForY=[" << france << "]" << endl;

   return 0;
}

Upvotes: 0

Mark B
Mark B

Reputation: 96241

You can't do it from the value itself, but you can use std::map::find to get an iterator to the interesting item in the map and delete the iterator's key/value pair directly.

Upvotes: 0

Related Questions