代码之家 › 专栏 › 技术社区 › Roel

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

stl data-structures c++

Roel · 技术社区 · 16 年前

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

std::map<size_t, TObject>

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

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

(当然,我可以,而不是在我的映射中取最高的键并添加一个,而是每次遍历映射并搜索第一个可用的键,但这会将复杂性从O(1)降低到O(n),如果API是一个简单的,那就更好了

size_t new_key = m_Container.insert(object);

5 回复 | 直到 16 年前

Manuel 16 年前

如果你不打算分配超过 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);

MSalters 16 年前

我不确定你到底想从你的身份证里得到什么。碰巧,每个对象都已经有了有

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

Alexey Malistov 16 年前

创建 std::set<key_type> removed_keys; removed_keys 移除的钥匙 否则创建一个新密钥。

Community Mohan Dere 5 年前

为什么不只用向量呢?

std::vector<TObject> m_Container;

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

如果你有一些其他的使用特征,比如:(元素可以被移除),(我们在大块中插入元素),(我们不经常插入元素)等等,这些都是有趣的因素,可能会改变人们给出的建议。

您提到要搜索未使用的元素ID。这表明您可能正在删除元素,但我看不到任何明确的要求或用法,其中元素被删除。

看看上面的代码:

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

这不是你认为的那样。
它也相当于:

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

邮递减量运算符修改左值。但表达式的结果是原始值。因此,您将运算符->应用于end()返回的值。这(可能)是未定义的行为。

见标准:

后缀++表达式的值是其操作数的值。

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;
}

Thomas Matthews 16 年前

你需要一个理由吗 std::map 不删除 键,值 一对?

一种方法是替换具有虚拟值或占位符值的部分。从长远来看,问题是虚拟值可以从 标准::地图 只要钥匙还在。每次被访问。

因为您想要维护一个没有值的键,所以很可能必须编写自己的容器。当客户机访问没有值的键时,您将特别需要设计代码来处理这种情况。

使用标准容器和没有值对的密钥似乎没有性能提升。但是,那里可以