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

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

Определяемый пользователем тип:

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

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

вопрос задан 11.07.2009
DeusAduro
3816 репутация

6 ответов


  • 93 рейтинг

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

    ответ дан Paul, с репутацией 10733, 11.07.2009
  • 31 рейтинг

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

    std::set 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.
    }
    
    ответ дан Mehrdad Afshari, с репутацией 335708, 11.07.2009
  • 6 рейтинг

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

    #include 
    #include 
    #include 
    #include 
    
    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 {
        bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const
        {
            return !(lhs == rhs) && (lhs < rhs);
        }
    };
    
    int main() {
        std::set 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(std::cout, "\n"));
    }
    

    Выход:

    0
    1
    2
    3
    4
    3
    2
    1
    0
    

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

    Из стандарта C ++: 25. 3: 3 «Чтобы алгоритмы работали правильно, comp должен вызывать строгий слабый порядок значений».

    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 & lt; 2 (заказ)
    • comp(b,c) верно с 2! = 1 (равенство) и 2 & lt; 9 (заказ)
    • comp(a,c) неверно, поскольку 1 == 1 (равенство)
    ответ дан Steve Jessop, с репутацией 229130, 14.07.2009
  • 4 рейтинг

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

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

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

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

    ответ дан Greg Hewgill, с репутацией 645957, 11.07.2009
  • 3 рейтинг

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

    //! 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 routeset;
    // ... add each RouteElem to the set ...
    
    // now copy the RouteElems into a vector
    std::vector 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, который будет поддерживать порядок 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, но лучше, если будет много повторений.

    ответ дан Steve Jessop, с репутацией 229130, 11.07.2009
  • 0 рейтинг

    Остерегайтесь последствий этого. Похоже, вы пытаетесь сделать что-то вроде 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
    {
        bool operator()(const RouteElem& lhs, const RouteElem& rhs) const
        {
            return !(lhs == rhs) && (lhs < rhs);
        }
    };
    
    std::set my_set;
    
    ответ дан rlbond, с репутацией 37768, 11.07.2009