C++ de datos dobles de clasificación con múltiples elementos

Question

tengo varias entradas de datos que contienen la siguiente información: id_number nombre1 fecha nombre2

Es posible poner esto en una estructura como esta:

struct entry { 
    int id_number; 
    string name1; 
    int date; 
    string name2; 
} 

En mis datos, tengo muchas de esas entradas y me gustaría ordenarlas. Primero, quiero ordenar alfabéticamente en función de name1, luego ordenar por fecha. Sin embargo, la clasificación por fecha es un subconjunto del orden alfabético, p. si tengo dos entradas con el mismo nombre1, entonces quiero ordenar esas entradas por fecha. Además, cuando ordeno, quiero que los elementos de la entrada permanezcan juntos, por lo que los cuatro valores van juntos.

Mis preguntas son las siguientes:

1) ¿Qué tipo de estructura de datos debería utilizar para mantener estos datos para que pueda mantener el conjunto de cuatro elementos juntos cuando cualquier tipo por cualquiera de ellos?

2) ¿Cuál es la forma más rápida de hacer esta ordenación (en términos de cantidad de tiempo para escribir el código). Idealmente, quiero usar algo como el género en algorithms.h ya que está integrado.

3) ¿STL tiene alguna estructura de datos integrada que pueda manejar la doble clasificación que describí de manera eficiente?

Answer 1

La estructura que tiene está muy bien, excepto que es posible que desee agregar una sobrecarga de operator< hacer la comparación. Aquí estoy haciendo la comparación "comparar por su nombre, a continuación, la fecha":

// Add this as a member function to `entry`. 
bool operator<(entry const &other) const { 
    if (name1 < other.name1) 
     return true; 
    if (name1 > other.name1) 
     return false; 

    // otherwise name1 == other.name1 
    // so we now fall through to use the next comparator. 

    if (date < other.date) 
     return true; 
    return false; 
} 

[Editar: lo que se requiere que se llama un "ordenamiento débil estricto". Si desea entrar en detalles sobre cuáles son los medios y qué alternativas son posibles, Dave Abrahams escribió una publicación bastante detallada en C++ Next al respecto.

En el caso anterior, comenzamos comparando los campos name1 de los dos. Si es a<b, inmediatamente devolveremos la verdad. De lo contrario, verificamos a>b, y si es así, devolvemos falso. En ese punto, hemos eliminado a<b y a>b, por lo que hemos determinado que a==b, en cuyo caso probamos las fechas: si es a<b, devolveremos la verdad. De lo contrario, devolveremos el valor falso: las fechas son iguales o b>a, lo que significa que la prueba para a<b es falsa. Si el género necesita resolver (sin juego de palabras) cuál de esos es el caso, puede llamar a la función nuevamente con los argumentos intercambiados. Los nombres seguirán siendo iguales, por lo que aún se reducirá a las fechas; si obtenemos una respuesta falsa, las fechas son iguales. Si somos ciertos en las fechas intercambiadas, entonces lo que comenzó como la segunda fecha es realmente mayor. ]

El operator< que define en la estructura define el orden que se utilizará de forma predeterminada.Cuando/si se desea se puede especificar otra orden para la clasificación de usar:

struct byid { 
    bool operator<(entry const &a, entry const &b) { 
     return a.id_number < b.id_number; 
    } 
}; 

std::vector<entry> entries; 

// sort by name, then date 
std::sort(entries.begin(), entries.end()); 

// sort by ID 
std::sort(entries.begin(), entries.end(), byid()); 

Answer 2

Esa estructura de datos debería funcionar bien. Lo que debe hacer es anular al operador menor que, entonces podría simplemente insertarlos todos en un mapa y se ordenarían. Here is more info on the comparison operators for a map

Actualización: a mayor reflexión, utilizaría un conjunto, y no un mapa, porque no hay necesidad de un valor. Pero aquí es la prueba de que todavía funciona

Prueba esto funciona:

#include<string> 
#include<map> 
#include<stdio.h> 
#include <sstream> 


using namespace std; 

struct entry { 
    int m_id_number; 
    string m_name1; 
    int m_date; 
    string m_name2; 

    entry( int id_number, string name1, int date, string name2) : 
     m_id_number(id_number), 
     m_name1(name1), 
     m_date(date), 
     m_name2(name2) 
    { 

    } 

    // Add this as a member function to `entry`. 
    bool operator<(entry const &other) const { 
     if (m_name1 < other.m_name1) 
      return true; 
     if (m_name2 < other.m_name2) 
      return true; 
     if (m_date < other.m_date) 
      return true; 
     return false; 
    } 

    string toString() const 
    { 
     string returnValue; 

     stringstream out; 
     string dateAsString; 

     out << m_date; 
     dateAsString = out.str(); 

     returnValue = m_name1 + " " + m_name2 + " " + dateAsString; 

     return returnValue; 
    } 
}; 


int main(int argc, char *argv[]) 
{ 
    string names1[] = {"Dave", "John", "Mark", "Chris", "Todd"}; 
    string names2[] = {"A", "B", "C", "D", "E", "F", "G"}; 

    std::map<entry, int> mymap; 
    for(int x = 0; x < 100; ++x) 
    { 
     mymap.insert(pair<entry, int>(entry(0, names1[x%5], x, names2[x%7]), 0)); 
    } 

    std::map<entry, int>::iterator it = mymap.begin(); 
    for(; it != mymap.end() ;++it) 
    { 
     printf("%s\n ", it->first.toString().c_str()); 
    } 
    return 0; 
} 

Answer 3

En realidad se puede utilizar objeto de función para implementar los criterios de clasificación

suponer que desea almacenar las entradas en el conjunto

//EntrySortCriteria.h 
class EntrySortCriteria 
{ 
    bool operator(const entry &e1, const entry &e2) const 
    { 
     return e1.name1 < e2.name1 || 
       (!(e1.name1 < e2.name1) && e1.date < e2.date)) 
    } 
} 

//main.cc 
#include <iostream> 
#include "EntrySortCriteria.h" 

using namespace std; 
int main(int argc, char **argv) 
{ 

    set<entry, EntrySortCriteria> entrySet; 
    //then you can put entries into this set, 
    //they will be sorted automatically according to your criteria 
    //syntax of set: 
    //entrySet.insert(newEntry); 
    //where newEntry is a object of your entry type  
}