C ++ double-sort data with multiple elements

Question

I have several data records that contain the following information: ID number name1 Date name2

You can put this in the structure as follows:

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

In my data, I have many such records, and I would like to sort. First, I want to sort alphabetically based on name1, and then sort by date. However, sorting by date is a subset of the alphabetical sort, for example. if I have two records with the same name1, I want to order these records by date. Also, when I sort, I want the recording elements to stay together, so all four values ​​are combined.

My questions are as follows:

1) What data structure should I use to store this data so that I can combine a set of four elements when I sort them with any of them?

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

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

Answer 1

You have a good structure, except that you can add operator< overloading for comparison. Here I compare the comparison "by name, then date":

 // 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 is required is called "strict weak ordering." If you want to talk in detail about what tools and which alternatives are possible, Dave Abrahams wrote a rather detailed post in C ++ Next about this.

In the above example, we will start by comparing the name1 fields of the two. If a<b , then we immediately return true. Otherwise, we check a>b , and if so, we return false. At this point, we excluded a<b and a>b , so we determined that a==b , in which case we check the dates - if a<b , we return true. Otherwise, we return false - either the dates are equal, or b>a , or of which means that the test for a<b is false. If sorting should be sorted (no pun intended), which one is the case, he can again call the function with the replacement of arguments. Names will still be equal, so they will go up to dates - if we get false, the dates will be equal. If we return on dates with a replacement, then what started on the second date is actually more. ]

operator< that you define in the structure determines the order that will be used by default. When / if you want, you can specify a different sort order 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

This data structure should work fine there. What you have to do is redefine less than the operator, then you can just insert them all on the card and they will be sorted. Additional information about comparison operators for a map

Update: with further reflection, I would use a set, not a map, because there is no need for a value. But here is the proof that it still works
Proof of these 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; } 

Answer 3

You can actually use a function object to implement your sorting criteria

suppose you want to keep records in a 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 }