std::set с определяемым пользователем типом, как обеспечить отсутствие дубликатов

Question

Таким образом, у меня есть std::set, который должен сохранять определенный порядок, а также не допускать дублирования определенного пользователем типа. Теперь я могу заставить ордер работать правильно, перегрузив оператор "<" в моем типе. Тем не менее, набор не может надлежащим образом обнаруживать дубликаты, и, честно говоря, я не совсем уверен, как это происходит внутри страны. Я перегрузил оператор '==', но почему-то я не уверен, что это то, что на самом деле использует набор? Итак, вопрос в том, как набор определяет дубликаты при добавлении значений? Вот соответствующий код:

Пользовательский тип:

//! An element used in the route calculation.
struct RouteElem {
    int shortestToHere; // Shortest distance from the start.
    int heuristic;      // The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
        return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
        return (position.x == other.position.x && position.y == other.position.y);
    }
};

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

Answer 1

operator== не используется std::set, элементы a а также b считаются равными, если !(a < b) && !(b < a)

Answer 2

std::set поддерживает указание функции сравнения. По умолчанию less который будет использовать operator < проверить равенство. Вы можете определить пользовательскую функцию для проверки равенства и использовать ее вместо:

std::set<RouteElem, mycomparefunction> myset; 

Обратите внимание, что невозможно отделить функцию сравнения от функции сортировки. std::set является двоичным деревом, и если элемент в двоичном дереве не больше или меньше, чем определенный элемент, он должен быть в том же месте. Это делает что-то вроде этого в алгоритме поиска места:

if (a < b) {
    // check the left subtree
} else if (b < a) {
    // check the right subtree
} else {
    // the element should be placed here.
}

Answer 3

Компаратор rlbond не предотвращает вставку элементов, которые сравниваются одинаково. Очевидно, что это трудно доказать в комментариях, учитывая ограничение на количество символов, поскольку rlbond считает, что std::set гарантирует, что он никогда не будет содержать два элемента с !compare(a,b) && !compare(b,a) для его компаратора. Однако компаратор rlbond не определяет строгий порядок и поэтому не является допустимым параметром для std::set.

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

struct BrokenOrder {
    int order;
    int equality;

    public:
    BrokenOrder(int o, int e) : order(o), equality(e) {}

    bool operator<(const BrokenOrder &rhs) const {
        return order < rhs.order;
    }
    bool operator==(const BrokenOrder &rhs) const {
        return equality == rhs.equality;
    }
};

std::ostream &operator<<(std::ostream &stream, const BrokenOrder &b) {
    return stream << b.equality;
}

// rlbond's magic comparator
struct LessThan : public std::binary_function<BrokenOrder, BrokenOrder, bool> {
    bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const
    {
        return !(lhs == rhs) && (lhs < rhs);
    }
};

int main() {
    std::set<BrokenOrder,LessThan> s;
    for (int i = 0; i < 5; ++i) {
        s.insert(BrokenOrder(i,i));
    }
    for (int i = 0; i < 5; ++i) {
        s.insert(BrokenOrder(10-i,i));
    }
    std::copy(s.begin(), s.end(), 
        std::ostream_iterator<BrokenOrder>(std::cout, "\n"));
}

Выход:

0
1
2
3
4
3
2
1
0

Дубликаты. Волшебный компаратор не удался. Различные элементы в наборе имеют одинаковое значение equalityи, следовательно, сравнить то же самое с operator==потому что во время вставки набор никогда не сравнивал новый элемент с его дубликатом. Единственный дубликат, который был исключен, был 4, потому что у двух 4 были порядки сортировки 4 и 6. Это поместило их достаточно близко друг к другу в наборе, чтобы сравнить их друг с другом.

От стандарта C++: 25.3:3 "Чтобы алгоритмы работали правильно, комп должен вызывать строгий слабый порядок значений".

25.3: 4 "... требования состоят в том, чтобы comp и эквивалентные оба были транзитивными отношениями:

comp(a,b) && comp(b,c) implies comp(a,c)"

Теперь рассмотрим элементы a = BrokenOrder(1,1), b = BrokenOrder(2,2), а также c = BrokenOrder(9,1), а также comp конечно, равен волшебному компаратору. Затем:

• comp(a,b) верно, так как 1!= 2 (равенство) и 1 < 2 (порядок)
• comp(b,c) верно, так как 2!= 1 (равенство) и 2 < 9 (порядок)
• comp(a,c) ложно, так как 1 == 1 (равенство)

Answer 4

Реализация набора STL концептуально делает что-то подобное для обнаружения равенства:

bool equal = !(a < b) && !(b < a);

То есть, если два элемента оба не меньше других, то они должны быть равны. Вы можете проверить это, установив точку останова на вашем operator==() метод и проверка, чтобы увидеть, вызывается ли он вообще.

Я бы вообще с подозрением относился к операторам сравнения, которые проверяют совершенно разные вещи. Ваш < Оператор определяется с точки зрения двух вещей, которые отличаются от того, как ваш == Оператор определен. Как правило, вы хотите, чтобы такие сравнения использовали согласованную информацию.

Answer 5

Вы можете попробовать что-то вроде следующего:

//! An element used in the route calculation.
struct RouteElem {
    int shortestToHere; // Shortest distance from the start.
    int heuristic;              // The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
      return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
      return (position.x == other.position.x && position.y == other.position.y);
    }
};

struct CompareByPosition {
    bool operator()(const RouteElem &lhs, const RouteElem &rhs) {
        if (lhs.position.x != rhs.position.x) 
            return lhs.position.x < rhs.position.x;
        return lhs.position.y < rhs.position.y;
    }
};

// first, use std::set to remove duplicates
std::set<RouteElem,CompareByPosition> routeset;
// ... add each RouteElem to the set ...

// now copy the RouteElems into a vector
std::vector<RouteElem> routevec(routeset.begin(), routeset.end());

// now sort via operator<
std::sort(routevec.begin(), routevec.end());

Очевидно, что есть копия в середине, которая выглядит медленно. Однако любая структура, которая индексирует элементы по двум различным критериям, будет иметь дополнительные издержки на элемент по сравнению с набором. Весь приведенный выше код O(n log n), предполагая, что ваша реализация std::sort использует introsort.

Если у вас есть, по этой схеме вы можете использовать unordered_set вместо set сделать первоначальную унификацию. Поскольку хеш должен зависеть только от x и y, он должен быть быстрее, чем O(log N) сравнения, требуемые для вставки в набор.

Изменить: только что заметил, что вы сказали, что хотите "сохранить" порядок сортировки, а не что вы хотите обрабатывать все в пакете. Извини за это. Если вы хотите эффективно поддерживать порядок и исключать дубликаты при добавлении элементов, то я бы рекомендовал использовать набор или неупорядоченный набор, который я определил выше, на основе позиции, а также std::multiset<RouteElem>, который будет поддерживать operator< порядок. Для каждого нового элемента выполните:

if (routeset.insert(elem).second) {
    routemultiset.insert(elem);
}

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

if (routeset.insert(elem).second) {
    try {
        routemultiset.insert(elem); // I assume strong exception guarantee
    } catch(...) {
        routeset.erase(elem); // I assume nothrow. Maybe should check those.
        throw;
    }
}

Или эквивалент RAII, который будет более многословным, если в вашем коде есть только одно место, в котором вы когда-либо используете класс RAII, но лучше, если будет много повторений.

Answer 6

Остерегайтесь последствий этого. Похоже, вы пытаетесь сделать что-то вроде A*, и если вы попытаетесь вставить "дубликат", он будет проигнорирован, даже если есть "лучший" маршрут.

ПРИМЕЧАНИЕ. Это решение не работает, см. Объяснение ниже.

struct RouteElem 
{
    int shortestToHere; // Shortest distance from the start.
    int heuristic;              // The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
        return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
        return (position.x == other.position.x && position.y == other.position.y);
    }
};

struct RouteElemLessThan : public std::binary_function<RouteElem, RouteElem, bool>
{
    bool operator()(const RouteElem& lhs, const RouteElem& rhs) const
    {
        return !(lhs == rhs) && (lhs < rhs);
    }
};

std::set<RouteElem, RouteElemLessThan> my_set;