Контейнер с двумя индексами (или составной индекс)

Question

У меня есть такой класс

class MyClass 
{
    int Identifier;
    int Context;
    int Data;
}

и я планирую хранить его в контейнере STL, например

vector<MyClass> myVector;

но мне нужно будет получить к нему доступ либо по внешнему индексу (используя myVector[index]); и сочетание Identifier и Context, которое в этом случае я бы выполнил поиск с чем-то вроде

vector<MyClass>::iterator myIt;
for( myIt = myVector.begin(); myIt != myVector.end(); myIt++ )
{
    if( ( myIt->Idenfifier == target_id ) &&
        ( myIt->Context == target_context ) )
        return *myIt; //or do something else...
}

Есть ли лучший способ хранить или индексировать данные?

Answer 1

Boost :: Multi-Index обладает именно такой функциональностью, если вы можете позволить себе зависимость наддува (только заголовок). Вы бы использовали индекс random_access для индекса, подобного массиву, и либо hashed_unique, hashed_non_unique, ordered_unique или ordered_non_unique (в зависимости от ваших желаемых характеристик) с функтором, который сравнивает Идентификатор и Контекст вместе.

Answer 2

Нам нужно знать ваше использование. Почему вам нужно иметь возможность получить их по индексу, и как часто вам нужно искать контейнер для определенного элемента.

Если вы сохраните его в std::set, ваше время поиска будет равно O (ln n), но вы не можете ссылаться на них по индексу.

Если вы используете std::vector, вы можете индексировать их, но вы должны использовать std::find, чтобы получить определенный элемент, который будет O (n).

Но если вам нужен индекс для передачи его другим вещам, вы можете использовать указатель. То есть используйте набор для более быстрого поиска и передавайте указатели (не индексы) на конкретные элементы.

Answer 3

Да, но если вам нужна скорость, вам нужно пожертвовать пространством. Сохраните его в коллекции (например, в наборе STL) с идентификатором / контекстом в качестве ключа и одновременно сохраните его в векторе. Конечно, вам не нужны две копии самих данных, поэтому сохраняйте их в наборе, используя умный указатель (auto_ptr или вариант), и сохраняйте их в векторе, используя тупой указатель.