Как лучше всего использовать два ключа с помощью std :: map?

Question

У меня есть std :: map, который я использую для хранения значений для координат x & y. Мои данные очень скудны, поэтому я не хочу использовать массивы или векторы, которые могут привести к огромным потерям памяти. Мои данные колеблются от -250000 до 250000, но у меня будет максимум несколько тысяч очков.

В настоящее время я создаю std :: string с двумя координатами (т.е. "12x45") и использую ее в качестве ключа. Это не лучший способ сделать это.

Другие мои мысли заключались в том, чтобы использовать int64, вставить два int32 и использовать его в качестве ключа.

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

Каков наилучший способ сделать это? Я бы предпочел не использовать карту карт.

Answer 1

Используйте ключ std :: pair :

std::map<std::pair<int,int>, int> myMap;

myMap[std::make_pair(10,20)] = 25;
std::cout << myMap[std::make_pair(10,20)] << std::endl;

Answer 2

Я обычно решаю такую ​​проблему следующим образом:

struct Point {
    int x;
    int y;
};

inline bool operator<(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}

Answer 3

Каковы требования к классу, который будет использоваться в качестве ключа?

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

Шаблон карты также реализует перегруженный конструктор, который позволяет передавать ссылку на функциональный объект типа key_compare, который может реализовывать оператор сравнения: так, что альтернативно сравнение может быть реализовано как метод этого внешнего функционального объекта вместо того, чтобы запекаться до любого типа, к которому относится твой ключ.

Answer 4

Boost имеет контейнер карты, который использует один или несколько индексов.

Многоиндексная карта

Answer 5

Это поместит несколько целочисленных ключей в большое целое число, в данном случае _int64. Он сравнивается как _int64, AKA long long (самое уродливое объявление типа. Short short short short, было бы чуть менее элегантно. 10 лет назад его называли vlong. Намного лучше. Так много для «прогресса»), так что никакого сравнения функция нужна.

#define ULNG  unsigned long
#define BYTE  unsigned char
#define LLNG  long long 
#define ULLNG unsigned long long

// --------------------------------------------------------------------------
ULLNG PackGUID(ULNG SN,  ULNG PID, BYTE NodeId) {
    ULLNG CompKey=0;

    PID = (PID << 8) + NodeId;
    CompKey = ((ULLNG)CallSN << 32) + PID;

    return CompKey;
}

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

С другой стороны, если у вас уже есть координата XY и вы просто хотите связать значение с этим ключом, то это работает потрясающе, потому что сравнение _int64 занимает то же время, что и любое другое целочисленное сравнение на чипах Intel X86 - 1 час

В этом случае сравнение по этому синтетическому ключу происходит в 3 раза быстрее по сравнению с тройным составным ключом.

Если использовать это для создания малонаселенной электронной таблицы, я бы использовал RX, используя два разных дерева, одно вложенное в другое. Сделайте измерение Y "боссом", и ищите пространство Y сначала до разрешения, прежде чем перейти к измерению X. Таблицы выше, чем они широки, и вы всегда хотите, чтобы 1-е измерение в любом составном ключе имело наибольшее количество уникальных значений.

При таком расположении будет создана карта для измерения Y, которая будет иметь карту для измерения X в качестве данных. Когда вы попадаете на лист в измерении Y, вы начинаете искать его измерение X для столбца в электронной таблице.

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

Answer 6

Надеюсь, вы найдете это полезным:

map<int, map<int, int>> troyka = { {4, {{5,6}} } };
troyka[4][5] = 7;

Answer 7

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

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

Это создает некрасивые подпрограммы, поэтому немного магии макросов сделает вашу жизнь проще. Я оставил это одно общее назначение, но приведение типов в макросе - хорошая идея, если вы создаете макросы для конкретных карт. TresKey12 протестирован и работает нормально. QuadKeys также должно работать.

ПРИМЕЧАНИЕ. Пока ваши ключевые части являются базовыми типами данных, вам не нужно больше ничего писать. AKA, не нужно беспокоиться о функциях сравнения. STL покрыл тебя. Просто закодируйте его и дайте ему разорваться.

using namespace std;    // save some typing
#define DosKeys(x,y)      std::make_pair(std::make_pair(x,y))
#define TresKeys12(x,y,z) std::make_pair(x,std::make_pair(y,z))
#define TresKeys21(x,y,z) std::make_pair(std::make_pair(x,y),z))

#define QuadKeys(w,x,y,z) std::make_pair(std::make_pair(w,x),std::make_pair(y,z))


map<pair<INT, pair<ULLNG, ULLNG>>, pIC_MESSAGE> MapMe;
MapMe[TresKey12(Part1, Part2, Part3)] = new fooObject;

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

PS: TresKey12 дал мне проблемы с картой, объявленной как пара, z, так как она делает x, пара, и эти два не играют хорошо. Не проблема для DosKeys или QuadKeys. Если жаркая летняя пятница, вы можете обнаружить неожиданный побочный эффект при наборе текста в DosEquis. ... эээ ... DosKeys пару раз, жажда мексиканского пива. Пусть покупатель будет бдителен. Как говорит Шелдон Купер: «Какая жизнь без прихотей?».

Answer 8

Использовать std :: pair. Лучше даже использовать QHash<QPair<int,int>,int>, если у вас много таких отображений.