@Vatine: Я считаю, что Йохан хотел сказать, что стоимость динамического выделения массива зависит только от размера выделенных вами фрагментов. Поэтому, если вы хотите, чтобы он всегда был компактным, вам придется часто выделять ресурсы (копируя все данные каждый раз). Если вы выделяете более крупные куски, вам нужно будет сделать это только один или два раза, это не имеет большого значения (но, с другой стороны, это означает, что вы теряете пространство).
нам нужны деревья в алгоритмах, и я получаю дерево с большим количеством указателей и рекурсией.
Иногда мне нужно больше скорости, и я помещаю дерево в 2D-массив следующим образом:
Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11 dddddddd| //sibbling is x dimension of the array.
|2222 cccc| //The 123 tree is stored root up.
|33333333 bb| //Notice how the abc-tree is stored upside down
|4444444444444444a| //The wasted space in the middle, is offset by the fact
+-----------------+ //that you do not need up, down, and sibbling pointers.
Мне нравится эта структура, потому что она позволяет мне ускорить варианты, которых у меня нет при использовании указателей и рекурсии.
Но обратите внимание, что впустую пространство в середине ....
Как мне избавиться от / использовать повторно потраченное место?
Требования
Я использую эту структуру, только если мне нужен каждый последний бит скорости, поэтому решение с большим количеством переводов и вычислений адресов, чтобы добраться до этого места, не будет полезным.