Thread: sorting container

Hello

I have a large stl container with name - surname (pair of two std::strings). I want to sort the whole container by surname.

What approach should I use?
Note that there are more than few 500 000 items (names/surnames).

Thanks for help

I would suggest doing it somthing like this:..

Code:

sort function
{
   make a "current point" varible as "ZZZZZZZZZZZZZZZZZZZZZ" or somthing like it
   make a new array the same size as the original

   // never reset the "current point" varible

   loop through the whole new array
   {
      loop through the whole original array
      {
         if this surename is less than the one in the "current point" varible
         {
            set the "current point" varible to this surename 
         }
      }
      set this surename in the new array to the one in "current point" varible
   }
   // there, now you're new array is the old one, just sorted.
}

Of course, it's not actuall code, but you get the idea...

It depends on the container. Use sort like in XSquared's example for vector or deque. Use the list's member sort method if you are using a list. For a map or set, if you aren't already sorted by surname, you should copy all the data to a vector and re-sort.

Can I put Comp function (from XSquared's example) in a class?
Would you OOP guys do this? (I dont have any global functions in my programs)

You could always put it in whatever class you think it belongs and make it static. You'd then pass it to sort() as ClassName::Comp.

sort is a global function. So is operator<<. There's nothing wrong with making a function a non-member.

You can make operator< for your class, but it probably doesn't make as much sense as a separate comparison function because your class can be sorted by name or surname and you'd have to pick only one of those for your operator< if you made one. It makes more sense to have to comparison functions, one for name and one for surname, and pass the correct one to sort. It's probably even better to make a function object:

Code:

struct CompSecond
{
  bool operator()(const TPair& PairA, const TPair& PairB) const
  {
    return PairA.second < PairB.second;
  }
};

Originally Posted by CornedBee

Or you could use TR1 binders.

Code:

typedef std::pair<std::string, std::string> person;
std::vector<person> people;
// ...
std::sort(people.begin(), people.end(),
    tr1::bind(&person::second, _1) < tr1::bind(&person::second, _2));

Seems like the best option. What do you think?

If you have tr1, then I'd say yes. Something as simple as sorting by surname doesn't need a separate function object.

It's been a while since I've played with this stuff, I'm wondering what the syntax is if you have a member function get_second() instead of a public member variable.

Why if I have tr1?
Isnt this in standard?
Is it in boost also?