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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
#1

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

24.06.2014, 17:59. Просмотров 665. Ответов 8
Метки нет (Все метки)

Привет, народ! Посоветуйте, что лучше использовать.

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

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

Какой контейнер выбрать? - C++
Добрый день. Подскажите, какой контейнер стоит выбрать? Пара ключ-значение, отдельно. Значение может повторяться. Ключ - текущий размер...

Какой контейнер выбрать? - C++
Доброго времени суток, Господа. Такая есть задача. Есть объект Scene, который является контейнером для объектов System и еще...

Какой STL-контейнер выбрать? - C++
Приветствую! Мне нужно выбрать STL-контейнер (C++11), для хранения элементов по ключу. Типа ключа - std::string, элемент - указатель...

Какой контейнер STL выбрать? - C++
Во входном потоке (FILE*) дано множество точек. Найти пару точек, расстояние между которыми минимально. Ввод и вывод в произвольной форме....

Какой ассоциативный контейнер выбрать? И как реализовать в нем чтение из файла? - C++
Вот сама задание: Текстовый файл содержит следующую информацию: координату точки и угол наклона прямой, проходящей через эту точку....

Создать массив указателей с возможностью удаления любого элемента - C++
Привет, друзья! Мне в одной программе нужно было создать массив указателей с возможностью удаления любого элемента, сделал с помощью...

8
RamonN
32 / 32 / 11
Регистрация: 13.07.2011
Сообщений: 138
24.06.2014, 18:11 #2
Используйте вектор
Смотрите описания методов:
vector::insert Вставка элементов в вектор
vector::erase Удаляем указанные элементы вектора (один или несколько)
1
IrineK
Заблокирован
24.06.2014, 19:35 #3
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вектор - готовое решение.

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

Выбирайте.
1
Антон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();
0
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
25.06.2014, 02:28 #5
Цитата Сообщение от Антон219 Посмотреть сообщение
Так как порядок для меня неважен, стоит ли при удалении i-ого указателя сделать так:
Имеет, только стоит помнить, что память, которую занимал сам указатель (последний элемент вектора) не освободится.
1
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
25.06.2014, 02:42  [ТС] #6
gray_fox, а как ее освободить тогда? Что добавить в код? не могу сообразить
0
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 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 минут
Вообще смысла в подобной "чистке" обычно нет, если только из контейнера не удаляется большая часть элементов и вам памяти жаль)
1
Антон219
0 / 0 / 0
Регистрация: 09.06.2013
Сообщений: 68
25.06.2014, 03:33  [ТС] #8
gray_fox, ясно, то есть сэкономить все равно не удасться в этом случае. А что случиться, когда я добавлю в конец новый элемент? Выделится новая память под него, или он все же запишется поверх той, неосвобожденной памяти?
0
Renji
1925 / 1323 / 298
Регистрация: 05.06.2014
Сообщений: 3,808
25.06.2014, 04:01 #9
В моей задаче нужен массив, с возможностью добавления и удаления элементов, при этом добавлять можно куда угодно - в конец, например, а удаление может происходить отовсюду - из середины, из начала, и т.д..
Все просто как мычание.
1) std::vector - можно получить любой элемент за константное время. Но добавление/удаление элемента займет время пропорциональное размерам массива.
2) std::map - добавление/удаление займет логарифмическое время (вдвое больше тормозов каждый раз когда размер возводится в квадрат). Но поиск произвольного элемента также займет логарифмическое время.
3) std::list - удаление/добавление за константное время. Но элементы читать можно только по порядку.
Выбирай что больше подходит.
Т.е. если ты хочешь освободить уже не используемую память, то придётся выделить новый блок памяти нужного размера, скопировать туда оставшееся содержимое массива, освободить старый участок памяти
Это уже от реализации realloc зависит. Он может и просто прописать "занятый блок А уменьшился на один байт, свободный блок Б увеличился на один байт".

Добавлено через 7 минут
UPD еще можно попробовать std::unordered_map. При правильном расположении звезд поиск/вставка/удаление делаются за константное время. При неправильном расположении - как повезет. Перебор элементов возможен, но порядок элементов опять же зависит от звезд. И чтоб оно работало быстро, unordered_map должно заранее хапнуть памяти с большим запасом.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2014, 04:01
Привет! Вот еще темы с ответами:

Стеки, функции добавления и удаления элементов - C++
Программа на стеки выводит на экран 9876543210 ..помогите сделать так, чтобы можно было вводить вручную, удалять элементы из стека,...

функция удаления и добавления элементов. что не так с програмой? - C++
#include &lt;iostream&gt; using namespace std; struct node{ double a; double b; node *next;}; node *head= NULL; node *p,...

Красно-черное прошитое дерево с функцией добавления и удаления элементов - C++
Доброго времени Суток! Помогите пожалуйста,необходимо реализовать красно-чёрное дерево по таким условиям: &quot;Создать красно-черное прошитое...

Создать очередь, написать функции для добавления/удаления элементов - C++
Добрый. Помогите, пожалуйста. Задание: Разработать функции, позволяющие: 1)создать очередь; 2)добавлять в нее элементы; 3)извлекать...


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

Или воспользуйтесь поиском по форуму:
9
Yandex
Объявления
25.06.2014, 04:01
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru