Click here to Skip to main content
Click here to Skip to main content

Using the std::sort() Method

, 27 Apr 2000
Rate this:
Please Sign up or sign in to vote.
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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Paul Wolfensberger
Web Developer
United States United States
No Biography provided

Comments and Discussions

 
GeneralCan't get data from a loaded vector. Help!! PinmemberLarry Mills2-Apr-05 4:43 
GeneralInheriting continued... PinsussMårten9-Jan-03 2:44 
GeneralUsing operator<() PinmemberRyan14-Apr-01 16:00 
GeneralRe: Using operator<() PinmemberBen Burnett14-Apr-01 23:34 
GeneralRe: Using operator&lt;() PinmemberChristoph Conrad17-Mar-09 21:41 
QuestionWhat about sorting lists? PinmemberJames Patterson15-Mar-01 6:33 
AnswerRe: What about sorting lists? PinmemberAdrian0116-Jan-02 23:41 
GeneralRe: What about sorting lists? PinmemberPaul Wolfensberger21-Jan-02 14:11 
GeneralRe: What about sorting lists? PinmemberChristian Graus21-Jan-02 15:07 
Generaltried to use std::sort in map but failed PinmemberArun Saha22-Feb-01 5:45 
Hello, all the c++ experts out there. I am trying to do the following and abviously doing something wrong. This is similar to what the author posted but I am trying to sort a map. Please be gentle, I am new in c++.
 
#include "stdafx.h"
#include
#include
#include <map>
#include
#include
#include
using namespace std;
 
class Product
{
public:
Product():mName("New Product"), mStockLevel(0), mPrice(0) {}
Product(string newName, double newPrice = 0, int newStockLevel = 0):
mName(newName), mPrice(newPrice), mStockLevel(newStockLevel) {}
 
void setName(string newName) { mName = newName; }
void setName(int newStockLevel) { mStockLevel = newStockLevel; }
void setPrice(double newPrice) { mPrice = newPrice; }
 
string getName() const { return mName; }
int getStockLevel() const { return mStockLevel; }
double getPrice() const { return mPrice; }
 
friend ostream& operator<<(ostream& os, const Product& p)
{
os << "Product: " << p.mName
<< "\tPrice: " << p.mPrice
<< "\tStock on hand: " << p.mStockLevel;
return os;
}
 
bool operator<(const Product& q) const
{
return (getPrice() < q.getPrice());
}
 
private:
string mName;
int mStockLevel;
double mPrice;
};
/*
template
class byPrice: public binary_function
{
public:
bool operator()(const T& x, const T& y) const
{
return (x < y);
}
};
*/
 
struct sortbyPrice
{
bool operator()(const Product& x, const Product& y)
{
return (x.getPrice() < y.getPrice());
}
};
 
// template function to show all elements in a map
template
void showMap(const map& m);
 
int main()
{
Product Pen("Pen", 5.99, 58);
Product Lamp("Lamp", 28.49, 24);
Product Speaker("Speaker", 24.95, 40);
 
map productMap;
typedef map::iterator mItor;
 
productMap[Pen.getName()] = Pen;
productMap[Lamp.getName()] = Lamp;
productMap[Speaker.getName()] = Speaker;

cout << "Products before sort...\n";
showMap(productMap);
productMap.size();
mItor first = productMap.begin();
mItor last = productMap.end();
 
sort(first, last, sortbyPrice());
cout << "Products after sort by price...\n";
showMap(productMap);
 
return 0;
}
 
//
// Show map elements
//
template
void showMap(const map& m)
{
cout << "Map elements:\n";
for (map::const_iterator ci = m.begin(); ci != m.end(); ++ci)
cout << ci->first << "\t" << ci->second << "\n";
 
cout << "\n\n";
}
Frown | :( Frown | :( :(
GeneralRe: tried to use std::sort in map but failed PinmemberPaul Wolfensberger22-Feb-01 13:59 
GeneralRe: tried to use std::sort in map but failed PinmemberCarignan19-Feb-02 6:20 
GeneralRe: tried to use std::sort in map but failed PinmemberCarignan19-Feb-02 6:18 
GeneralRe: tried to use std::sort in map but failed PinmemberNemanja Trifunovic19-Feb-02 6:24 
GeneralRe: tried to use std::sort in map but failed PinmemberPaul Wolfensberger19-Feb-02 10:42 
GeneralRe: tried to use std::sort in map but failed PinmemberAnonymous24-Jun-02 7:40 
GeneralInheriting from std::vector is a preference thing.... PinsussPaul29-Apr-00 6:43 
GeneralRe: Inheriting from std::vector is a preference thing.... PinmemberJulien22-Feb-01 15:05 
GeneralRe: Inheriting from std::vector is a preference thing.... PinmemberPaul Wolfensberger23-Feb-01 3:01 
GeneralInheriting from std::vector is a Bad Idea (TM) PinsussWilliam Kempf29-Apr-00 6:23 
GeneralRe: Inheriting from std::vector is a Bad Idea (TM) PinsussMikael Garde18-Oct-05 1:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 28 Apr 2000
Article Copyright 2000 by Paul Wolfensberger
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid