C++:由整数键入的对象的映射或向量？

Question

我将存储一些由各种数字键入的对象.大多数数字没有对象,有些会有1个,有些会有多个.

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

std::vector<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?
    }
}

我应该使用地图或矢量,我应该如何实现该功能？

Answer 1

您正在寻找的可能是多图,请参阅http://www.cplusplus.com/reference/stl/multimap/.

但是你应该指出你的目标是什么 - 记忆效率,表现？此外,如何在键上"分配"值？如果这是一个重要的决定,你应该做原型.

PS:不要写

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

反而

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

GCC将解释>>作为运营商>>否则.

Answer 2

这实际上取决于您将使用的整数类型.

如果您可能有一个负整数作为键,那么map就是要走的路,因为vector它不支持负指数.在相关的说明中,如果您不会使用负键,请考虑使用键入元素unsigned int而不是int更清楚地表明键可以是负数.

如果你有大量的小整数作为键,这vector可能是一个不错的选择.基于内存vector的方法的内存使用量将具有内存使用量O(U + n),其中U是最大的密钥,因为vector需要具有连续的存储.如果U很小,那么vector基于-Based的方法可能会更好.如果U是巨大的,那就去吧map.

但我认为最好的解决方案是使用新的C++ 0x unordered_map,它提供接近于vector(每个元素的常量时间查找)的复杂性保证,其内存保证接近于map(您只需支付元素费用) '正在使用).这可以使用Boost的容器实现,或者使用TR1实现,或者(如果你有一个C++ 0x编译器)使用新的标准库来完成.