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來保存對應的引用？