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.