Using the std::sort() Method






4.52/5 (10 votes)
Apr 28, 2000

222472

767
An introduction to sorting using STL
Last year I was working on a database program that had to execute three queries, each of which had a couple of common fields and several dissimilar fields. The common data were starting and ending dates, and naturally the rows of data would have to be interleaved.
Purchase Jan 1, 1990
Installation Feb 2, 1990
Repair Sept 23, 1991
Installation Dec 10, 1993
Repair Jun 4, 1996
Since there were three different but similar items, I needed a base class which I could derive from. The base contained the date stamp I would sort on, and for this example I’ve added a method to output text to an output stream:
// Base class we're using to provide a function with a sortable value class CHistoryItem { public: CHistoryItem(DATE& rTimestamp) { m_Timestamp = rTimestamp; } DATE& GetTimestamp() { return m_Timestamp; } // Indicate the item type as a string virtual char* ItemName() = 0; // Output the item to a stream void OutputToStream(std::ostream& os) { os << ItemName() << "\t" << m_Timestamp << "\n"; } protected: DATE m_Timestamp; };
Once the base class was defined, I derived the three history items from it:
// Repair history entry class CRepairItem : public CHistoryItem { public: CRepairItem(DATE rTimestamp) : CHistoryItem(rTimestamp) { } // Indicate that this is a repair char* ItemName() { return "Repair: "; } }; // Installtion history entry class CInstallItem : public CHistoryItem { public: CInstallItem(DATE& rTimestamp) : CHistoryItem(rTimestamp) { } // Indicate that this is a installation char* ItemName() { return "Install: "; } }; // Purchase history entry class CPurchaseItem : public CHistoryItem { public: CPurchaseItem(DATE& rTimestamp) : CHistoryItem(rTimestamp) { } // Indicate that this is a installation char* ItemName() { return "Purchase: "; } };
Ok...so we have our class definitions, now its time to create a vector which will contain our objects. Since I didn’t know what know prior to the query is performed what to expect, we have to dynamically allocate objects. Since I’m a bit lazy and forgetful, I tend to free the objects I allocate in my vectors in the vector destructor.
// A vector based class to contain our history items class CHistoryVector : public std::vector<CHistoryItem*> { public: // Make sure that the history items are de-allocated so we don't leak ~CHistoryVector() { for (iterator pItem=begin(); pItem != end(); ++pItem) delete *pItem; } };
Now that we have everything set up, we need to provide a way of specifying how we want to sort the data. Now typically I only need to sort my data one way, but to show how the sorting works, I’ve created two sorting methods. Again, I could have put more work into the CHistoryItem class and given it an operator < method, but then what I’m doing might not be so obvious. Basically the sorting classes must have an operator () method that returns a bool and is passed two elements from the vector by the sort() algorithm. It is your job to return true if the first item is to placed before the second item in the sorted output, false if it is after the second item.
// Ascending date sorting function struct SAscendingDateSort { bool operator()(CHistoryItem*& rpStart, CHistoryItem*& rpEnd) { return rpStart->GetTimestamp() < rpEnd->GetTimestamp(); } }; // Descending date sorting function struct SDescendingDateSort { bool operator()(CHistoryItem*& rpStart, CHistoryItem*& rpEnd) { return rpStart->GetTimestamp() > rpEnd->GetTimestamp(); } };
All we need now is something to create our vector, sort it, and then do something that would indicate to us what the output is. Here is a simple console application which can be used to test our example:
// Stuff a vector with data & then sort int main(int argc, char* argv[]) { CHistoryVector HistoryVector; // Put two repair items in the vector HistoryVector.push_back(new CRepairItem(2*365.0)); HistoryVector.push_back(new CRepairItem(5*365.0)); // Now stick three installations items in the vector HistoryVector.push_back(new CInstallItem(3*365.0)); HistoryVector.push_back(new CInstallItem (6*365.0)); HistoryVector.push_back(new CInstallItem (4*365.0)); // Finally we need to add a purchase item to the vector HistoryVector.push_back(new CPurchaseItem (1*365.0)); //================================== // Sort the items in ascending order std::sort(HistoryVector.begin(), HistoryVector.end(), SAscendingDateSort()); // Now show the results! std::cout << "Ascending Sort\n"; for (long lEle=0; lEle < HistoryVector.size(); ++lEle) HistoryVector[lEle]->OutputToStream(std::cout); //================================== // Sort the items in descending order std::sort(HistoryVector.begin(), HistoryVector.end(), SDescendingDateSort()); // Now show the new results! std::cout << "\nDescending Sort\n"; for (lEle=0; lEle < HistoryVector.size(); ++lEle) HistoryVector[lEle]->OutputToStream(std::cout); getchar(); // Pause for a response return 0; }
So how does it look when its run?? Where here is the output:
Ascending Sort
Purchase: 365
Repair: 730
Install: 1095
Install: 1460
Repair: 1825
Install: 2190
Descending Sort
Install: 2190
Repair: 1825
Install: 1460
Install: 1095
Repair: 730
Purchase: 365
Obviously the dates haven’t been converted to a nice string, but we could obviously add this if needed...the main point is to note that the first set of data is sorted in ascending order while the second set of data is in descending order.
Paul's company is ADOPro.com.