C++: Быстрая структура с двумя связанными ключами

У меня есть ситуация, когда у меня есть контейнер, который должен содержать идентификатор (уникальные идентификаторы) и значение данных. Мне также нужно сохранить эти идентификаторы в порядке. Кортеж этих переменных будет проверяться идентификатором, но затем обрабатывается до найденного элемента, то есть я не всегда хочу обрабатывать весь контейнер. Для этого у меня есть простое решениеC++: Быстрая структура с двумя связанными ключами

// ordinal, { ID, data } 
std::map<int64, pair<int64, data_t> >

Какой я первый поиска ID перебирая и сравнивая значение поиска с первым полем пары, давая мне итератор ходить до, то я обработаю все элементы до этой позиции. Есть ли лучший способ сделать это (по моему счету это O (2n))?

источник

2016-12-06 Madden

вы можете использовать зЬй :: Карта вместо станд :: пары который затем дает вам быстрый поиск, но будет тратить память. –

Оба лимита 'int64' показывают здесь идентификатор? Поиск в «карте» равен O (log n), а не O (n). –

Первый ординал, второй (в паре) - это идентификатор. В рамках этой схемы я не занимаюсь поиском, просто повторяя ее дважды. Мне передают идентификатор, из этого мне нужно найти порядковый номер процесса в порядке до и включая этот порядковый номер – Madden

Вы можете использовать Boost.Bimap, если хотите индексировать значения, а также ключи. Таким образом, вы можете найти пару на карте на основе ее ценности. Без этого или подобного, это должно быть сделано грубой силой (=> итерацией по карте вручную).

В противном случае вы можете использовать std::find_if, чтобы помочь вам найти пару с ID, который вы ищете, но это будет такая же скорость, что и итерация по карте.

источник

2016-12-06 14:38:52

Вы можете поменять ordinal и ID и хранить их в карте карты:

//     ID    ordinal data 
std::unordered_map<int64, std::map<int64, data_t>> container;

Это позволит вам найти элемент с ID дается и минимально возможным ordinal в O(log N) время:

container[ID].begin(); // Has ID given, smallest possible ordinal and corresponding data 
         // Equal to container[ID].end() if not found

После этого вы можете сравнить ordinal объекта, найденного с заданным пороговым значением.

UP: Конечно, если ваши ID s уникальны, нет никакой необходимости в гнездовой map: вы можете просто использовать std::unordered_map<int64, std::pair<int64, data_t>>.

источник

2016-12-06 14:48:31 alexeykuzmin0

Если порядковое строго для поддержания порядка и не будет каких-либо пробелов, я бы сделать что-то простое, как это:

int64_t givenID = whereToQuit; 

    std::vector<int64_t>    ordinal_to_ID; 
    std::unordered_map< int64_t, data_t > data_map; 

    using datapair_t = std::pair< int64_t, data_t >; 
    void do_whatever(datapair_t); 

    bool done = false; 
    do 
    { 
     int64_t ID = ordinal_to_ID[ i ]; 
     do_whatever(datapair_t(ID, data_map[ ID ])); 
     done = ID == givenID; 
    } 
    while (!done);

источник

2016-12-06 15:22:38

C++: Быстрая структура с двумя связанными ключами

ответ

Смежные вопросы