C++設置如何按值排序集和按鍵搜索

我正在實施A*最短路徑算法。 Openlist部分存儲將要訪問的所有節點。該列表就像一個優先級隊列，第一個元素具有最小的成本值，因此在每次迭代中，我們只需彈出第一個元素並訪問它。但是在迭代中，我們需要遍歷這個節點的鄰居，並檢查鄰居是否在Openlist中。C++設置如何按值排序集和按鍵搜索

因此，這意味着這Openlist需要支持兩種操作：

自動分揀
查找一個節點（通過其ID）

這裏的問題是，Openlist會按成本值排序，而查找需要基於鄰居節點（相鄰節點）的ID。所以我正在考慮使用set，其中的元素是節點。但是我不知道如何通過它在這個集合中的ID來查找元素。

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;

來源

2016-07-24 daydayup

保留兩個集合，一個用'f'索引，另一個用'id'索引。 –

你不會在一個集合中通過它的ID來查找元素 - 至少不是遍歷整個集合。這不是什麼套。 – immibis

@但find的set（）方法做什麼？ – daydayup

C++容器，像std::set，std::map，std::list，和std::vector，等人，是「單目的」或「原始」的容器。每個人都有一些獨特的屬性，可以將他們與其他容器區分開來;否則，當然，沒有理由將所有這些容器放在第一位。

std::set的目的是按值查找容器中的值，並且只在該集中存儲唯一值，就是這樣。

A std::set與其他關聯容器一樣，允許您指定一個可選的比較器類，它實際上指定容器中每個實際值的「值」的含義。而且你已經這樣做了，實際上，只是定義你的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中的內容時，請使用該映射來查找迭代器，然後對其進行解引用。問題解決了。

此外：

remove（）荷蘭國際集團從std::set一個astar_node也將需要從OpenList_by_id查找圖中除去它的迭代器。
由於std::set包含唯一值，因此需要處理集合中已存在具有相同f的astar_node並適當處理這種情況的情況。

來源

2016-07-25 00:12:12

謝謝先生！對於提供幫助，對於2，是使用multiset的答案嗎？謝謝。 – daydayup

是的，只要您希望支持多個值，'std :: multiset'將是最簡單的方法。 –

C++設置如何按值排序集和按鍵搜索

回答

相關問題