C++：需要索引集

Question

我需要一个按如下方式操作的索引关联容器：

• 初始为空，大小=0。

• 当我向其中添加新元素时，它会将其放置在索引 [size] 处，与向量的 Push_back 非常相似。它增加大小并返回新添加元素的索引。

• 如果该元素已存在，则返回其出现位置的索引。

Set 似乎是理想的数据结构，但我没有看到任何像获取这样的东西 查找操作的索引。在集合上查找返回元素的迭代器。

在这种情况下，使用 set.begin() 进行差异处理是正确的做法吗？

Answer 1

STL 中没有立即适用的数据结构，但实现此目的的一种直接且相当有效的方法是使用映射和指针向量。 map 将对象映射到它们在数组中的索引（以便检查对象是否存在是高效的，并且，如果对象已经存在，则索引立即可用），并且 vector 将索引映射到映射中的对象（以便通过索引检索对象是高效的）。

std::map<T,size_t> objects;
std::vector<const T *> indexed;

添加元素：（

size_t add_element(const T &v) {
    std::map<T,size_t>::iterator it=objects.find(v);
    if(it==objects.end()) {
        it=objects.insert(std::map<T,size_t>::value_type(v,objects.size())).first;
        indexed.push_back(&it->first);
    }
    return it->second;
}

根据个人风格明显的改变可能是存储一个map迭代器的向量，每次使用map::insert并检查结果的bool部分以查看indexed是否需要更新等）

并获取一个元素：

const T &get_element(size_t index) {
    return *indexed[index];
}

就是这样。当然，一个问题是，一旦对象进入集合，就无法对其进行修改。这是这里实现方式的一种泄漏，因为映射键是常量，原因很明显——但事实上，我认为，无论实现如何，这都是我们想要的。如果您坚持不存在重复项，那么一旦某个对象位于列表中，它就不能被修改，以防任何修改都会使其成为另一个对象的重复项。

（另请注意，我在这里使用 size_t 进行了一些作弊——我认为 std::vector::size_type 可能更准确——这主要是为了简洁！）