Вы можете попробовать что-то вроде следующего:
//! 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, но лучше, если будет много повторений.