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

Question

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

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

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

Answer 1

It feels like we can use trees to solve the problem

Answer 2

1. First query, the worst case is O(n), the best case is O(1), O(n) only needs a linear structure, arrays and linked lists are OK, if you want To achieve O(1), as you said, you must trade space for time, and hash tables are a common practice. In addition, there are some structures with intermediate time complexity. Binary search is a common practice, which can easily accelerate structures that originally require O(n) to O(lgn). Arrays, linked lists, and trees can all be used. Use this approach;
2. Then comes the modification. The modification actually involves querying first and then modifying. The time complexity of the query has already been mentioned. The complexity of the specific data modification depends on what your data is like;
3. Finally, there is sorting. The time complexity of sorting has been said badly. The lower limit of time complexity of the comparison-based sorting algorithm is O(nlgn). There are many structures to achieve it.
Depending on your needs, you want to do quick queries, and then you want to do real-time sorting.
Assuming that your modifications are more than queries, it is recommended that queries do not pursue O(1), and a lower limit is required for sorting. Using a heap or skip list structure can achieve the goal. If your queries are frequent and the modifications are small, you can create a hash table for querying, and you can directly divide the array into two or even use a linked list for sorting.

Answer 3

Std::map in C++ is implemented using red-black trees, which means that the output is sorted by key. Why

But after modification, the data needs to be reordered according to certain rules. Obviously map does not apply?

If multiple sorting methods are needed, can a std::map be used to save the corresponding reference for each sorting?