How do I insert a list of pairs most efficiently?

Supose i have

(A,B)
(A,C)
(A,D)
(B,C)
(B,D)
(C,D)
(D,E)

in a text file. I'll extract it using regular expressions.

I would like to insert the data in to a container so that it looks like this.

A->B,C,D
B-开发者_StackOverflow>C,D
C->D
D->E

Which container do I use?

I need to be able to look up data on both the left hand and right hand side of the container, i.e. by key an value. So I need to be able to search/lookup

A,B,C,D in

A->B,C
B->C,D
C->D
D->E

and the B,C in

A->B,C

std::multimap comes to mind... Is basically a map, but allows duplicates in the map key (i.e. you can have multiple "A" keys, each mapping to a "B", "C" or "D" key, to continue your example).

EDIT: In response to Chris' comment: you insert items into a multimap in the same manner as a map - you make a std::pair object containing the key and value, then insert that into the multimap:

std::multimap<char, char> myMap;
myMap.insert(std::pair<char, char>('A', 'B'));
myMap.insert(std::pair<char, char>('A', 'C'));
myMap.insert(std::pair<char, char>('A', 'D'));
myMap.insert(std::pair<char, char>('B', 'C'));
// ... etc

Assuming here that you literally are examining characters, and A, B, C etc aren't stand-ins for something else. If they are stand-ins, adjust as appropriate.

You can then query the multimap for all values under the key 'A' as follows:

typedef std::multimap<char, char>::iterator mmIter; // For brevity...
std::pair<mmIter, mmIter> iters = myMap.equal_range('A');
// Iterate over values for key
for (mmIter iter = iters.first ; iter != iters.second; ++iter)
{
    // Print out value.
    cout << " " << (*iter).second;
}

multimap.equal_range returns a pair containing iterators to the first entry matching the key, and the entry immediately following the last entry matching the key. Therefore, these can be used to iterate over the entries, as demonstrated.

EDIT 2 just realised what you really meant by your comment. Multimap does not natively support bidirectional operation (i.e. lookup on value as well as on key), so you might then need to maintain two multimaps - one for each direction. This can be a pain to do though - it can be tricky ensuring that the two remain properly synchronised.

Alternatively, I'm sure there's some Boost class that would serve the purpose (I don't actually know - I don't use Boost myself, but I'm sure someone else should be able to provide more detail).

Assuming you have to lookup the data on the righthand side using the 'key' on the lefthand side, I'd use a multimap to store these values.

The other alternative would be something like a std::map<keytype, std::vector<valuetype> >.