data structure for sorting a list of pairs

[Tagore]

Hi,
I want to sort a list of pairs based on key values. e.g. If my pairs
are like
(4,3)
(2,8)
(3,10)
(19,23)
(13,14)

then I would like to sort this with final list as:
(2,8)
(3,10)
(4,3)
(13,14)
(19,23)


What would be best data structure for this in C++?

Thanks,

 

[Kai-Uwe Bux]

Hi,
I want to sort a list of pairs based on key values. e.g. If my pairs
are like
(4,3)
(2,8)
(3,10)
(19,23)
(13,14)

then I would like to sort this with final list as:
(2,8)
(3,10)
(4,3)
(13,14)
(19,23)


What would be best data structure for this in C++?

Depends (among other things on your notion of "best").

If your application is strictly ordered as fill-sort-lookup then a
std::vector with std::sort will be efficient in terms of memory and speed.
The lookup, you could realize efficiently via binary_search with a custom
predicate only looking at the keys.

If you need to mix inserting and lookup and you want a data structure that
keeps the collection of pairs sorted all the time, then std::multiset is
more appropriate.


Best

Kai-Uwe Bux

 

[Jorgen Grahn]

std::list<std:air<int, int> > listOfPairsOfInts;
...
// add elements to listOfPairsOfInts
...
listOfPairsOfInts.sort();

Depends on what he really wanted. He uses the word "key", so maybe
he doesn't want lexicographical sort on the std:air. Maybe,

/Jorgen