Каковы преимущества карты карт против std :: pair в качестве ключа

Каковы преимущества и недостатки следующих способов создания карты, предназначенной для представления двумерной сетки. Сетка должна быть заполнена в любой точке, без выделения памяти для всего, поэтому я не просто использовал 2d-массив.Каковы преимущества карты карт против std :: pair в качестве ключа

std::map<int, std::map<int, Tile*>* >* tiles; 

std::map<std::pair<int, int>, Tile*>* tiles;

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

источник

2013-02-11 rekh127

Это (очевидно) другая структура данных и зависит от того, как вы к ней обращаетесь.

Первый из них больше похож на двухуровневую древовидную структуру. Переместите x-координаты на несколько y-координат на несколько фрагментов. Это может показаться немного неуместным для вашей проблемы.

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

Если вам нужно сопоставить (x, y) координаты с плиткой, то второй подход может быть в порядке.

источник

2013-02-11 17:38:14 sstn

Поскольку ключи в 'std :: map' упорядочены, вы можете, конечно, перебрать все элементы с определенной координатой x. Начните с первого ключа, по крайней мере, такого же размера, как make_pair (x, INT_MIN), и продолжайте с последующими клавишами, пока вы не достигнете конца или не найдете тот, чья координата x отличается. То, что вы не можете сделать ни с какой-либо структурой данных, легко проходит через элементы с определенной координатой y. – rici

Значит, проблема с памятью или скоростью не решена? В настоящее время я обращаюсь к нему по мере того, как получаю карту, координата x которой меня направляет, а затем получает фрагмент, координата y которого меня направляет с этой карты. Я думал об этом, так как основная карта - это карта столбцов, столбцов и карт плиток. – rekh127

Почему бы не использовать вектор вектора, std :: vector < std :: vector>?

Было бы лучше, если ваша сетка не разрежена (не каждый элемент сетки имеет плитки), и вы хотите сохранить память. Время доступа с использованием вектора было бы намного лучше, если бы скорость была проблемой, поскольку std :: map использует tress в качестве базовой структуры.

источник

2013-02-11 17:58:31 umps

* «Время доступа с использованием вектора было бы намного лучше» * - Если не существует много элементов, которые вы должны регулярно перемещать, и вы используете вектор векторов, который убивает вашу локальность данных. –

Вы правы, это зависит от шаблона доступа и размера данных. – umps

Извините, я не знал, как это описать хорошо, но моя сетка разрежена, она предназначена для того, чтобы на ней могли быть пятна, которые генерируются с пустой областью между ними, и что эти пустые области заполняются по мере необходимости. Таким образом, в сетке из тысяч возможных Плиток вначале может присутствовать только несколько десятков из них, но мне нужно сохранить x, y для позиции. – rekh127

Каковы преимущества карты карт против std :: pair в качестве ключа

ответ

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