我有一组值 V
,它们由它们的索引 I
访问——即 i->V[i]
。
我需要根据值V[i]
(例如从大到小)迭代这些。
此外,我有原始索引 I_1, I2,..., I_N
的子集,我需要以相同的顺序(从大到小)访问它们的相应值。
这里使用的正确数据结构和过程是什么?我已经为此苦苦挣扎了一段时间,所以非常感谢您的帮助。
请注意,值 (V[i]
) 会不断更新,并且始终通过索引 i
进行访问。
如果我使用 set
来表示这些值,那么我需要删除更新后的元素并将其插入回去并提示放置它的位置(很可能它靠近它之前的位置集)。但是集合只包含V
,并且不允许我通过 i 访问元素。另一方面,使用 Map
或 Multimap
元素按 I
而不是 V
排序。
似乎我需要使用指针和集合等的组合,但我想不通...
最佳答案
你是对的,你需要一个组合。这是我会做的:
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
。
关于c++ - 用于访问集合的已排序子集的数据结构 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21787014/