C++: map or vector for objects keyed by integers?

I am going to store some objects keyed by various numbers. Most numbers will have no objects, some will have 1, and some will have multiple.

std::map<int, std::vector<MyObject>> myObjects;
// or...
std::vector<std::vector<MyObject>> myObjects;

std::vec开发者_开发技巧tor<MyObject> GetObjectsForNumber( int number )
{
    // how best to do this?

    if ( -check if there is a vector for the number- )
    {
        return myObjects[number];
        // or...
        return myObjects.at(number);
    }
    else
    {
        // return empty vector?
    }
}

Should I use a map or vector, and how should I implement the function?

---

What you are looking for is probably the multimap, see http://www.cplusplus.com/reference/stl/multimap/.

But you should point out what exactly your goals are - memory efficiency, performance? Also, how is the "distribution" of the values over the keys? If it's an important decision, you should prototype.

P.S.: Don't write

std::vector<std::vector<MyObject>> myObjects;

but rather

std::vector<std::vector<MyObject> > myObjects;  //note the space between the > >

GCC will interpret >> as operator>> otherwise.

---

This really depends on the types of integers you'll be using.

If you might ever have a negative integer as a key, the map is the way to go, since vector doesn't support negative indices. On a related note, if you aren't going to ever have negative keys, consider keying the elements using unsigned int instead of int to make it clearer that the keys can be negative.

If you will have a large number of small integers as keys, the vector may be a good option. The memory usage for your vector-based approach will have memory usage O(U + n), where U is the largest key, since the vector needs to have contiguous storage. If U is small, then the vector-based approach might be better. If U is huge, go with the map.

But I think the best solution would be to use the new C++0x unordered_map, which gives complexity guarantees close to that of the vector (constant-time lookup of each element) with memory guarantees close to that of the map (you only pay for elements you're using). This could be done using either Boost's implementation of the containers, or with a TR1 implementation, or (if you have a C++0x compiler) using the new standard libraries.

---

Really sounds like a candidate for a hash map with chaining, or a double hash.

---

Here is an important question: Will the numbers you use as keys are uniformly distributed (e.g. 1, 6, 2, 7, 4), then using the numbers directly as indices in a vector will be very efficient (O(1) lookup). If they are not uniformly distributed (e.g. 0, 1, 10000, 100000), then you're going to store a lot of empty cells and use a lot of memory.

In the second case, using map would be much better. Also, hash_map behaves almost identically to map, but it may be faster in this case because the computer can look at integers (your keys) all at once rather than simply arrange them by saying "Is this key bigger or smaller than that key?" (this is how a map works)