Как я могу определить сортировку «Do-Nothing»?

Question

Я работаю над системой, где мне нужно иметь возможность сортировать вектор по заданному предикату, который мои классы не должны контролировать. В принципе, я передаю им производный класс, и они слепо сортируются по нему.

Как один из «восхитительных причуд», одним из шаблонов сортировки является порядок ввода. Вот что у меня до сих пор.

struct Strategy 
{ 
    virtual bool operator()(const Loan& lhs, const Loan& rhs) const = 0; 
}; 

struct strategyA : public Strategy 
{ 
    bool operator()(const Loan& lhs, const Loan& rhs) const 
    { 
     return true; 
    } 
}; 

struct strategyB : public Strategy 
{ 
    bool operator()(const Loan& lhs, const Loan& rhs) const 
    { 
     return lhs.getID() > rhs.getID(); 
    } 
}; 

struct strategyC : public Strategy 
{ 
    bool operator()(const Loan& lhs, const Loan& rhs) const 
    { 
     return lhs.getFee() > rhs.getFee(); 
    } 
}; 

Очевидно, что strategyA рефлексивно, она не может быть использована, и если установить его на ложь, он будет относиться ко всему, как равно и я могу поцеловать меня на прощание данных.

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

Я знаю, что, возможно, самым простым решением является добавление порядка ввода переменной в класс займа или партнер с одним в паре. В качестве альтернативы я мог бы подать параметр с помощью предиката, который сообщает сортировщику, использовать его или нет.

Answer 1

Лично я думаю, что ваш класс стратегии должен иметь «сортировку» метод. Таким образом, он может либо вызвать std :: sort, либо не так, как он считает нужным. , а также как часть стратегии сортировки.

Darios stable_sort ответ очень хороший, если вы можете его использовать.

Можно сортировать по позиции позиции в векторе, но это не означает, что элементы не будут перемещаться (многие алгоритмы сортировки будут в основном скремблировать, а затем использовать ваши данные), поэтому вам нужно иметь некоторые надежный способ определения, где были элементы, когда вы начали.

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

Другая проблема - в зависимости от контейнера - порядок адресов (скажем) не всегда соответствует порядку элементов.

Answer 2

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

Answer 3

Есть ли способ определения предикатной функции для сортировки вектора, который ничего не изменит?

Это зависит от алгоритма. Если ваш вид stable sort, порядок «равных» элементов не будет изменен (что не определено для нестабильных родов).

Рассмотрите возможность использования std::stable_sort.

Answer 4

Нет функции сортировки, которая будет хранить порядок элементов, основанных только на значениях элементов. Если это возможно, вам необходимо предоставить дополнительную информацию для вашего Strategy.

Answer 5

Другой подход может заключаться в том, чтобы привести семантику ваших данных в контейнер. Рассмотрите возможность использования подталкивания :: multi_index для различных способов доступа и упорядочения на те же данные:

http://www.boost.org/doc/libs/1_42_0/libs/multi_index/doc/index.html