c ++ 11 — Как эффективно отсортировать четырехместные структуры в C ++?

Question

c ++ 11 — Как эффективно отсортировать четырехместные структуры в C ++?

У меня есть структура с членами x, y, z и w. Как мне эффективно сортировать
сначала по x, затем по y, по z и, наконец, по w в C ++?

5

c++c++11 lexicographic stl tuples

Решение

Другие решения

Вы можете превратить структуру в std::tuple с помощью std::tieи использовать лексикографическое сравнение std::tuple::operator<, Вот пример использования лямбды для std::sort

#include <algorithm>
#include <tuple>
#include <vector>

struct S
{
// x, y, z, w can be 4 different types!
int x, y, z, w;
};

std::vector<S> v;

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) {
return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w);
});

Этот пример поставки std:sort с оператором сравнения на лету. Если вы всегда хотите использовать лексикографическое сравнение, вы можете написать нечлен bool operator<(S const&, S const&) который будет автоматически выбран std::sortили заказанными ассоциативными контейнерами типа std::set а также std::map,

Что касается эффективности, от онлайн ссылка:

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

Если у вас есть среда C ++ 11, предпочтите std::tie за рукописные решения, приведенные здесь. Они более подвержены ошибкам и менее читабельны.

6

Это решение имеет не более 4 сравнений на элемент-сравнение и не требует построения других объектов:

// using function as comp
std::sort (quadrupleVec.begin(), quadrupleVec.end(), [](const Quadruple& a, const Quadruple& b)
{
if (a.x != b.x)
return a.x < b.x;

if (a.y != b.y)
return a.y < b.y;

if (a.z != b.z)
return a.z < b.z;

return a.w < b.w;
});

2

Если вы катите свой собственный оператор сравнения, то вы можете свободно бросать объекты в std::mapS или вызвать std::sort, Эта реализация разработана, чтобы быть простой, чтобы вы могли легко проверить и изменить ее при необходимости. Только используя operator< чтобы сравнить x, y, z и w, он минимизирует количество операторов, которые вам могут понадобиться реализовать, если эти переменные еще не сопоставимы (например, если они являются вашими собственными структурами, а не целыми числами, double, std :: strings и т. д.) ,

bool operator<(const Q& lhs, const Q& rhs)
{
if (lhs.x < rhs.x) return true;
if (rhs.x < lhs.x) return false;
if (lhs.y < rhs.y) return true;
if (rhs.y < lhs.y) return false;
if (lhs.z < rhs.z) return true;
if (rhs.z < lhs.z) return false;
if (lhs.w < rhs.w) return true;
return false;
}

Иногда типы будут определять функцию сравнения, которая возвращает -1, 0 или 1, чтобы указать, что меньше, равно или больше, чем оба, в качестве способа поддержки реализации <, <=, ==, !=, >= а также > а также потому, что иногда делаю < затем != или же > будет повторять большую работу (рассмотрим сравнение длинных текстовых строк, где отличается только последний символ). Если x, y, z и w относятся к таким типам и имеют функцию сравнения с более высокой производительностью, вы можете улучшить общую производительность с помощью:

bool operator<(const Q& lhs, const Q& rhs)
{
int c;
return (c = lhs.x.compare(rhs.x) ? c :
(c = lhs.y.compare(rhs.y) ? c :
(c = lhs.z.compare(rhs.z) ? c :
lhs.w < rhs.w;
}

2

Источник

Accepted Answer

Если вы хотите реализовать лексикографический порядок, то самый простой способ — это использовать std::tie реализовать оператор сравнения или функтор сравнения меньше или больше, а затем использовать std::sort на коллекции ваших структур.

struct Foo
{
T x, y, z, w;
};

....
#include <tuple> // for std::tie

bool operator<(const Foo& lhs, const Foo& rhs)
{
// assumes there is a bool operator< for T
return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

....

#include <algorithm> // for std::sort

std::vector<Foo> v = ....;
std::sort(v.begin(), v.end());

Если нет естественного заказа для Fooбыло бы лучше определить функторы сравнения, а не реализовывать операторы сравнения. Затем вы можете передать их для сортировки:

bool cmp_1(const Foo& lhs, const Foo& rhs)
{
return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

std::sort(v.begin(), v.end(), cmp_1);

Если у вас нет C ++ 11 tuple поддержка, вы можете реализовать это с помощью std::tr1::tie (используйте заголовок <tr1/tuple>) или используя boost::tie от библиотека boost.tuple.

9