Как лучше организовать динамический двухмерный массив. Необходим для хранения ячеек таблицы, при этом должны добавляться как строки, так и колонки с приемлемой скоростью. Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации???
Здравствуйте, Аноним, Вы писали:
А>Как лучше организовать динамический двухмерный массив. Необходим для хранения ячеек таблицы, при этом должны добавляться как строки, так и колонки с приемлемой скоростью. Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации???
Почему неверный? ИМХО, нормально.
Можно еще vector<TCell> и преобразовывать индексы вроде i * n + k.
С уважением, Александр
Re[2]: dynamic 2D array
От:
Аноним
Дата:
20.09.07 06:24
Оценка:
Здравствуйте, Smal, Вы писали:
А>>Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации??? S>Почему неверный? ИМХО, нормально.
Копирование у vector<TCell> явно недешовое
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Smal, Вы писали:
А>>>Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации??? S>>Почему неверный? ИМХО, нормально. А>Копирование у vector<TCell> явно недешовое
А можно дешевле? К тому же, не хочешь — не копируй.
Если нужно просто передать владение используй auto_ptr< vector<TCell> >.
Здравствуйте, Аноним, Вы писали:
А>Как лучше организовать динамический двухмерный массив. Необходим для хранения ячеек таблицы, при этом должны добавляться как строки, так и колонки с приемлемой скоростью. Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации???
Здравствуйте, Аноним, Вы писали:
А>Как лучше организовать динамический двухмерный массив. Необходим для хранения ячеек таблицы, при этом должны добавляться как строки, так и колонки с приемлемой скоростью. Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации???
Добавление строк — операция дешевая, а вот столбцов — нет. Как ни крути, а придется существующие строки перелить в другие большего размера, а прежние удалить. Фактически это пересоздание матрицы целиком.
Если не рассматривать этот вопрос как академический, а перейти к практической реализации в Windows, и если известен максимальный размер строки (пусть даже этот максимальный на порядки больше реального), то я бы посоветовал копать в сторону VirtualAlloc. Там есть возможность резервировать адресное пространство и коммитировать память, и это разные вещи. Резервировать можно хоть 10 Мб, хоть 100 Мб — это очень дешево и не выделяет память. А потом можно коммитировать этот зарезервировааный диапазон адресов понемногу, по мере надобности.
Схема такая
Резервируешь под каждую строку с помощью VirtualAlloc, скажем, 128 Кб. Если элементы матрицы имеют размер 4 байта, то максимум у тебя может быть 32 тысячи столбцов. Если надо что-то иное, подредактируй это значение. И так на то количество строк, которое тебе в начале надо (например, 1024).
Теперь коммитируем в каждой строке, скажем, 4 Кб. Это даст тебе 1024 столбца.
Итак, имеем матрицу 1024 на 1024, вполне готовую к употреблению. Зарезервировано 128 Кб * 1024 == 128 Мб (не так уж и много, всего есть примерно 2 Гб адресного пространства). Коммитировано (реально выделено) 4 Кб * 1024 = 4 Мб ну и плюс массив указателей на эти строки (это копейки). Кстати, под него память можно выделять тем же способом, чтобы и его никогда не копировать, а только докоммитировать.
Если понадобится 1025 строка, просто делаем то же самое для нее.
А вот если понадобится 1025 столбец, проходим по всем 1024 строкам и коммитируем еще по 4 Кб (меньше нельзя, память выделяется страницами). Теперь у нас есть матрица 1024*2048.
Ну и т.д.
Если размер уменьшается, то можно и декоммитировать как куски строк (при уменьшении числа столбцов), так и строки (при уменьшении их числа).
Здравствуйте, Аноним, Вы писали:
А>Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации???
class Mt2DArray {
public:
T& operator() ( int line, int column ) { return (*lines[line])[columns[column]]; }
privarte:
std::vector< std::vector<T>* > lines;
std::vector<int> columns;
}
Остальное сам исправишь и допишешь, если идея подходит
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: dynamic 2D array
От:
Аноним
Дата:
20.09.07 10:09
Оценка:
Здравствуйте, Pavel Dvorkin
Такую идею я рассматривал (по поводу VirtualAlloc). Немогли бы вы пояснить более подробно моменты добавления/удаления столбцов и строк. Ячейка примерно около 50 байт. Все это мне необходимо для контрола grid.
Здравствуйте, Аноним, Вы писали:
А>Как лучше организовать динамический двухмерный массив. Необходим для хранения ячеек таблицы, при этом должны добавляться как строки, так и колонки с приемлемой скоростью. Думал о vector<vector<TCell>>, но вроде как это неверный путь 8) Может есть какие другие реализации???
Если матрица (таблица) чаще всего будет разряженной, то рассмотри представление разряженной матрицы — подробности в Кнуте.
Здравствуйте, <Аноним>, Вы писали:
А>Как лучше организовать динамический двухмерный массив. Необходим для хранения ячеек таблицы, при этом должны добавляться как строки, так и колонки с приемлемой скоростью.
Один из подходов: ptr_vector< ptr_vector< TCell > >
где ptr_vector — вектор указателей, каждый элемент которого размещён отдельно.
Можно порыться в бусте, а можно и из обычного std::vector с долей рукоделия.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Pavel Dvorkin
А>Такую идею я рассматривал (по поводу VirtualAlloc). Немогли бы вы пояснить более подробно моменты добавления/удаления столбцов и строк. Ячейка примерно около 50 байт. Все это мне необходимо для контрола grid.
Да вроде я всю идею описал.
Ячейку лучше сделать размера 2^N, в твоем случае 64. Тогда на 4 Кб (страница) поместится 64 столбца. Если максимальне число столбцов N, то резервировать надо N*64, округлив до 64К.
Коммитировать в начале нужно столько, сколько требуется. К примеру, если нужно 128 столбцов, то коммитируем , начиная с адреса, который вернула Virtualalloc (pBase) при резервировании, размер 8К. Если потом понадобится увеличить число столбцов до 192, коммитируем с адреса pBase+8K еще 4K И т.д.
Каждая строка лежит отдельным куском, поэтому такое делается для каждой строки по отдельности. pBase — это фактически массив указателей на эти куски, т.е pBase[i] — указатель на i строку матрицы. Поэтому добавление строки просто сводится к использованию pBase с большими номерами тем же способом. Сам массив pBase можно просто описать на максимальное число строк, память при этом захватывается небольшая
PD>Выглядит , конечно, красиво, но это двойная индексация. Фактически это уже не массив, p++ тут не будет. И скорость упадет.
А что это за фигня p++ применительно к двумерным массивам?
Итерирование по строке? По столбцу? Адресная арифметика просто так из любви к искусству? В топку её.
Перекуём баги на фичи!
