Каков наилучший способ использования двух ключей с std:: map?

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

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

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

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

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

Ответ 1

Используйте ключ std:: pair < int32, int32 > для ключа:

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;

Ответ 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;
    }
}

Ответ 3

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

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

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

Ответ 4

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

Multi Index Map

Ответ 5

Это будет содержать несколько целых ключей в большое целое число, в данном случае - _int64. Он сравнивается как _int64, AKA long long (самая уродливая декларация типа когда-либо короткая короткая короткая короткая, была бы чуть менее элегантной. 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 такт.

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

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

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

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

Ответ 6

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

Ответ 7

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

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

Это делает для некоторых уродливых суб-скриптов, так что небольшая макромагия сделает вашу жизнь проще. Я оставил эту общую цель, но тип-литье аргументов в макросе - хорошая идея, если вы создаете макросы для определенных карт. 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... err.. DosKeys куча раз, это жажда мексиканского пива. Пусть покупатель будет бдителен. Как говорит Шелдон Купер: "Какая жизнь без прихотей?".

Ответ 8

Надеюсь, вам понравится:

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