通过迭代器获取集合元素的"索引"

Question

这个问题适用于 std::set 和 std::unordered_set。

我有一个指向集合中元素的迭代器。我想使用这个迭代器根据元素在集合中的位置获取一个“索引”。

例如，我的集合的索引如下：

int index = 0;

for(MySetType::iterator begin = mySet.begin(); begin != mySet.end(); begin++)
{
    cout << "The index for this element is " << index;
    index++;
}

我尝试使用迭代器进行算术运算，但是它不起作用：

int index = mySetIterator - mySet.begin();

有没有办法使用迭代器来获取集合中元素的索引值？

- user974967

---

获取两个迭代器之间的“距离”的正确方法是使用std::distance函数。但是，在使用它之前，请先阅读Jack的答案。 - Some programmer dude

Answer 1

使用STL distance，即std::distance(set.begin(), mySetIterator)

请注意:

返回first和last之间的元素数量。如果通过（可能重复）递增first无法到达last，则行为未定义。

备注: 复杂度为线性；

但是，如果InputIt还满足LegacyRandomAccessIterator的要求，则复杂度是常数。

- dreamcrash

Answer 2

std::set和set::unordered_set是关联容器，而不是序列容器，因此索引的概念本身并没有太多意义。

如果您需要检索关联容器的索引，则应该更改设计（即使因为在这些容器中，由于没有最近插入元素的最小或最大概念，因此这些索引可能会发生变化）。

- Jack

---

我只需要一个“索引”将元素（迭代器）链接到集合项，以便可以写入文件。换句话说，我有一个大型的集合迭代器列表，不想将相同的冗余集合元素数据写入文件。我宁愿将唯一的集合元素写入一个文件，然后为每个元素编制索引，将它们链接回特定的集合项。 - user974967

索引的概念非常有意义，例如 set<ChessPlayer> players; int RankOf(ChessPlayer player, const set<ChessPlayer>& players); players.insert(newPlayer); players.erase(retiredPlayer)那么你如何实现一个高效的 RankOf 函数呢？ - mercury0114

Answer 3

std::set仅提供双向迭代器，这意味着您无法使用operator +（或-）完成您尝试的操作。这些仅适用于随机访问迭代器，例如std::vector提供的迭代器。

您需要使用std::distance获取“索引”，并使用std::advance从集合的开头移动到结尾。

auto distance = std::distance(mySet.begin(), someIterator);
auto it = mySet.begin();
std::advance(it, distance);

assert(it == someIterator);

- moswald

---

在集合中，distance()函数的时间复杂度是多少？它是O(1)吗？ - Prince

不行，因为set只有一个双向迭代器，所以distance必须遍历整个列表。如果它有随机访问迭代器，那么它可以是O(1)的。 - moswald