C ++ двойная сортировка данных с несколькими элементами

Question

У меня есть несколько записей данных, которые содержат следующую информацию: идентификационный номер name1 Дата name2

Можно поместить это в такую ​​структуру:

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

В моих данных у меня много таких записей, и я хотел бы отсортировать. Сначала я хочу отсортировать по алфавиту на основе name1, а затем отсортировать по дате. Однако сортировка по дате является подмножеством сортировки по алфавиту, например если у меня есть две записи с одинаковым именем1, я хочу заказать эти записи по дате. Кроме того, когда я сортирую, я хочу, чтобы элементы записи оставались вместе, поэтому все четыре значения объединяются.

Мои вопросы следующие:

1) Какой тип структуры данных мне следует использовать для хранения этих данных, чтобы я мог хранить набор из четырех элементов вместе, когда сортирую по любому из них?

2) Какой самый быстрый способ сделать эту сортировку (с точки зрения количества времени, чтобы написать код). В идеале я хочу использовать что-то вроде сортировки в алгоритме. Так как он уже встроен.

3) Имеет ли STL некоторую встроенную структуру данных, которая может эффективно обрабатывать двойную сортировку, которую я описал?

Answer 1

У вас хорошая структура, за исключением того, что вы можете добавить перегрузку operator< для сравнения.Здесь я делаю сравнение «сравни по имени, затем по дате»:

// 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;
}

[Редактировать: то, что требуется, называется «строгим слабым порядком».Если вы хотите вникнуть в подробности о том, что означает и какие альтернативы возможны, Дейв Абрахамс написал довольно подробный пост о C ++ Next об этом.

В приведенном выше случае мы начинаемсравнивая поля name1 из двух.Если a<b, то мы немедленно возвращаем true.В противном случае мы проверяем a>b и, если так, возвращаем false.В этот момент мы исключили a<b и a>b, поэтому мы определили, что a==b, и в этом случае мы проверяем даты - если a<b, мы возвращаем true.В противном случае мы возвращаем false - либо даты равны, либо b>a, что означает, что проверка для a<b является ложной.Если сортировке нужно разобраться (без каламбура), какой из этих случаев имеет место, она может снова вызвать функцию с заменой аргументов.Имена по-прежнему будут одинаковыми, поэтому все равно будут сводиться к датам - если мы получим false, даты будут равны.Если мы получим истинное значение на свопированных датах, то то, что началось со второй даты, на самом деле больше.]

operator<, который вы определяете в структуре, определяет порядок, который будет использоваться по умолчанию.Когда / если вы хотите, вы можете указать другой порядок для сортировки:

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

На самом деле вы можете использовать объект функции для реализации ваших критериев сортировки

предположим, что вы хотите сохранить записи в наборе

//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    
}

Answer 3

Эта структура данных тут же должна работать просто отлично.Вам нужно переопределить оператор less, тогда вы можете просто вставить их все в карту, и они будут отсортированы. Вот дополнительная информация об операторах сравнения для карты

Обновление: при дальнейшем отражении я бы использовал набор, а не карту, потому что в значении нет необходимости.Но вот доказательство того, что оно все еще работает

Доказательство этого работает:

#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;
}