将唯一 ID 映射到对象的数据结构

Question

我正在寻找一种 C++ 数据结构，它可以让我将对象与唯一的数值（键）关联起来，并且在从容器中删除相应的对象后将重新使用这些键。所以它基本上是一种混合映射/队列结构。我当前的实现是 a

std::map<size_t, TObject>

并且我插入这样的对象：

 size_t key = (m_Container.end()--)->first + 1;
 m_Container[key] = some_object;

这对于我的目的来说效果很好（我永远不会分配超过 size_t 的对象）；但我仍然想知道是否有更专门的容器可用，最好已经在 stl 或 boost 中，或者有一种方法可以使用另一个容器来实现此目标。

（当然，我可以，而不是每次都遍历地图并搜索第一个可用的键，而不是获取地图中最高的键并添加一个，但这会将复杂性从 O(1) 降低到 O(n) 而且它也会如果 API 很简单就好了

size_t new_key = m_Container.insert(object);

）。

有什么想法吗？

Answer 1

如果您永远不会分配超过 size_t 个键，那么我建议您只需使用静态计数器：

size_t assign_id()
{
    static size_t next_id;
    return next_id++;
}

如果您想要一个不错的 API：

template<class Container>
size_t insert(Container & container, TObject const & obj)
{
     container.insert(obj);
     return assign_id();
}

std::set<TObject> m_Container;
size_t new_key = insert(m_Container, object);

Answer 2

我不确定你到底想从你的 ID 中得到什么。碰巧的是，每个对象已经拥有一个唯一的ID：它的地址！不存在具有相同地址的两个不同对象，并且对象的地址在其生命周期内不会改变。

std::set 通常将其 T 值存储为较大节点的成员，而不是独立对象。尽管如此，T 子对象永远不会移动，因此它们的地址也是稳定的、唯一的标识符。

Answer 3

创建 std::setreturned_keys; 已删除的键。如果 removed_keys 不为空，则使用 removed_keys 中的密钥，否则创建一个新密钥。

Answer 4

为什么不直接使用向量呢？

std::vector<TObject> m_Container;

size_t key = m_Container.size();
m_Container.push_back(some_object);

当然，如果您有其他使用特征，这可能完全没用。但由于您只描述了插入和对密钥的需求（因此提取），因此很难给出任何其他明确的答案。但是从这两个要求来看， std::vector<> 是这样的：应该可以正常工作。

如果您有其他一些使用特征，例如：（可以删除元素）、（我们在大块中插入元素）、（我们不经常插入元素）等，这些将是有趣的事实，可能会改变人们给出的建议。

您提到您想要搜索未使用的元素 ID。这表明您可能正在删除元素，但我没有看到删除元素的任何明确要求或用法。

查看上面的代码：

size_t key = (m_Container.end()--)->first + 1;

这并没有按照您的想法进行。
它也是等价的：

size_t key = m_Container.end()->first + 1;
m_Container.end()--;

post减量运算符修改左值。但表达式的结果是原始值。因此，您正在应用运算符 ->到 end() 返回的值。这（可能）是未定义的行为。

参见标准：

节：5.2.6 递增和递减
postfix ++ 表达式的值是其操作数的值。

m_Container.end()--  // This sub-expresiion returns m_Container.end()

选择：

#include <vector>

template<typename T>
class X
{
    public:
        T const& operator[](std::size_t index) const    {return const_cast<X&>(*this)[index];}
        T&       operator[](std::size_t index)          {return data[index];}
        void        remove(std::size_t index)           {unused.push_back(index);}

        std::size_t insert(T const& value);
    private:
        std::vector<T>                  data;
        std::vector<std::size_t>        unused;
};

template<typename T>
std::size_t X<T>::insert(T const& value)
{
    if (unused.empty())
    {
        data.push_back(value);
        return data.size() - 1;
    }
    std::size_t result  = unused.back();
    unused.pop_back();
    data[result]    = value;
    return result;
}

Answer 5

您是否需要 std::map 才能不删除键、值对？

这听起来像是一次过早优化的尝试。

一种方法是用虚拟或占位符值替换值部分。从长远来看，问题是只要密钥存在，就可以从 std::map 中提取虚拟值。每次访问 std::map 时，您都需要添加对虚拟值的检查。

因为您想要维护一个没有值的键，所以您很可能必须编写自己的容器。您尤其需要设计代码来处理客户端访问没有值的密钥的情况。

看起来使用标准容器和没有值对的键没有性能提升。然而，就记忆而言，可能有所收获。你的问题会减少动态内存的碎片；因此不必为同一个键重新分配内存。您必须做出权衡。