C++:需要索引集

Question

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

• 初始为空，size=0。

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

• 如果该元素已经存在，则返回它出现的索引。

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

在这种情况下，用 set.begin() 求差是正确的做法吗？

Answer 1

在 STL 中没有直接适用于此的数据结构，但实现此目的的一种直接且相当有效的方法是使用映射和指针 vector 。 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;
}

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

获取一个元素:

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

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

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