(w C++)
Mam elementy drzewka typy (klucz, klucz parenta), root ma własny klucz i
klucz parenta==NULL. Są umieszczone w pliku losowo, można do
optymalizacji założyć że nie całkiem losowo.
Zabrałem się to tego tak:
klucz jest haszem - stringiem
biorę mapę unordered_map<string, CChainNode*> map;
następnie pierwsza faza:
pętla po wszystkich elementach przy założeniu że trochę jest po kolei:
szukanie parenta i te, które nie znaleziono, dodawane do wektora:
for (int j = 1; j < vecAllElems.size(); j++)
{
CChainNode *elem = vecAllElems[j];
unordered_map<string, CChainNode*>::const_iterator iter =
map.find(elem->strHashPrevBlock);
if (iter == map.end())
{
vecNotFound.push_back(elem);
}
else
{
CChainNode *parent = iter->second;
map[elem->strHashBlock] = elem;
parent->Add(elem);
}
}

Następnie próbowałem, ale to mi nie wychodzi, bo bardzo długo oblicza:
while (foundInRund>0)
{
int j = 0;
foundInRund = 0;
while (j < vecNotFound.size())
{
CChainNode *elem = vecNotFound[j];
unordered_map<string, CChainNode*>::const_iterator iter =
map.find(elem->strHashPrevBlock);
if (iter == map.end())
j++;
else
{
CChainNode *parent = iter->second;
map[elem->strHashBlock] = elem;
vecNotFound.erase(vecNotFound.begin() + j);
foundInRund++;
parent->Add(elem);
break; //from beginning
}
}
}
Skoro jest while (foundInRund>0), to powinien znaleźć wszystkie , choć
to może długo trwać, ale dla niektórych danych znajduje coś za mało.

Jak zrobić? może tworzyć wiele (tysięcy nawet) osobnych niepowiązanych
drzewek, a potem łączyć je w jedno?
Problemem jest to, że często najpierw w pliku występuje child a potem
parent.