c++ - 10W级数据频繁查询修改与排序问题，如何提高效率？

Question

现有10w级的数据量，需求频繁的查询，频繁排序，该如何设计好的数据结构？因为数据变化频繁，初步考虑用map映射表索引查询，修改数据，但是修改之后数据又要根据一定的规则重新排序，显然map又不适用。如果采用vector容器可以解决排序，但查询修改数据的效率太过低下了，现在纠结该如何提高效率？用list不知道如何？大概的数据结构如下：

struct
{
int index;
std::string name;
}

由于学艺不清，在此请教各位前辈。

Answer 1

感觉是用树 来解决

Answer 2

1、首先查询，最差的情况是O（n），最好的情况是O（1），O（n）只需要一个线性的结构就可以了，数组、链表都ok，想要达到O（1），就像你说的，必须用空间换时间，哈希表是一种常见做法。除此之外还有一些时间复杂度居中的结构，二分查找是一种常见的做法，可以很方便的把原本需要O（n）的结构加速成O（lgn），数组、链表、树都可以采用这种做法；
2、然后是修改，修改其实是先查询，再修改，查询的时间复杂度已经说过了，具体数据修改的复杂度得看你的数据是什么样的；
3、最后是排序，排序的时间复杂度已经被说烂了，基于比较的排序算法的时间复杂度下限是O（nlgn），有多种结构可以实现它。
看你的需求想要做快速查询，然后想要做实时排序。
假定你的修改是多于查询的，建议查询不必追求O（1），排序求一个下限，用堆或者跳表的结构可以达到目的。假如你的查询是频繁的，修改是少量的，那么可以建立一个哈希表用于查询，排序直接用数组二分甚至用链表都可以。

Answer 3

C 中std::map是用红黑树实现的，也就是输出时按key排序好。为什么会

但是修改之后数据又要根据一定的规则重新排序，显然map又不适用？

如果需要多种排序方式，是不是可以每一种排序都用一个std::map来保存相应的引用？