C++ double sorting data with multiple elements

Question

I have multiple data entries that contain the following information: id_number name1 date name2

It is possible to put this into a struct like this:

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

In my data, I have many such entries and I would like to sort. First, I want to sort alphabetically based on name1, then sort by date. However, the sort by date is a subset of the alphabetical sort, e.g. if I have two entries with the same name1, I then want to order those entries by date. Furthermore, when I sort, I want the elements of the entry to remain together, so all four values go together.

My questions are the following:

1) What type of data structure should I use to hold this data so I can keep the set of four elements together when I sort any by any one of them?

2) What is the quickest way to do this sorting (in terms of amount of time to write the code). Ideally, I want to use something like the sort in algorithms.h since it is already built in.

3) Does STL have some built in data structure that can handle the double sorting I described efficiently?

Answer 1

The struct you have is fine, except that you may want to add an overload of operator< to do comparison. Here I'm doing the "compare by name, then date" comparison:

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

[Edit: What's required is called a "strict weak ordering". If you want to get into detail about what the means, and what alternatives are possible, Dave Abrahams wrote quite a detailed post on C++ Next about it.

In the case above, we start by comparing the name1 fields of the two. If a<b, then we immediately return true. Otherwise, we check for a>b, and if so we return false. At that point, we've eliminated a<b and a>b, so we've determined that a==b, in which case we test the dates -- if a<b, we return true. Otherwise, we return false -- either the dates are equal, or b>a, either of which means the test for a<b is false. If the sort needs to sort out (no pun intended) which of those is the case, it can call the function again with the arguments swapped. The names will still be equal, so it'll still come down to the dates -- if we get false, the dates are equal. If we get true on the swapped dates, then what started as the second date is actually greater. ]

The operator< you define in the structure defines the order that will be used by default. When/if you want you can specify another order for the sorting to use:

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

Actually you can use function object to implement your sorting criteria

suppose that you would like to store the entries in the set

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

That data structure right there should work just fine. What you should do is override the less than operator, then you could just insert them all in a map and they would be sorted. Here is more info on the comparison operators for a map

Update: upon farther reflection, I would use a set, and not a map, because there is no need for a value. But here is proof it still works

Proof this works:

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