1

I need an indexed associative container that operates as follows:

  • initially empty, size=0.

  • when I add a new element to it, it places it at index [size], very similar to a vector's push_back. It increments the size and returns the index of the newly added element.

  • if the element already exists, it returns the index where it occurs.

Set seems the ideal data structure for this but I don't see any thing like getting an index from a find operation. Find on a set returns an iterator to the element.

Will taking the difference with set.begin() be the correct thing to do in this situation?

4

1 回答 1

5

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

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

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

于 2010-04-01T16:54:45.743 回答