c++ - 用于访问集合的已排序子集的数据结构 C++

Question

我有一组值 V，它们由它们的索引 I 访问——即 i->V[i]。我需要根据值V[i](例如从大到小)迭代这些。此外，我有原始索引 I_1, I2,..., I_N 的子集，我需要以相同的顺序(从大到小)访问它们的相应值。

这里使用的正确数据结构和过程是什么？我已经为此苦苦挣扎了一段时间，所以非常感谢您的帮助。

请注意，值 (V[i]) 会不断更新，并且始终通过索引 i 进行访问。如果我使用 set 来表示这些值，那么我需要删除更新后的元素并将其插入回去并提示放置它的位置(很可能它靠近它之前的位置集)。但是集合只包含V，并且不允许我通过 i 访问元素。另一方面，使用 Map 或 Multimap 元素按 I 而不是 V 排序。

似乎我需要使用指针和集合等的组合，但我想不通...

Answer 1

你是对的，你需要一个组合。这是我会做的:

std::map<SomeKey, SomeObject> sortedObjects;
std::vector<std::map<SomeKey, SomeObject>::iterator> indexedObjects;

插入一个对象:

indexedObjects.push_back(sortedObjects.emplace(newKey, newObject).first);

这里的想法是，对象实际上在map中，但是vector可以通过索引访问iterator 到 map 中的对象。关键是除非两个容器都被修改，否则两个容器都不会被修改。您可以编写一个将这 2 个容器包装在一起的类，这样您不能修改一个而不修改另一个，或者您可以确保您永远不会犯那个错误。

从 indexedObjects 中按索引访问元素，从 sortedObjects 中按键访问元素。如果您需要从中间索引添加/删除元素，请使用 list 而不是 vector，这样您就可以从容器的中间添加/删除元素。如果您没有单独的 key ，请使用 set，而不是 map。如果您有重复的键/对象，请使用 multiset 或 multimap。