Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента:
1) память не освобождается
2) остальные элементы никуда не сдвигаются
Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
Здравствуйте, Аноним, Вы писали:
А>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>1) память не освобождается А>2) остальные элементы никуда не сдвигаются
А>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
А>Спасибо.
Re[2]: stl-контейнер для push_back() / pop_front()
От:
Аноним
Дата:
20.12.07 16:43
Оценка:
Здравствуйте, remark, Вы писали:
R>Здравствуйте, Аноним, Вы писали:
А>>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>>1) память не освобождается А>>2) остальные элементы никуда не сдвигаются
А>>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
А>>Спасибо.
R>std::deque
А почему тогда
Deque reallocation occurs when a member function must insert or erase elements of the controlled sequence. In all such cases, iterators or references that point anywhere within the controlled sequence become invalid
Здравствуйте, Аноним, Вы писали:
А>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>1) память не освобождается
Какая память?
А>2) остальные элементы никуда не сдвигаются
Любой ассоциативный контейнер. У дека итераторы и указатели остаются валидными при выполнении push_back.
А>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
list, deque.
Любите книгу — источник знаний (с) М.Горький
Re[3]: stl-контейнер для push_back() / pop_front()
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, Аноним, Вы писали:
А>>>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>>>1) память не освобождается А>>>2) остальные элементы никуда не сдвигаются
А>>>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
А>>>Спасибо.
R>>std::deque
А>А почему тогда А>
А>Deque reallocation occurs when a member function must insert or erase elements of the controlled sequence. In all such cases, iterators or references that point anywhere within the controlled sequence become invalid
Если нужны такие строгие требования к работе с памятью, придётся самому писать. Хотя вряд ли велоспипед будет лучше чем std::deque.
Здравствуйте, Аноним, Вы писали:
А>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>1) память не освобождается А>2) остальные элементы никуда не сдвигаются
А>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
А>Спасибо.
Чтобы память под ноды не освобождалась, можно использовать boost::pool аллокатор для стандартных контейнеров.
Re[2]: stl-контейнер для push_back() / pop_front()
Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>Чтобы память под ноды не освобождалась, можно использовать boost::pool аллокатор для стандартных контейнеров.
А всё равно локальность будет плохая...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: stl-контейнер для push_back() / pop_front()
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>>Чтобы память под ноды не освобождалась, можно использовать boost::pool аллокатор для стандартных контейнеров. E>А всё равно локальность будет плохая...
Имеете ввиду что ноды будут по разным страницам разбросаны?
Мерили?
Здравствуйте, Аноним, Вы писали:
А>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>1) память не освобождается А>2) остальные элементы никуда не сдвигаются
А>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
А>Спасибо.
Boost.Circular_Buffer. Его пока ни в одном в официальном релизе. Его недавно добавили в транк, так что он появится в 1.35. А пока его можно просто вырезать оттуда.
Re[4]: stl-контейнер для push_back() / pop_front()
Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>Имеете ввиду что ноды будут по разным страницам разбросаны?
Да.
DL>Мерили?
Нет, но никаких предпосылок к тому, чтобы это было не так вроде нет...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[5]: stl-контейнер для push_back() / pop_front()
От:
Аноним
Дата:
25.12.07 14:01
Оценка:
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>>Имеете ввиду что ноды будут по разным страницам разбросаны? E>Да.
DL>>Мерили? E>Нет, но никаких предпосылок к тому, чтобы это было не так вроде нет...
Почему? При работе с pool allocation сама аллокация происходит единожды — при создании пула. Блок памяти — continuous. На крайний случай, можно сдвинуться вверх до начала ближайшей страницы. Все "аллокации", запрашиваемые из пула — не более чем ковыряние в этой песочнице, изменение внутренних структур. Всё рядышком, по возможности будет максимально затянуто в кэш процессора.
Re[4]: stl-контейнер для push_back() / pop_front()
От:
Аноним
Дата:
31.01.08 11:18
Оценка:
Здравствуйте, AntiFreeze, Вы писали:
AF>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, remark, Вы писали:
R>>>Здравствуйте, Аноним, Вы писали:
А>>>>Подскажите, пожалуйста, есть ли контейнер, работающий по следующим принципам при удалении элемента: А>>>>1) память не освобождается А>>>>2) остальные элементы никуда не сдвигаются
А>>>>Вообще, интересует подходящий контейнер для частых операций push_back()/pop_front().
А>>>>Спасибо.
R>>>std::deque
А>>А почему тогда А>>
А>>Deque reallocation occurs when a member function must insert or erase elements of the controlled sequence. In all such cases, iterators or references that point anywhere within the controlled sequence become invalid
AF>Если нужны такие строгие требования к работе с памятью, придётся самому писать. Хотя вряд ли велоспипед будет лучше чем std::deque.
Не согласен, была похожая проблема (алгоритм поиска в ширину/волновой) написал циклический буффер, результаты замера производительности были с неплохим перевесом на строне последнего (тестировался против deque, vector, list)... Так что...
