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

Question

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

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

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

Answer 1

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

Concise Sparse Matrix Package in C

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

Answer 2

Вы ищете sparse matrix?

Answer 3

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

Answer 4

 

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/

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