Group sorting a vector in C++

Question

I have a std::vector full of objects, each with a numeric group identifier associated with them. The object also has properties such as "size" and "name".

I need to be able to sort the vector of objects by name, size and other properties while keeping them grouped together (e.g. by the group identifier mentioned above).

How can this goal be accomplished?

Answer 1

Using the STL, it's straightforward to insert your own comparison functions. You want to define a comparison function that compares on group first, and then compares on the other attributes.

static bool CompareWidget(const Widget& w1, const Widget& w2)
{
    if(w1.GetGroupNumber() != w2.GetGroupNumber())
        return (w1.GetGroupNumber() < w2.GetGroupNumber());
    if(w1.GetHeight() != w2.GetHeight())
        return (w1.GetHeight() < w2.GetHeight();
    /// etc
    return false;
}


 static void SortWidgetVector(WidgetVector& widgetVector)
 {
      std::sort(widgetVector.begin(), widgetVector.end(), CompareWidget);
 }

Answer 2

Use the group identifier as the primary sort key.

For example, to sort on group, then name, then size, you can use a comparison object such as:

 class my_comparison : public std::binary_function< object, object, bool >
 {
 public:
     inline bool operator()(
         object const &left,
         object const &right ) const
     {
         return ( left.group_id < right.group_id ? true :
                  left.group_id > right.group_id ? false :
                  left.name < right.name ? true :
                  left.name > right.name ? false :
                  left.size < right.size );
     }
 };

Then pass an instance of this as a third parameter to the std::sort() function.

Answer 3

First of all, let's rephrase the problem. What you really want is to sort your objects by group ID, and then by (name, size, ...). If you sort them by group ID first, then, obviously, objects with the same group ID will stick together.

This can obviously be easily done using a custom predicate for std::sort. Something along these lines:

struct MyPredicate {
  bool operator() (const MyClass& lhs, const MyClass& rhs) const {
    if (lhs.groupID != rhs.groupID) {
      return lhs.groupId < rhs.groupId;
    } else if (lhs.name != rhs.name) {
      return lhs.name < rhs.name;
    else
      return lhs.size < rhs.size.
    }
  }
};

std::sort(myObjects.begin(), myObjects.end(), MyPredicate());

Answer 4

You can use partition or stable_partion to divide your objects into several sets and sort them individually. I’m not sure, how much it faster or slower, but it seems to me the code will be slightly more understandable.

class GroupPredicate : std::unary_function<object, bool>
{
public:
   GroupPredicate(INT group)
   : m_group(group)
   {
   }

   inline bool operator()(const object &object)
   {
     return object.group == m_group;
   }

   INT m_group;
};

class SizeSort : public std::binary_function<object, object, bool>
{
public:
  inline bool operator()(const object &left, const object &right)
  {
    return left.size < right.size;
  }
};

//...

std::vector<object> arVector;

for (INT i = 0; i < groupCount; ++i)
{
  std::vector<object>::iterator pEndGroup = std::partition(pStartGroup, arVector.end(), GroupPredicate(i));
  std::sort(pStartGroup, pEndGroup, SizeSort());
  pStartGroup = pEndGroup;
}

Answer 5

What you really want is to sort your objects by group ID, and then by (name, size, ...)

Actually, what I'm attempting to do is the reverse. First, I want to sort the vector by a secondary attribute (such as name, size, etc.) and then ensure that all vector elements are contained within groups.

I have found an algorithm that works for this, but exhibits very poor performance when dealing with large vectors (hundreds of thousands of elements). I first use a std::sort to order the vector by size (for example), then do the following:

vector<object*>::iterator iter = m_vec.begin();
while (iter != m_vec.end())
{
 UINT nGroupIndex = ((object*)*iter)->GetGroupIndex();
 iter = stable_partition(iter, m_vec.end(), GroupPredicate(nGroupIndex));
}

(Of course, GroupPredicate simply compares the group ID of the current object)

Again, this does exactly what I want, but it's too slow. On a fast computer with lots of memory, it works great on an array with thousands of elements, but dies a horrid death when the array is much larger (hundreds of thousands, for example).

How can I accomplish the same goal, but do it faster?

Answer 6

I need to be able to sort the vector of objects by name, size and other properties while keeping them grouped together (e.g. by the group identifier mentioned above).

Actually, what I'm attempting to do is the reverse. First, I want to sort the vector by a secondary attribute (such as name, size, etc.) and then ensure that all vector elements are contained within groups.

The outcome should be the same no matter how you think about it, unless you want to use the vector in the intermediary state where it isn't sorted by group identifier. If it isn't so, I can't see why a comparison function using two criteria cannot be used (where group id is primary condition and name/size/other is secondary). You can even create a generic comparison object that combines the use of two predicates (by_two_criteria):

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>

template <class FirstCondition, class SecondCondition>
class by_two_criteria_t
{
    FirstCondition first;
    SecondCondition second;
public:
    by_two_criteria_t(FirstCondition f, SecondCondition s): first(f), second(s) {}
    template <class T>
    bool operator()(const T& a, const T& b) const
    {
        return first(a, b) || (!first(b, a) && second(a, b));
    }
};

template <class FirstCondition, class SecondCondition>
by_two_criteria_t<FirstCondition, SecondCondition> by_two_criteria(FirstCondition f, SecondCondition s)
{
    return by_two_criteria_t<FirstCondition, SecondCondition>(f, s);
}

class X
{
    int group;
    int value;
public:
    X(int g, int n): group(g), value(n) {}
    friend bool compare_group(const X& a, const X& b);
    friend bool compare_value(const X& a, const X& b);
    friend std::ostream& operator<<(std::ostream& os, const X& x) { return os << x.group << ", " << x.value; }
};

bool compare_group(const X& a, const X& b) { return a.group < b.group; }
bool compare_value(const X& a, const X& b) { return a.value < b.value; }

X random_x()
{
    return X(rand() % 10, rand() % 20);
}

int main()
{
    using namespace std;
    vector<X> vec;
    generate_n(back_inserter(vec), 100, random_x);
    sort(vec.begin(), vec.end(), by_two_criteria(compare_group, compare_value));
    copy(vec.begin(), vec.end(), ostream_iterator<X>(cout, "\n"));
}

And just for fun, here's a functor that combines n comparison criteria (C++0x only for variadic templates and new-style initialization syntax):

#include <functional>
template <class T, class ...Fun>
class n_criteria_t {};

template <class T, class Fun1, class ...FunN>
class n_criteria_t<T, Fun1, FunN...>: public std::binary_function<T, T, bool>
{
public:
    n_criteria_t(Fun1 f1, FunN... fn): f1(f1), f2(fn...) {}
    bool operator() (const T& a, const T& b) const
    {
        return f1(a, b) || (!f1(b, a) && f2(a, b));
    }
private:
    Fun1 f1;
    n_criteria_t<T, FunN...> f2;
};

template <class T, class Fun1>
class n_criteria_t<T, Fun1>: public std::binary_function<T, T, bool>
{
public:
    n_criteria_t(Fun1 f1): f1(f1) {}
    bool operator() (const T& a, const T& b) const
    {
        return f1(a, b);
    }
private:
    Fun1 f1;
};

template <class T, class ...Fun>
n_criteria_t<T, Fun...> n_criteria(Fun... f)
{
    return {f...};
}