84669 人學習
152542 人學習
20005 人學習
5487 人學習
7821 人學習
359900 人學習
3350 人學習
180660 人學習
48569 人學習
18603 人學習
40936 人學習
1549 人學習
1183 人學習
32909 人學習
现有10w级的数据量，需求频繁的查询，频繁排序，该如何设计好的数据结构？因为数据变化频繁，初步考虑用map映射表索引查询，修改数据，但是修改之后数据又要根据一定的规则重新排序，显然map又不适用。如果采用vector容器可以解决排序，但查询修改数据的效率太过低下了，现在纠结该如何提高效率？用list不知道如何？大概的数据结构如下：
struct { int index; std::string name; }
由于学艺不清，在此请教各位前辈。
人生最曼妙的风景，竟是内心的淡定与从容！
感觉是用树 来解决
1、首先查询，最差的情况是O（n），最好的情况是O（1），O（n）只需要一个线性的结构就可以了，数组、链表都ok，想要达到O（1），就像你说的，必须用空间换时间，哈希表是一种常见做法。除此之外还有一些时间复杂度居中的结构，二分查找是一种常见的做法，可以很方便的把原本需要O（n）的结构加速成O（lgn），数组、链表、树都可以采用这种做法； 2、然后是修改，修改其实是先查询，再修改，查询的时间复杂度已经说过了，具体数据修改的复杂度得看你的数据是什么样的； 3、最后是排序，排序的时间复杂度已经被说烂了，基于比较的排序算法的时间复杂度下限是O（nlgn），有多种结构可以实现它。 看你的需求想要做快速查询，然后想要做实时排序。 假定你的修改是多于查询的，建议查询不必追求O（1），排序求一个下限，用堆或者跳表的结构可以达到目的。假如你的查询是频繁的，修改是少量的，那么可以建立一个哈希表用于查询，排序直接用数组二分甚至用链表都可以。
C++中std::map是用红黑树实现的，也就是输出时按key排序好。为什么会
但是修改之后数据又要根据一定的规则重新排序，显然map又不适用？
如果需要多种排序方式，是不是可以每一种排序都用一个std::map来保存相应的引用？
感觉是用树 来解决
1、首先查询，最差的情况是O（n），最好的情况是O（1），O（n）只需要一个线性的结构就可以了，数组、链表都ok，想要达到O（1），就像你说的，必须用空间换时间，哈希表是一种常见做法。除此之外还有一些时间复杂度居中的结构，二分查找是一种常见的做法，可以很方便的把原本需要O（n）的结构加速成O（lgn），数组、链表、树都可以采用这种做法；
2、然后是修改，修改其实是先查询，再修改，查询的时间复杂度已经说过了，具体数据修改的复杂度得看你的数据是什么样的；
3、最后是排序，排序的时间复杂度已经被说烂了，基于比较的排序算法的时间复杂度下限是O（nlgn），有多种结构可以实现它。
看你的需求想要做快速查询，然后想要做实时排序。
假定你的修改是多于查询的，建议查询不必追求O（1），排序求一个下限，用堆或者跳表的结构可以达到目的。假如你的查询是频繁的，修改是少量的，那么可以建立一个哈希表用于查询，排序直接用数组二分甚至用链表都可以。
C++中std::map是用红黑树实现的，也就是输出时按key排序好。为什么会
如果需要多种排序方式，是不是可以每一种排序都用一个std::map来保存相应的引用？