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::insert 并检查结果的 bool 部分以查看是否indexed需要更新等）

并获得一个元素：

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

就是这样。一个问题当然是一旦一个对象在集合中，它就不能被修改。这是这里实现方式的一种泄漏，因为映射键是常量，原因很明显——但事实上，我认为无论如何它都是想要的，不管实现如何。如果你坚持没有重复，那么一旦一个对象在列表中，它就不能被修改，以防任何修改使它成为另一个对象的副本。

（另请注意，我在size_t这里使用有点作弊——我想std::vector<const T *>::size_type可能更准确——这主要是为了简洁起见！）