C++: how to store a sorted set of tuples?

Using GCC 4.x, g++ and STL. Which internal structure should be used to hold such array: ( (开发者_如何学JAVA1,4), (2,8), (3,7) )? It should have static element numbers to keep the original (as added) order.

Variants:

• set<map(int,int)>
• array<map>
• array {array[2], array[2]}

Can this be done with vectors in a better looking way?

If it's already sorted, then a vector<pair<int, int> > makes more sense as it will allow you to preserve the insert order (which will be sorted order anyway!). Question is whether you want to sort on insert or not?

std::set holding std::pair is what first comes to mind

however this might not comply with this requirement:

It should have static element numbers to keep the original (as added) order.

It totally depends on your insertion/extraction use-case. In any case, you should use std::pair or boost::tuple as your element type, as they already implement the lexicographical ordering you want.

As for the container and insertion/extraction: Can you live without random-access? Do you need access to all elements (use std::set) or just the top (use std::priority_queue with std::vector)? If you need random access, use a bare std::vector: are you inserting individual elements? Then it depends on how you extract: all elements, once, after you're done inserting? Just use push_back and std::sort when you are done. Or are you extracting a lot? Then keep the array sorted by using std::vector::insert and std::lower_bound.