Mapa c++ , sortowanie po wartości

Mam klasę Node, która posiada instancję Point2d oraz pewien atrybut liczbowy oceniający ten węzeł. Chcę mieć mapę w stylu: unordered_map<int, Node*>, gdzie funkcja hashująca wygląda tak:

return point.x << 16 + point.y

Problemem jest to, że potrzebuje mieć tę mapę cały czas posortowaną wg tej oceny - od najlepszego do najgorszej.
Sortowanie musi być szybkie, bo jest w pętli. Nody są cały czas tworzone dynamicznie i dodawane do tej mapy. Potrzebny jest też dostęp przez hasz.

Jak to ugryźć?

Użyj zwykłej mapy, ona jest sortowana po kluczu. Jako klucz przyjmij hash.

struct Point2D{
	unsigned x, y;
};

unsigned myhash(Point2D const& p) {
	return (p.x << 16) + p.y;
}

int main()
{
	map<int, Point2D> m;

	auto add = [&m](Point2D const& p){
		m[myhash(p)] = p;
	};

	add({2,3});
	add({2,4});
	add({1,3});
}

http://melpon.org/wandbox/permlink/bKlB8DXW0YMJKAaH

Tylko, że hash != od tego po czym chce sortować. Tak to sprawa była by prosta.

W takim razie polecam Boost.MultiIndex ( http://www.boost.org/doc/libs/1_55_0/libs/multi_index/doc/index.html )

struct Point2D{
	struct ID{};
	struct Hash{};

	unsigned x, y;
};

unsigned myhash(Point2D const& p) {
	return (p.x << 16) + p.y;
}

unsigned myhash_on_pair(pair<int,Point2D> const& p){
	return myhash(p.second);
}
namespace mi = boost::multi_index;

typedef boost::multi_index_container<
	pair<int,Point2D>,
	mi::indexed_by<
		mi::hashed_non_unique<
			mi::tag<Point2D::ID>,
			mi::member<pair<int,Point2D>,int,&pair<int,Point2D>::first>
		>,
		mi::ordered_non_unique<
			mi::tag<Point2D::Hash>,
			mi::global_fun<pair<int,Point2D> const&, unsigned, &myhash_on_pair>
		>
	>
> custom_map;

Działanie: http://melpon.org/wandbox/permlink/kfvkD1deOGCppyUU

To stwórz hash który jest "sklejką" tego po czemu chcesz sortować plus ten obecny unikalny i po sprawie.

To nie można mieć po prostu dwóch kolekcji - jednej posortowanej po tym, po czym chce sortować z dostępem O(log n), drugiej do wyszukiwania po haszu z czasem O(1)?

Z dwoma kolekcjami jest pewien problem w kontekście implementacji tego algorytmu: Chodzi o algorytm Pathfinder A* http://theory.stanford.edu/~amitp/GameProgramming/

Na razie mam tak: zbiór "opened" to std::vector<Node*> (nie optymalnie) a closed to std::unordered_map<hash, Node*>
Problem sprowadza się do tego, że dla "opened" muszę mieć posortowane wg "node->f" ale także dostęp do po hashu, do dowolnego elementu. Gdy kluczem to byłby "node->f", to rodzi to problemy w dostępie do elementu.