Is there a C++ structure like a map but instead of key to values I get a handle to a value?

user_10116440 0
Viewed 264

I need an structure kinda like a Map, but I dont care about the key value, only the value correspondent to the key.

On a map, I need to make things like this:

map[1] = "value1"
map[2] = "value2"

It gives me the responsibility to not choose coliding keys. I could solve this by doing:

let handle = randomValue();
map[handle] = "value1"

since I'm not concerned with the value of the key, I only need a handle to it. There's still the problem of coliding values if two random values are equal. I could write a little thing that checks if the key already exists in the map and generate a new one, but once the structure is kinda full, I'll get many collisions.

A List seems a good choice at first, but it's not, since if I remove one element, the indexes of all the others get rearranged.

Instead of implementing my own, I'd like to know if there is already something like this in C++: a map where you get a handle that makes it possible for you to access the value.

I just have another requirement: sometimes I actually need to pass this handle to Rust, so I think that if this handle can be translated to a number and back it'd be very useful.

std c++
4 Answers

IIUC, you want a container with the following features:

  • ability to add a new element and get a numeric handle to it
  • ability to remove an existing element

You do not need a mapping container here because you have no given key. But you want direct access from the handle. So what you need is a vector. I you never remove elements, you push_back items to the end of the vector and get their index as a handle. If you want to be able to quickly remove elements, I would use a special value for an empty slot and store empty indices in an auxilliary container, typically a stack or a queue. Here again I would use a vector because it is a very simple container and use it as a stack, but you could use a dequeue or a forward_list if you want to use it as a queue.

So to remove an element you mark it as empty and store its index in the empty list, and to add an element, you first try to get next slot from the empty list, and push_back it to the end of the primary vector if the list is empty.

Both addition and removal are in constant time.

user_35452730

One possibility: Your "map" is a std::list, and your "handle" is a std::list::iterator, which you can transform into a pointer (with &*it) when needed to transfer to Rust.

This works because references and iterators to nodes in a linked list are guaranteed to remain valid, even when adding or removing elements, or moving them between lists. Iterators are only invalidated when the corresponding element is removed.

user_65359150

You could wrap std::map into your own class which keeps track of the last used id:

#include <map>
#include <string>
#include <iostream>

template < typename T >
class AutoMap
{
public:
  typedef typename std::map<int, T>::iterator iterator;
  typedef typename std::map<int, T>::const_iterator const_iterator;

  int insert(const T& value)
  {
     int key = next++;
     map[key] = value;
     return key;
  }

  const T& operator [] (int key) const
  {
     auto it = map.find(key);
     if (it == map.end()) throw std::invalid_argument("invalid key");
     return it->second;
  }

  T& operator [] (int key)
  {
     auto it = map.find(key);
     if (it == map.end()) throw std::invalid_argument("invalid key");
     return it->second;
  }

  void erase(int key)
  {
      map.erase(key);
  }

  iterator find(int key)
  {
      return map.find(key);
  }

  const_iterator find(int key) const
  {
      return map.find(key);
  }

  iterator begin()
  {
      return map.begin();
  }

  iterator end()
  {
      return map.end();
  }

  const_iterator begin() const
  {
      return map.begin();
  }

  const_iterator end() const
  {
      return map.end();
  }
private:
  std::map<int, T> map;
  int next = 0;
};

int main()
{
    AutoMap<std::string> m;
    std::cout << m.insert("test") << "\n";
    std::cout << m.insert("test2") << "\n";
    std::cout << m[0] << "\n";
    std::cout << m[1] << "\n";
    m.erase(0);
    std::cout << (m.find(0) == m.end()) << "\n";
}
user_54943700

Sets

If you really don't care about the key, you might use std::set or std::unordered_set:

std::set<MyClass> set{MyClass(42), MyClass(32), MyClass(85)};
...
auto it = set.find(MyClass(32));

Maps

If you want to save somewhere the key and retrieve the element related to the key further in the code, std::map and std::unordered_map are good choices. You can use auto-increment key.

std::unordered_map<size_t, MyClass> map;
...
size_t counter=0;
map[counter++] = MyClass(42);
map[counter++] = MyClass(32);
...
auto it = map.find(1); // iterator to MyClass(32)

Note: several object can have the same key (collision) using std::multimapand std::unordered_multimap, objects with same key are not lost, but can be retrieved using iterators. This make the selection of the hash less critical.

Hashes

C++ provides several "hash" functions for typical types, which can be used for maps.

Reference to std::hash https://en.cppreference.com/w/cpp/utility/hash

user_9036510
Related