Групповая сортировка вектора в C ++

Question

У меня есть std :: vector, полный объектов, каждый из которых связан с числовым идентификатором группы. Объект также имеет такие свойства, как «размер» и «имя».

Мне нужно иметь возможность сортировать вектор объектов по имени, размеру и другим свойствам, сохраняя их сгруппированными (например, по указанному выше идентификатору группы).

Как можно достичь этой цели?

Answer 1

Используя STL, легко вставить свои собственные функции сравнения. Вы хотите определить функцию сравнения, которая сначала сравнивает группу, а затем сравнивает другие атрибуты.

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

Прежде всего, давайте перефразируем проблему. То, что вы действительно хотите, это отсортировать ваши объекты по идентификатору группы, а затем по (имени, размеру, ...). Если вы сначала отсортируете их по идентификатору группы, то, очевидно, объекты с одинаковым идентификатором группы будут слипаться.

Очевидно, что это легко сделать с помощью пользовательского предиката для std::sort. Что-то вроде этого:

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 3

Мне нужно иметь возможность сортировать вектор объектов по имени, размеру и другим свойствам, сохраняя их сгруппированными (например, по указанному выше идентификатору группы).

На самом деле, я пытаюсь сделать наоборот. Сначала я хочу отсортировать вектор по вторичному атрибуту (например, имени, размеру и т. Д.), А затем убедиться, что все элементы вектора содержатся в группах.

Результат должен быть одинаковым независимо от того, как вы о нем думаете, если только вы не хотите использовать вектор в промежуточном состоянии, где он не отсортирован по идентификатору группы. Если это не так, я не могу понять, почему нельзя использовать функцию сравнения, использующую два критерия (где идентификатор группы является основным условием, а имя / размер / другое является вторичным). Вы даже можете создать общий объект сравнения, который сочетает в себе использование двух предикатов (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"));
}

И просто для удовольствия, вот функтор, который объединяет n критерий сравнения (C ++ 0x только для шаблонов с переменными числами и синтаксиса инициализации нового стиля):

#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...};
}

Answer 4

Использовать идентификатор группы в качестве первичного ключа сортировки.

Например, для сортировки по группе, имени, размеру можно использовать объект сравнения, например:

 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 );
     }
 };

Затем передайте экземпляр этого в качестве третьего параметра в функцию std::sort().

Answer 5

Вы можете использовать partition или stable_partion, чтобы разделить ваши объекты на несколько наборов и отсортировать их по отдельности. Я не уверен, насколько это быстрее или медленнее, но мне кажется, что код будет немного более понятным.

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;
}