是否有像映射这样的 C++ 结构，但我得到的不是值的键，而是值的句柄？

Question

我需要一个类似于Map的结构，但我不关心键值，只关心键对应的值。

在地图上，我需要做这样的事情：

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

它给了我不选择冲突键的责任。我可以通过这样做来解决这个问题：

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

因为我不关心密钥的值，所以我只需要它的句柄。如果两个随机值相等，仍然存在值冲突的问题。我可以写一些东西来检查映射中是否已经存在键并生成一个新键，但是一旦结构有点满，我就会遇到很多冲突。

一开始列表似乎是个不错的选择，但事实并非如此，因为如果我删除一个元素，所有其他元素的索引都会重新排列。

我不想自己实现，而是想知道 C++ 中是否已经有这样的东西：一个映射，您可以在其中获得一个句柄，使您可以访问该值。

我还有一个要求：有时我实际上需要将这个句柄传递给 Rust，所以我认为如果这个句柄可以转换为数字并返回，那将非常有用。

Answer 1

一种可能：你的"map"是一个std::list，你的"handle"是一个std::list::iterator，你可以把它转换成一个指针（用&*it) 当需要转移到 Rust 时。

这是有效的，因为对链表中节点的引用和迭代器保证保持有效，即使在添加或删除元素或在列表之间移动它们时也是如此。迭代器只有在相应的元素被移除时才会失效。

Answer 2

IIUC，您想要一个具有以下功能的容器：

能够添加新元素并为其获取数字句柄
能够删除现有元素

您在这里不需要映射容器，因为您没有给定的密钥。但是您希望从句柄直接访问。所以你需要的是一个向量。我从不删除元素，你 push_back 项目到向量的末尾并将它们的索引作为句柄。如果您希望能够快速删除元素，我会为空槽使用一个特殊值，并将空索引存储在辅助容器中，通常是堆栈或队列。在这里我会再次使用矢量，因为它是一个非常简单的容器并将其用作堆栈，但如果您想将其用作队列，则可以使用出队或 forward_list。

因此，要删除一个元素，您将其标记为空并将其索引存储在空列表中，并添加一个元素，您首先尝试从空列表中获取下一个位置，然后 push_back 它到如果列表为空，则主向量的末尾。

添加和删除都在常数时间内。

Answer 3

您可以将 std::map 包装到您自己的 class 中，这样可以跟踪上次使用的 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";
}

Answer 4

套

如果你真的不关心密钥，你可以使用 std::set 或 std::unordered_set:

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

地图

如果你想把key保存在某个地方，并在代码中进一步检索与key相关的元素，std::map和std::unordered_map是不错的选择。您可以使用自增键.

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.

哈希值

C++ 为典型类型提供了几个 "hash" 函数，可用于映射。

参考std::hash https://en.cppreference.com/w/cpp/utility/hash

是否有像映射这样的 C++ 结构，但我得到的不是值的键，而是值的句柄？

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

c++

std

套

地图

哈希值