Average Rating: 4/5 | Rate this item | 4 users have rated this item.

Expertise: Intermediate
Language: C

January 26, 2004

Sorting a STL Sequential Container of Pointers

Say you have a user structure and a container of pointers to that user structure. You need to sort the container based only on some structure's members. The solution is to define the structure's specific function objects less and greater and to pass to the sort algorithm the appropiate function object (less for ascending sorting and greater for descending sorting).

The following code example illustrates the solution for a vector container and a simple user structure sorted by the member m_i:

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

struct STest
{
  STest(int i) : m_i(i) {}
  int m_i;
};

namespace std
{
  struct less<STest*>
  {
    bool operator()(STest const* p1, STest const* p2)
    {
      if(!p1)
        return true;
      if(!p2)
        return false;
      return p1->m_i < p2->m_i;
    }
  };

  struct greater<STest*>
  {
    bool operator()(STest const* p1, STest const* p2)
    {
      if(!p1)
        return false;
      if(!p2)
        return true;
      return p1->m_i > p2->m_i;
    }
  };
};

int main()
{
  vector<STest*> myvect;
  myvect.push_back(new STest(11));
  myvect.push_back(new STest(22));
  myvect.push_back(new STest(13));
  myvect.push_back(new STest(7));
  myvect.push_back(new STest(15));
  //Ascending Sorting
  sort(myvect.begin(), myvect.end(), less<STest*>());
  //Display
  vector<STest*>::iterator it;
  for(it=myvect.begin(); it!=myvect.end(); it++)
    cout << (*it)->m_i << endl;
  //Descending Sorting
  sort(myvect.begin(), myvect.end(), greater<STest*>());
  //Display
  for(it=myvect.begin(); it!=myvect.end(); it++)
    cout << (*it)->m_i &l;t< endl;
  //Free allocated memory
  for(it=myvect.begin(); it!=myvect.end(); it++)
    delete *it;
  }
  return 0;
}

This solution can be applied to all the STL sequential containers, excepting the list container, for which only the greater function object can be implemented and instead of the sort algorithm the sort member function has to be applied.

This code example is illustrates the solution for the same user structure as above:

#include <iostream>
#include <functional>
#include <list>

using namespace std;

struct STest
{
  STest(int i) : m_i(i) {}
  int m_i;
};

namespace std
{
  struct greater<STest*>
  {
    bool operator()(STest const* p1, STest const* p2)
    {
      //Defined like less for ascending sorting
      if(!p1)
        return true;
      if(!p2)
        return false;
      return p1->m_i < p2->m_i;
    }
  };
};

int main()
{
  list<STest*> mylist;
  mylist.push_back(new STest(11));
  mylist.push_back(new STest(22));
  mylist.push_back(new STest(13));
  mylist.push_back(new STest(7));
  mylist.push_back(new STest(15));
  //Ascending Sorting
  mylist.sort(greater<STest*>());
  list<STest*>::iterator it;
  for(it=mylist.begin(); it!=mylist.end(); it++)
    cout << (*it)->m_i << endl;
  for(it=mylist.begin(); it!=mylist.end(); it++)
    delete *it;
  return 0;
}