Добавление, освобождение памяти

 
0
 
C++
ava
Амортизатор | 18.02.2006, 22:31
 Суть вот чем. Надо без всякого STL реализовать добавление, удаление элементов. Добавление будет идти в конец последовательности, удаление - из начала. STL как я понял не катит, поскольку vector будет тормозить, переписывая при каждом удалении из начала весь массив, а список не годится - надо бегать по последоваетльности часто и быстро.

Я хочу реализовать это дело функциями malloc и remalloc. Выделять malloc'ом типа
int prt=malloc(N*sizeof(myclass*)) память, и при удалении элемента с начала realloc(ptr+sizeof(myclass*), (N-1)*sizeof(myclass*)), при добавлении аналогично добавлять.

Вопрос - разумно ли это, и насколько быстра функция malloc?
Добавлено позднее:
Все это буде происходить на WM_TIMER, поэтому быстрота исключительно важна. 
Ответы (7)
ava
LPBOY | 18.02.2006, 23:13 #
 
Цитата (Амортизатор @  18.2.2006,  22:31 findReferencedText)
Добавление будет идти в конец последовательности, удаление - из начала. STL как я понял не катит, поскольку vector будет тормозить, переписывая при каждом удалении из начала весь массив, а список не годится - надо бегать по последоваетльности часто и быстро.


Здесь подойдет std::deque, или еще лучше std::queue. 
ava
Амортизатор | 18.02.2006, 23:48 #
 Нельзя дать краткое описание этих классов? msdn сейчас нету под рукой. 
ava
DeadSoul | 18.02.2006, 23:49 #
 msdn.microsoft.com 
ava
Амортизатор | 18.02.2006, 23:53 #
 Да только что там был.

Цитата


The Standard Template Library (STL) sequence container deque arranges elements of a given type in a linear arrangement and, like vectors, allow fast random access to any element and efficient insertion and deletion at the back of the container. However, unlike a vector, the deque class also supports efficient insertion and deletion at the front of the container.



Подтвердите, пожалуйста, что добавление вперед массива будет происходжить столь же быстро, что и в конец, и что скорость не зависит от размера вектора, и в частности не будет при каждой вставке перекопирования элементов. 
ava
LPBOY | 19.02.2006, 00:03 #
 
Цитата (Амортизатор @  18.2.2006,  23:53 findReferencedText)
Подтвердите, пожалуйста, что добавление вперед массива будет происходжить столь же быстро, что и в конец, и что скорость не зависит от размера вектора, и в частности не будет при каждой вставке перекопирования элементов. 


Да, в этом и смысл двусторонней очереди (deque). - Вставка/удаление элемента в начало/конец происходит быстро (за константное время) без перемещения элементов. А queue это более специализированный адаптер, добавление(push) элементов происходит в конец, а удаление(pop) из начала. По умолчанию queue реализуется на основе дека (std::deque), поэтому операции push/pop происходят также быстро. 
ava
Амортизатор | 19.02.2006, 10:19 #
 Спасибо, это информация мне очень помогла. 
ava
Earnest | 21.02.2006, 20:39 #
 
Цитата (Амортизатор @  18.2.2006,  22:31 findReferencedText)
Все это буде происходить на WM_TIMER, поэтому быстрота исключительно важна. 

 smile 
Т.е. не чаще чем раз в 10 mc...
Уверяю тебя по сравнению с вызовами WinAPI, в тем паче GDI - все выделения-развыделения памяти полная ерунда... разве что каждый твой элемент по пол-мегабайта весит...
Это я к чему: не ищи проблем там где их нет.  smile 

Однако совет LPBOY насчет использования деки или очереди совершенно разумный.
  
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить