Как мне сравнить пары указателей (для предиката сортировки)

Question

У меня есть контейнер STL, полный миллиардов следующих объектов

pair<SomeClass*, SomeClass*>

Мне нужна функция следующего вида

/*returns items sorted biggest first */

bool sortPredicate (pair<SomeClass*, SomeClass*>two,  pair<SomeClass*, SomeClass*> one)
{
  return ???;
}

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

Редактировать 1: уточнение

В конце Я просто хочу отсортировать список пар указателей так, чтобы вседубликаты находятся рядом друг с другом .Предположим, что в SomeClass нет четкого метода, который можно было бы использовать для этой цели - у меня есть только пары указателей, и я хочу найти все идентичные пары (параллельно).Я думал, что сортировка поможет, но если вы можете придумать лучший параллельный метод, дайте мне знать.

Редактировать 2: Уточнение

Исправлен мой код(аргументы предиката сортировки были неверны - они должны быть парами).

Answer 1

Причуда C ++ заключается в том, что произвольные указатели одного и того же типа (не обязательно) сравнимы с <, но сравнимы с <code>std::less.

К сожалению, operator< для std::pairопределяется как operator< для компонентов, а не std::less.

Итак, предполагая, что вы хотите, чтобы две пары попали в одну и ту же позицию сортировки, если и только если они указывают на одни и те же два объекта, выneed:

// "less than"
template<typename T>
bool lt(const T &lhs, const T &rhs) {
    return std::less<T>()(lhs, rhs);
}

typedef std::pair<SomeClass*, SomeClass*> mypair;

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lt(lhs.first, rhs.first) 
        || (!lt(rhs.first, lhs.first) && lt(lhs.second, rhs.second));
 }

Почти во всех системах, которые вы можете назвать, это должно компилироваться с тем же кодом, что и return lhs < rhs;, но это не является формально правильным.Если ссылки всех указателей являются подобъектами одного и того же объекта (например, если у вас огромный массив, и все пары указывают на элементы этого одного массива), то operator< в порядке для указателей и, следовательно, в порядке для std::pair<pointer,pointer>.

Если вы хотите, чтобы пары попадали в одну и ту же позицию сортировки, если и только если объекты, на которые они указывают, сортируют одинаково, вы добавили бы разыменование:

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lt(*lhs.first, *rhs.first) 
        || (!lt(*rhs.first, *lhs.first) && lt(*lhs.second, *rhs.second));
 }

и, возможно, вы также добавите проверки на нулевые указатели, если они разрешены.Конечно, если вы знаете, что SomeClass действительно является типом класса, а не указателем, вам не нужно использовать std::less в вышеприведенной версии, просто определите operator< для SomeClass и:

inline bool lessptr(const SomeClass *lhs, const SomeClass *rhs) {
    if (lhs == 0) return rhs != 0;
    if (rhs == 0) return false;
    return *lhs < *rhs;
}

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lessptr(lhs.first, rhs.first) 
        || (!lessptr(rhs.first, lhs.first) && lessptr(lhs.second, rhs.second));
 }

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

Answer 2

Предполагая, что в вашем классе есть операторы сравнения:

bool sortPredicate (SomeClass *two,  SomeClass *one)
{
  return *two > *one;
}

Если вы просто хотите сравнить адреса указателей, используйте std::greater<T>:

sort(container.begin(), container.end(), std::greater<SomeClass *>());

РЕДАКТИРОВАТЬ: ОК, я действительно понятия не имею, что вы пытаетесь сделать с вашим последним редактированием Почему бы просто не использовать сортировку по умолчанию, если все, что вам нужно, это найти дубликаты?

Answer 3

Вы должны определить operator< в вашем классе пары.Я предполагаю, что ваша пара имеет item1 и item2.Итак:

template <class T>
class pair{
private:
  T item1;
  T item2
public:
  // [...] other stuff goes here
  // here the comparing
  bool operator<(pair p){
    return (item1 < p.item1 || (item1 == p.item1 && item2 < p.item2));
  }
};

Это решение предполагает, что элементы определили операторы < и ==.

Полагаю, я не встретил то, что вы искалино я рекомендую перегрузить операторы <, > и == в классе вашей пары.

Answer 4

Если я правильно понимаю, ваш предикат должен иметь следующую подпись

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs);

Я ничего не знаю о вашем классе и о том, есть ли для него естественный порядок, поэтому трудно догадаться, как вы хотите его отсортировать. В комментарии вы пишете, что самые большие предметы должны быть первыми. Я предполагаю, что есть <оператор для класса. Как насчет этого? </p>

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs)
{
    if(!(*(lhs.first) < *(rhs.first) || *(rhs.first) < *(lhs.first))) // If there is == operator use it.
    {
        return *(rhs.second) < *(lhs.second);
    }
    else
    {
        return *(rhs.first) < *(lhs.first);
    }

}

РЕДАКТИРОВАТЬ: Хорошо, спасибо за разъяснения. Как насчет этого?

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs)
{
    if(lhs.first == rhs.first)
    {
        return rhs.second < lhs.second;
    }
    else
    {
        return rhs.first < lhs.first;
    }
}