Si la memoria no es un problema para mi aplicación concreta (las prioridades son la entrada, la búsqueda y la velocidad de clasificación), ¿qué tipo de estructura/concepto de datos sería la mejor opción para una tabla de clasificación de varios campos?
Por ejemplo, digamos que quiero crear un Salón de la Fama de un juego, ordenable por puntuación máxima (independiente del nombre de usuario), nombre de usuario (con todas las puntuaciones del mismo usuario colocadas juntas antes de clasificar a los usuarios por sus puntuaciones más altas), o nivel alcanzado (independiente de la puntuación o el nombre). En este ejemplo, si ordeno una lista enlazada, un vector o cualquier otra estructura de datos secuencial por la puntuación máxima de cada jugador, hace que la búsqueda de los otros campos -como el nivel y las puntuaciones no más altas- sea más iterativa (es decir, iterar a través de todos buscando la etapa, o buscando un rango de puntuación específico), a menos que conciba alguna otra forma de almacenar la información ordenada cuando introduzca nuevos datos.
La pregunta es si existe un método o estructura de base de datos más eficiente (aunque complicado y que consuma mucha memoria) en C/C++ que pueda estar preparado para este tipo de ordenación de campos múltiples. Las listas enlazadas parecen estar bien para las clasificaciones de puntuación simples, e incluso podría organizar una tabla hash haciendo un hash en un solo campo (nombre del jugador, o nivel alcanzado) para ordenar por un solo campo, pero entonces los otros campos toman O(N) para encontrar, peor para ordenar. Con sólo tres campos, me pregunto si hay una manera (como conjuntos o listas secundarias) para evitar iterar en ciertas ordenaciones pre-deseadas que conocemos de antemano.