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），排序求一个下限，用堆或者跳表的结构可以达到目的。假如你的查询是频繁的，修改是少量的，那么可以建立一个哈希表用于查询，排序直接用数组二分甚至用链表都可以。

感觉是用树 来解决