Хранение и получение нескольких ключей в C ++

Question

У меня есть несколько целочисленных ключей, необходимых для получения значения.Каков наиболее эффективный способ хранения и извлечения значения на основе ключей?

В настоящее время я преобразовываю и объединяю три ключа в одну строку и сохраняю пару ключ-значение на карте.Однако я думаю, что должен быть более эффективный способ сделать это на основе одного целочисленного значения, например, сгенерировать один ключ на основе трех ключей.Есть идеи на этот счет?

Спасибо.

Answer 1

Вы почти наверняка можете добиться большего успеха, чем преобразование в строку (что, как правило, довольно медленная операция). Если ваши три элемента имеют достаточно малые диапазоны, вы можете сделать некоторые сдвиги и сложения, чтобы соединить их в одно целое число с большим диапазоном.

Не имея этого, вы можете просто создать структуру, которая содержит три целых числа и определяет operator< для их разумного сравнения:

class key { 
    int a, b, c;
public:
    bool operator<(key const &other) { 
        if (a < other.a)
            return true;
        if (a > other.a)
            return false;
        if (b < other.b)
            return true;
        if (b > other.b)
            return false;
        if (c < other.c)
            return true;
        return false;
    }
};

Edit: для тех, кому это нужно, использование (std | tr1 | boost) :: tuple не сильно изменит характер ответа, но устранит большую часть кода. Кортеж очень похож на std::pair, за исключением того, что он поддерживает произвольное количество элементов вместо двух. В приведенном выше примере вы можете использовать что-то вроде:

#include <tuple>

namespace stdx = std::tr1;    // or stdx=boost::tr1, etc.

typedef stdx::tuple<int, int, int> key_t;

std::map<key_t, whatever> my_map;

tuple определяет операторы сравнения автоматически, предполагая, что типы сравнимы (т. Е. Для сравнения двух кортежей с одинаковым количеством элементов, а типы соответствующих элементов сравнимы). В этом случае выполняется лексикографическое сравнение (т. Е. Результат сравнения - результат первой пары соответствующих элементов, которые не равны - ни один такой элемент не существует, два сравнения равны).

Answer 2

Джерри Коффин * Предложение 1002 * - хорошее предложение, которое можно расширить на любое количество ключей произвольной ширины.

Однако на практике существует много ситуаций, в которых может быть использован следующий эффективный метод. Если размер ключей таков, что их сумма вписывается в нативный тип, мы можем составить ключ следующим образом.

Предположим, у нас есть три ключевые части:

a, 16-bit,
b, 32-bit
c, 16-bit

перечислены в порядке значимости для сравнения. (То же, что в примере Джерри Коффин .)

Тогда мы можем иметь одно значение

class key {
  private:
    uint64_t key_rep_;  // internal key representation
};

со следующей базовой интерпретацией key_rep_

AAAABBBBBBBBCCCC

Каждая буква выше является клочком и показывает ключевую часть, которую она представляет.

Сравнение этого подхода с простым:

• чтение и запись части ключа в ключ выполняются медленнее
• сравнение двух клавиш быстрее

На карте или в наборе сравнение ключей происходит гораздо чаще, чем чтение / запись, поэтому этот подход, когда это применимо, обеспечивает общую эффективность.

Answer 3

То, что вы делаете, звучит нормально.Альтернативой, к которой вы, возможно, чувствуете свой путь, будет использование хеш-кода, сгенерированного из ваших трех целочисленных подразделов, для доступа к значениям через что-то вроде unordered_map .

Если std::map работает для вас, и вам не нужно время поиска O (1), переход к контейнеру на основе хеш-функции может создать сложность при генерации хеш-кода (что нелегко сделать хорошо), чтодоставляет больше хлопот, чем стоит.

Answer 4

вы можете отобразить вектор с ключами к значению с картой и использовать лексикографический порядок для карты.Если количество ключей постоянное, вы можете даже сопоставить массивы int с тем же порядком