станд.:: набор с определяемым пользователем типом, как не гарантировать дубликаты

Вот мои 2 цента о MVC для веб-приложений. Для вида приложений для GUI, для которых был первоначально предназначен MVC, требовался код "слушателя", так, чтобы UI мог быть обновлен, когда события изменили данные модели.

В MVC для сети это является ненужным, Вы получаете своего слушателя бесплатно: веб-сервер и Запрос HTTP ЯВЛЯЮТСЯ событием. Таким образом, действительно MVC для сети должен быть еще более простым. Действительно, это могло быть сведено к шаблону Посредника, где Контроллер посредничает между моделью и представлением.

существует две вещи, что существует много беспорядка о. Независимо от стандартной "мудрости":

Платформы! = данные MVC

Базы данных! = "Модель"

"Полный стек" платформы веб-разработки обычно добавляет много опций, и можете, или может не быть MVC-ориентирован в их ядре. Одной из опций, которые добавляют много платформ, является доступ к базе данных, или возразите реляционной функциональности отображения, и потому что платформы и MVC запутываются, впоследствии данные базы данных и образцовый фасет MVC также запутываются. Модель может обычно просматриваться как базовые данные для приложения, но это не должно прибывать из базы данных. Хорошим примером могла бы быть Wiki, где базовая модель/данные состоит из данных версии файла, например, от RCS.

Hope это помогает, и я уверен, что у других будет много для добавления.

59
задан DeusAduro 11 July 2009 в 22:50
поделиться

6 ответов

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

103
ответ дан 24 November 2019 в 18:10
поделиться

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

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

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

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

4
ответ дан 24 November 2019 в 18:10
поделиться

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

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.
}
31
ответ дан 24 November 2019 в 18:10
поделиться

Остерегайтесь последствий этого. Похоже, вы пытаетесь сделать что-то вроде 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;
0
ответ дан 24 November 2019 в 18:10
поделиться

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

//! 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 использует интросорт.

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

Редактировать: только что заметил, что вы сказали, что хотите «сохранить» порядок сортировки , не то чтобы вы хотели обрабатывать все одновременно. Прости за это. Если вы хотите эффективно поддерживать порядок и исключать дубликаты при добавлении элементов, я бы рекомендовал использовать набор или неупорядоченный набор, который я определил выше, в зависимости от положения, а также std :: multiset , который будет поддерживать порядок оператора <. Для каждого нового элемента выполните:

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, но лучше, если будет много повторений.

а также std :: multiset , который будет поддерживать порядок оператора <. Для каждого нового элемента выполните:

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, но лучше, если будет много повторений.

а также std :: multiset , который будет поддерживать порядок оператора <. Для каждого нового элемента выполните:

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, но лучше, если будет много повторений.

2
ответ дан 24 November 2019 в 18:10
поделиться

Компаратор 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

Дубликаты. Сбой магического компаратора. Различные элементы в наборе имеют одинаковое значение равенство и, следовательно, сравнивают то же самое с operator == , потому что во время вставки набор никогда не сравнивал новый элемент с его дубликатом. Единственный дубликат, который был исключен, - 4, потому что два 4 ' c) неверно, поскольку 1 == 1 (равенство)

7
ответ дан 24 November 2019 в 18:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: