Какую структуру данных использовать?

Question

Мне нужна структура данных со следующими свойствами:

• Доступ к элементам должен быть очень быстрым
• Элементы, которые не добавлены, не должны занимать память (как идеальный, размер пустой структуры близок к нулю)
• Каждый элемент имеет две целочисленные координаты (x, y) (доступ к элементам только по ним)
• Максимальное количество элементов, известных во время создания (более 10 ^ 3)
• Элемент содержит несколько значений с плавающей запятой

Было бы хорошо, если бы вы также обратились к реализации этой структуры на C или C ++.

Answer 1

Вы ищете разреженную матрицу ?

Answer 2

Проверьте это - вы можете изменить тип элемента на float, если это будет делать все, что вы хотите.

Краткий пакет с разреженной матрицей в C

Для C ++Вы можете использовать Boost.uBLAS - sparse_matrix details здесь .

Answer 3

typdef ElementAccessor std::pair<int, int>;

struct Element
{
  float f1;
  float f2;
  //etc.

};

std::map< ElementAccessor, Element > myElementMap;

Теперь вы можете использовать эту карту в качестве матрицы. ElementAccessor ссылается на x, y. Просто убедитесь, что элемент существует на карте, прежде чем пытаться получить к нему доступ, или он создан по умолчанию.

http://www.cplusplus.com/reference/std/utility/pair/ http://www.cplusplus.com/reference/stl/map/find/

edit: скобки шаблона отображаются на карте. тип ключа карты - ElementAccessor, значение - Element. Кроме того, для пары шаблон является int, int.

Answer 4

Если ваши X и Y относительно малы, то будет работать двумерный массив указателей. 10000 указателей будут 40K в 32-битном коде.