Форум программистов, компьютерный форум CyberForum.ru

Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? - C++

Восстановить пароль Регистрация
 
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
24.06.2014, 17:59     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #1
Привет, народ! Посоветуйте, что лучше использовать.

В моей задаче нужен массив, с возможностью добавления и удаления элементов, при этом добавлять можно куда угодно - в конец, например, а удаление может происходить отовсюду - из середины, из начала, и т.д.. При этом порядок элементов после удаления неважен. Что используют в таком случае? Вектор, список, или что другое?

Если можно - небольшой пример))
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2014, 17:59     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)?
Посмотрите здесь:

C++ Реализовать приложение, содержащее функции добавления нового элемента в массив и удаления элемента из массива. (Имитируется “резиновый” массив)
C++ функция удаления и добавления элементов. что не так с програмой?
Какой STL-контейнер выбрать? C++
Стеки, функции добавления и удаления элементов C++
Написать кольцевой список с возможностями добавления, удаления и поиска элементов, и сохранения в файл. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RamonN
 Аватар для RamonN
32 / 32 / 11
Регистрация: 13.07.2011
Сообщений: 136
24.06.2014, 18:11     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #2
Используйте вектор
Смотрите описания методов:
vector::insert Вставка элементов в вектор
vector::erase Удаляем указанные элементы вектора (один или несколько)
IrineK
Заблокирован
24.06.2014, 19:35     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вектор - готовое решение.

Можно написать свой контейнер. На основе списка - однонаправленного, двунаправленного, на основе динамического массива.
Свой контейнер можно реализовать структурой или классом.

Выбирайте.
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
25.06.2014, 02:24  [ТС]     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #4
Да, я собственно вектор и использую, но прав ли я: при удалении центрального элемента, все стоящие за ним будут переписываться на позицию назад? Ведь это довольно дорогая процедура для больших векторов? Так как порядок для меня неважен, стоит ли при удалении i-ого указателя сделать так:

C++
1
2
3
delete MyVec[i];
MyVec[i] = MyVec.back();
MyVec.pop_back();
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
25.06.2014, 02:28     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #5
Цитата Сообщение от Антон219 Посмотреть сообщение
Так как порядок для меня неважен, стоит ли при удалении i-ого указателя сделать так:
Имеет, только стоит помнить, что память, которую занимал сам указатель (последний элемент вектора) не освободится.
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
25.06.2014, 02:42  [ТС]     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #6
gray_fox, а как ее освободить тогда? Что добавить в код? не могу сообразить
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
25.06.2014, 02:58     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #7
Антон219, std::vector - это обёртка для массива по сути. Т.е. если ты хочешь освободить уже не используемую память, то придётся выделить новый блок памяти нужного размера, скопировать туда оставшееся содержимое массива, освободить старый участок памяти; в std::vector это всё конечно напрямую делать не надо, но "под капотом" будет именно это, и это не быстро (выделение\освобождение памяти + копирование); но если хочется, есть метод std::vector::shrink_to_fit. Если его нет (старый стандарт языка), то есть трюк с методом swap:
C++
1
std::vector<element_type>(vector).swap(vector);
Добавлено через 7 минут
Вообще смысла в подобной "чистке" обычно нет, если только из контейнера не удаляется большая часть элементов и вам памяти жаль)
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
25.06.2014, 03:33  [ТС]     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #8
gray_fox, ясно, то есть сэкономить все равно не удасться в этом случае. А что случиться, когда я добавлю в конец новый элемент? Выделится новая память под него, или он все же запишется поверх той, неосвобожденной памяти?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2014, 04:01     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)?
Еще ссылки по теме:

Определить структуру данных, поддерживающую функции добавления, удаления и вывода элементов C++
Создать массив указателей с возможностью удаления любого элемента C++
Какой контейнер STL выбрать? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Renji
1534 / 982 / 240
Регистрация: 05.06.2014
Сообщений: 2,957
25.06.2014, 04:01     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? #9
В моей задаче нужен массив, с возможностью добавления и удаления элементов, при этом добавлять можно куда угодно - в конец, например, а удаление может происходить отовсюду - из середины, из начала, и т.д..
Все просто как мычание.
1) std::vector - можно получить любой элемент за константное время. Но добавление/удаление элемента займет время пропорциональное размерам массива.
2) std::map - добавление/удаление займет логарифмическое время (вдвое больше тормозов каждый раз когда размер возводится в квадрат). Но поиск произвольного элемента также займет логарифмическое время.
3) std::list - удаление/добавление за константное время. Но элементы читать можно только по порядку.
Выбирай что больше подходит.
Т.е. если ты хочешь освободить уже не используемую память, то придётся выделить новый блок памяти нужного размера, скопировать туда оставшееся содержимое массива, освободить старый участок памяти
Это уже от реализации realloc зависит. Он может и просто прописать "занятый блок А уменьшился на один байт, свободный блок Б увеличился на один байт".

Добавлено через 7 минут
UPD еще можно попробовать std::unordered_map. При правильном расположении звезд поиск/вставка/удаление делаются за константное время. При неправильном расположении - как повезет. Перебор элементов возможен, но порядок элементов опять же зависит от звезд. И чтоб оно работало быстро, unordered_map должно заранее хапнуть памяти с большим запасом.
Yandex
Объявления
25.06.2014, 04:01     Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)?
Ответ Создать тему
Опции темы

Текущее время: 06:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru