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

Это на самом деле зависит от типов целых чисел, которые вы будете использовать.

Если в качестве ключа у вас может быть отрицательное целое число, то map - это путь, так как vector не делаетНе поддерживаю отрицательные показатели.На заметку о том, что если у вас никогда не будет отрицательных ключей, рассмотрите возможность ввода элементов с использованием unsigned int вместо int, чтобы было яснее, что ключи могут быть отрицательными.

Если вы будетеиметь большое количество маленьких целых чисел в качестве ключей, vector может быть хорошим вариантом.Использование памяти для вашего подхода на основе vector будет иметь использование памяти O (U + n), где U - самый большой ключ, так как vector должен иметь непрерывное хранилище.Если U мало, то подход на основе vector может быть лучше.Если U огромен, используйте map.

Но я думаю, что лучшим решением было бы использование нового C ++ 0x unordered_map, который дает гарантии сложности, близкие к таковым для vector (поиск каждого элемента в постоянном времени) с гарантией памяти, близкой к памяти map (вы платите только за элементы, которые используете).Это можно сделать с помощью реализации контейнеров в Boost или с помощью реализации TR1, или (если у вас есть компилятор C ++ 0x) с использованием новых стандартных библиотек.

Answer 2

То, что вы ищете, это, вероятно, мультикарта, см. 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 3

Действительно звучит как кандидат на хэш-карту с цепочкой или двойной хэш.

Answer 4

Вот важный вопрос: будут ли числа, которые вы используете в качестве ключей, распределены равномерно (например, 1, 6, 2, 7, 4), тогда использование чисел непосредственно в качестве индексов в векторе будет очень эффективным (O (1) уважать).Если они распределены неравномерно (например, 0, 1, 10000, 100000), то вы собираетесь хранить много пустых ячеек и использовать много памяти.

Во втором случае использование map приведет кбыть намного лучшеКроме того, hash_map ведет себя почти так же, как и map, но в этом случае он может работать быстрее, потому что компьютер может одновременно рассматривать целые числа (ваши ключи), а не просто упорядочивать их, спрашивая: «Этот ключ больше или меньше этого ключа?»(так работает карта)