C++ задает порядок сортировки по значению и поиск по ключу

Question

Я реализую алгоритм кратчайшего пути A*. Часть Openlist хранит все узлы, которые будут посещены. Список похож на приоритетную очередь, что первый элемент имеет минимальное значение стоимости, поэтому на каждой итерации мы просто выставляем первый элемент и посещаем его. Но внутри итерации нам нужно пересечь соседей этого узла и проверить, находится ли сосед в Openlist.

Так что означает этот Openlist должен поддерживать два типа операций:

1. автоматических сортировку
2. посмотреть узел (по идентификатору)

Проблема здесь состоит в том, что Openlist будет сортировать по стоимости, в то время как поиск должен основываться на идентификаторе соседнего узла (соседних узлов). Поэтому я рассматривал возможность использования set, где элементы являются узлами. Но я не знаю, как искать элемент по его идентификатору в этом наборе.

struct astar_node 
{ 
    string id; 
    double f; //estimated cost; 
    double g; //distance from source to this node; 
    double h; //heuristic cost from this node to target; 
}; 

struct openlist_compare 
{ 
    bool operator()(const astar_node &node1, const astar_node &node2){ 
      return node1.f < node2.f ; 
    } 
}; 

std::set<astar_node, openlist_compare> Openlist; 

Answer 1

C++ контейнеры, как std::set, std::map, std::list и std::vector, и другие, "единственная цель", или "примитивные" контейнеры. Каждый из них обладает определенными уникальными свойствами, отличающими их от других контейнеров; в противном случае, конечно, не было бы причин иметь все эти контейнеры, конечно.

Целью std::set является поиск значений в контейнере по значению и сохранение только уникальных значений в наборе, вот и все.

A std::set, как и другие ассоциативные контейнеры, позволяет указать необязательный класс компаратора, который определяет, по сути, то, что означает «значение» для каждого фактического значения в контейнере. И вы сделали это, по сути, определяя, что только член f вашего класса astar_node имеет значение для определения того, что содержит набор. Все остальные значения всех остальных членов astar_node игнорируются.

Как только это будет сделано, это все, что касается std::set. Набор можно найти на astar_node::f, и все. Это единственный способ найти что-то в наборе.

Как я сказал в начале, std::set и другие, являются «примитивными» контейнерами, а иногда вам понадобится нечто более сложное, как в данном случае. В этой ситуации вы можете использовать несколько контейнеров и комбинировать их таким образом, чтобы достичь желаемого результата. Нет закона против использования более чем одного контейнера для хранения одного набора данных. Не существует закона, в котором говорится, что вы должны использовать один контейнер, чтобы делать все, что вам нужно, с определенным набором данных.

Здесь, как я понимаю, вам также нужно найти astar_node в наборе по значению id.

Файн:

typedef std::set<astar_node, openlist_compare> openlist_t; 

openlist_t Openlist; 

std::map<std::string, openlist_t::iterator> OpenList_by_id; 

После insert() новый astar_node в свой OpenList, insert() возвращает итератор для нового элемента в openlist_t. Вы получаете итератор для вставленного astar_node. Возьмите этот итератор и поместите его в OpenList_by_id, с ключом id.

Теперь, когда вы хотите найти что-то в OpenList с учетом id, используйте карту, чтобы найти итератор, затем разыщите ее. Задача решена.

Дополнительно:

1. remove() ING в astar_node из std::set также потребует удаления его итератор с карты OpenList_by_id поиска.

2. Поскольку std::set содержит уникальные значения, вы должны справиться с ситуацией, когда astar_node с тем же f уже существует в наборе, и справиться с этой ситуацией должным образом.