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

@Антон219 · Регистрация: 09.06.2013

Студворк — интернет-сервис помощи студентам

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

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

Если можно - небольшой пример))

@RamonN · 24.06.2014, 18:11

Используйте вектор
Смотрите описания методов:
vector::insert Вставка элементов в вектор
vector::erase Удаляем указанные элементы вектора (один или несколько)

@IrineK · 24.06.2014, 19:35

Вектор - готовое решение.

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

Выбирайте.

@Антон219 · 25.06.2014, 02:24 **[ТС]**

Да, я собственно вектор и использую, но прав ли я: при удалении центрального элемента, все стоящие за ним будут переписываться на позицию назад? Ведь это довольно дорогая процедура для больших векторов? Так как порядок для меня неважен, стоит ли при удалении i-ого указателя сделать так:

C++
1
2
3
delete MyVec[i];
MyVec[i] = MyVec.back();
MyVec.pop_back();

@gray_fox · 25.06.2014, 02:28

Сообщение от Антон219

Так как порядок для меня неважен, стоит ли при удалении i-ого указателя сделать так:

Имеет, только стоит помнить, что память, которую занимал сам указатель (последний элемент вектора) не освободится.

@Антон219 · 25.06.2014, 02:42 **[ТС]**

gray_fox, а как ее освободить тогда? Что добавить в код? не могу сообразить

@gray_fox · 25.06.2014, 02:58

Антон219, std::vector - это обёртка для массива по сути. Т.е. если ты хочешь освободить уже не используемую память, то придётся выделить новый блок памяти нужного размера, скопировать туда оставшееся содержимое массива, освободить старый участок памяти; в std::vector это всё конечно напрямую делать не надо, но "под капотом" будет именно это, и это не быстро (выделение\освобождение памяти + копирование); но если хочется, есть метод std::vector::shrink_to_fit. Если его нет (старый стандарт языка), то есть трюк с методом swap:

C++
1
std::vector<element_type>(vector).swap(vector);

Добавлено через 7 минут
Вообще смысла в подобной "чистке" обычно нет, если только из контейнера не удаляется большая часть элементов и вам памяти жаль)

@Антон219 · 25.06.2014, 03:33 **[ТС]**

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

@Renji · 25.06.2014, 04:01

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

Все просто как мычание.
1) std::vector - можно получить любой элемент за константное время. Но добавление/удаление элемента займет время пропорциональное размерам массива.
2) std::map - добавление/удаление займет логарифмическое время (вдвое больше тормозов каждый раз когда размер возводится в квадрат). Но поиск произвольного элемента также займет логарифмическое время.
3) std::list - удаление/добавление за константное время. Но элементы читать можно только по порядку.
Выбирай что больше подходит.

Т.е. если ты хочешь освободить уже не используемую память, то придётся выделить новый блок памяти нужного размера, скопировать туда оставшееся содержимое массива, освободить старый участок памяти

Это уже от реализации realloc зависит. Он может и просто прописать "занятый блок А уменьшился на один байт, свободный блок Б увеличился на один байт".

Добавлено через 7 минут
UPD еще можно попробовать std::unordered_map. При правильном расположении звезд поиск/вставка/удаление делаются за константное время. При неправильном расположении - как повезет. Перебор элементов возможен, но порядок элементов опять же зависит от звезд. И чтоб оно работало быстро, unordered_map должно заранее хапнуть памяти с большим запасом.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Антон219 0 / 0 / 0 Регистрация: 09.06.2013 Сообщений: 72

	Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)? 24.06.2014, 17:59. Показов 2883. Ответов 8 Метки нет (Все метки) Привет, народ! Посоветуйте, что лучше использовать. В моей задаче нужен массив, с возможностью добавления и удаления элементов, при этом добавлять можно куда угодно - в конец, например, а удаление может происходить отовсюду - из середины, из начала, и т.д.. При этом порядок элементов после удаления неважен. Что используют в таком случае? Вектор, список, или что другое? Если можно - небольшой пример)) 0

@RamonN 32 / 32 / 19 Регистрация: 13.07.2011 Сообщений: 140
	24.06.2014, 18:11
	Используйте вектор Смотрите описания методов: vector::insert Вставка элементов в вектор vector::erase Удаляем указанные элементы вектора (один или несколько) 1

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	24.06.2014, 19:35
	Сообщение было отмечено Антон219 как решение Решение Вектор - готовое решение. Можно написать свой контейнер. На основе списка - однонаправленного, двунаправленного, на основе динамического массива. Свой контейнер можно реализовать структурой или классом. Выбирайте. 1

@Антон219 0 / 0 / 0 Регистрация: 09.06.2013 Сообщений: 72
	25.06.2014, 02:42 [ТС]
	gray_fox, а как ее освободить тогда? Что добавить в код? не могу сообразить 0

@Антон219 0 / 0 / 0 Регистрация: 09.06.2013 Сообщений: 72
	25.06.2014, 03:33 [ТС]
	gray_fox, ясно, то есть сэкономить все равно не удасться в этом случае. А что случиться, когда я добавлю в конец новый элемент? Выделится новая память под него, или он все же запишется поверх той, неосвобожденной памяти? 0

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

Решение