C++ sorting algorithm

Question

Thanks for looking at this question in advance.

I am trying to order the following list of items:

Bpgvjdfj,Bvfbyfzc
Zjmvxouu,Fsmotsaa
Xocbwmnd,Fcdlnmhb
Fsmotsaa,Zexyegma
Bvfbyfzc,Qkignteu
Uysmwjdb,Wzujllbk
Fwhbryyz,Byoifnrp
Klqljfrk,Bpgvjdfj
Qkignteu,Wgqtalnh
Wgqtalnh,Coyuhnbx
Sgtgyldw,Fwhbryyz
Coyuhnbx,Zjmvxouu
Zvjxfwkx,Sgtgyldw
Czeagvnj,Uysmwjdb
Oljgjisa,Dffkuztu
Zexyegma,Zvjxfwkx
Fcdlnmhb,Klqljfrk
Wzujllbk,Oljgjisa
Byoifnrp,Czeagvnj

Into the following order:

Bpgvjdfj
Bvfbyfzc
Qkignteu
Wgqtalnh
Coyuhnbx
Zjmvxouu
Fsmotsaa
Zexyegma
Zvjxfwkx
Sgtgyldw
Fwhbryyz
Byoifnrp
Czeagvnj
Uysmwjdb
Wzujllbk
Oljgjisa
Dffkuztu

This is done by:

1. Taking the first pair and putting the names into a list
2. Using the second name of the pair, find the pair where it is used as the first name
3. Add the second name of that pair to the list
4. Repeat 2 & 3

I am populating an unordered_map with the pairs then sorting and adding each name to a list. This can be seen in the following code:

westIter = westMap.begin();
std::string westCurrent = westIter->second;
westList.push_front(westCurrent);

for(int i = 0; i < 30; i++)
{
    if(westMap.find(westCurrent) != westMap.end())
    {
        //find pair in map where first iterator is equal to "westCurrent"
        //append second iterator of pair to list
    }
    westIter++;
}

Note: I'm not sure if "push_front" is correct at this moment in time as I have only got the first value inserted.

My question is could someone give me some insight as to how I could go about this? As I am unsure of the best way and whether my thinking is correct. Any insight would be appreciated.

Answer 1

There is but one weakness in your plan. You need to first find the first person of the chain, the Mr New York.

Your algorithm assumes the line starts with the first guy. For that to work, you should first scan the entire map to find the one name that does not appear as a second element. That is Mr New York and you can proceed from there. push_back is what you would need to use here.

Answer 2

1. Create a data structure that stores a chain, its front and back. Store in a hash table with 'back' as key.
2. Create a bunch of singleton chains (one for each element)
3. Iteratively, pick a chain find its 'front' in the hash table (i.e. find another chain that has the same element as 'back') and merge them
4. Do it until you are left with only one chain