Реализовать динамический список с добавлением, изменением и удалением элементов по индексу

@Tester64 · Регистрация: 22.05.2013

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

Подскажите класс, для хранения динамических списков классов. Не хочу изобретать велосипед, а пока ничего адекватного не нашел...

В Делфи есть TList. В яве есть List<int> my. Вроде и в с++ есть list<int> list_int; Но насколько я понял, это больше похоже на стек, чем на список (или я ошибаюсь?)...

Нужно добавлять записи, сортировать их, получать с любого места по номеру(счетчику)(перебирать), удалять по номеру, ...

Подскажите хотя-бы название класса (не охота вычитывать про все варианты в учебнике на 1000 страниц). Несколько раз встречал примеры как написать подобный список с нуля - могу конечно, но может есть готовый...

@castaway · 02.09.2014, 07:54

Как раз std::list тебе и подойдёт.

@0x10 · 02.09.2014, 08:52

std::vector

@Fallenworld · 02.09.2014, 10:50

и лист и вектор обьявляются с любым типом

C++
1
vector<type> v;

хранит обьекты типа type

Не по теме:

всегда было интересно, почему память в векторе выделяется как +=size/2, а не для каждого нового элемента. Очевидный ответ, про скорость записи, правда?

@aLarman · 02.09.2014, 12:10

Fallenworld, что бы не перевыделять память при добавлении нового эл-та(перевыделение есть но перевыделений намного меньше чем добавлений)

Добавлено через 56 секунд
Tester64, велосипед изобретать и не надо, std::list<type> type - какой - то тип данных(можно как встроенные так и user defined )

Добавлено через 56 секунд

Сообщение от Tester64

Но насколько я понял, это больше похоже на стек, чем на список (или я ошибаюсь?).

это обычный список - все приколы списка я думаю Вы знаете

Jupiter · 02.09.2014, 13:10

Не по теме:

Сообщение от Fallenworld

всегда было интересно, почему память в векторе выделяется как +=size/2, а не для каждого нового элемента. Очевидный ответ, про скорость записи, правда?

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

@Tester64 · 03.09.2014, 03:49 **[ТС]**

Спасибо! Вектор пока подошел... (ищу недостатки)

Сильно отвлекало подобное:

C++ (Qt)
1
2
3
std::vector<int> myVector; // мы создали пустой вектор типа int
myVector.reserve(10);      // тут мы зарезервировали память под 10 элементов типа int
std::vector<int> myVector(10);

Зачем резервировать, если можно добавлять?

А в чем существенная разница между вектором и списком?

Сообщение от aLarman

это обычный список - все приколы списка я думаю Вы знаете

Увы - нет! Я полный новичок в с++.
Работал раньше в других языках, но здесь (в с++) это намного сложнее... Привык что основа для списка обычно только одна и не нужно вдаваться в ее начинку (механизмы хранения в памяти)
Вроде нашел все базовые (привычные) схемы на основе вектора, но по листу почти пусто... Когда лист лучше вектора?

@КОП · 03.09.2014, 04:14

Сообщение от Tester64

Когда лист лучше вектора?

Когда нужно часто вставлять и удалять из середины, но не нужен произвольный доступ.

@Renji · 03.09.2014, 05:37

Зачем резервировать, если можно добавлять?

Затем что один раз зарезервировать, быстрее чем десять раз добавить.

А в чем существенная разница между вектором и списком?

В списке нельзя "получать с любого места по номеру". Только перебирать все записи по порядку.
Все ссылки на элементы вектора могут сдохнуть при любом изменении его размеров (включая вызов reserve). А могут и не сдохнуть, если фаза Луны удачная. Но лучше на это не полагаться. Плюс, тормоза от изменения размеров вектора прямо пропорциональны его размеру. Тогда как время вставки в список от его размера не зависит.

@Tester64 · 03.09.2014, 05:53 **[ТС]**

Сообщение от Renji

Все ссылки на элементы вектора могут сдохнуть при любом изменении его размеров (включая вызов reserve). А могут и не сдохнуть, если фаза Луны удачная. Но лучше на это не полагаться. Плюс, тормоза от изменения размеров вектора прямо пропорциональны его размеру. Тогда как время вставки в список от его размера не зависит.

Наверно плохо вопрос задал...
Допустим у меня есть сложный класс, который я многократно хочу добавить в список. Если я правильно понял, каждый раз перед добавлением я должен "создать" элемент своего класса (выделив под него память и задав начальные значения) и ссылку на него отправляю в списко/вектор. Что произойдет если я очищу список командой .clear();? В эти классы отправится "команда" на уничтожения (вызов деструктора) или они останутся в памяти с утерянными ссылками на них?

(ООП учил по паскалю и яве)

@Renji · 03.09.2014, 06:01

Если я правильно понял, каждый раз перед добавлением я должен "создать" элемент своего класса (выделив под него память и задав начальные значения) и ссылку на него отправляю в списко/вектор. Что произойдет если я очищу список командой .clear();?

У вас список объектов класса (std::list<my_class>) или список ссылок на объекты (std::list<my_class*>)? Если первое, все деструкторы вызовутся автоматом. Если второе, то не вызовутся. Но если написать std::list<std::unique_ptr<my_class> > то получится список ссылок с автоматическим вызовом деструкторов.

@Tester64 · 03.09.2014, 07:07 **[ТС]**

Сообщение от Renji

У вас список объектов класса (std::list<my_class>) или список ссылок на объекты (std::list<my_class*>)? Если первое, все деструкторы вызовутся автоматом. Если второе, то не вызовутся. Но если написать std::list<std::unique_ptr<my_class> > то получится список ссылок с автоматическим вызовом деструкторов.

Блин, и здесь сложности... Ну и язык... В делфи любой класс является всего-лишь ссылкой... И удалять классы элементов надо самому!

Спасибо! Основы понял, дальше сам разберусь!

@aLarman · 03.09.2014, 10:14

Сообщение от Renji

список ссылок на объекты (std::list<my_class*>)?

это список НЕ ссылок
std::list<my_class>, в такой лист сохраняется копия добавленного объекта
std::list<my_class*> в такой лист сохраняется указатель на объект(если быть точнее копия указателя), если Вы под объект выделяли память, и сохранили указатель, естественно это память надо будет почистить(вызвать delete), если вы добавляли адреса переменных не выделяя память динамически, то удалять не надо, но надо знать что если выйти из области видимости этих переменных, они удалятся, и указатели в списке станут не валидными

Добавлено через 22 секунды
Tester64, Вам какие методы нужны?

Добавлено через 1 минуту
просто у вестора и у листа примерно одинаков набор методов, и стоит учесть что например при удалении элемента вектора, элементы стоящие после него, будут перекопированы, чтобы убрать "дырку", копирование == время

@Tester64 · 03.09.2014, 12:02 **[ТС]**

Сообщение от aLarman

элементы стоящие после него, будут перекопированы

Капец! А если я вместо вектора буду спискок использовать? это исправится?
Ситуация: Хочу текстовый файл прочитать по строкам в память. Каждая строка - собственный класс. Строки могу удалять. Файлы могут быть большими... Если будет милион строк, а удаляю №2, выходит он "на долго" задумывается пока пересоздаст все строки с 3й по миллионую?

@0x10 · 03.09.2014, 12:13

Сообщение от Tester64

Строки могу удалять. Файлы могут быть большими...

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

И да: преждевременная оптимизация - корень всех зол.

Добавлено через 3 минуты
Сравнение производительности вектора и списка: http://baptiste-wicht.com/post... -list.html

@aLarman · 03.09.2014, 12:18

Сообщение от Tester64

Если будет милион строк, а удаляю №2, выходит он "на долго" задумывается пока пересоздаст все строки с 3й по миллионую?

да, но скорее всего Вам система не выделит такой линейный участок памяти, в этом плане будет лучше, наверное, список

Добавлено через 55 секунд
при удалении из списка вызывается деструктор объекта удаляется элемент и указатели соседних элементов переписываются друг на друга

@Renji · 03.09.2014, 17:33

Строки могу удалять. Файлы могут быть большими... Если будет милион строк, а удаляю №2, выходит он "на долго" задумывается пока пересоздаст все строки с 3й по миллионую?

Не будет он ничего пересоздавать. Будет миллион вызовов перемещающего конструктора, скорее всего просто перебрасывающего с места на место ссылки на внутренние буферы. Если, конечно, этот конструктор есть (у std::string есть).

Капец! А если я вместо вектора буду спискок использовать? это исправится?

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

@aLarman · 04.09.2014, 09:13

Сообщение от Renji

время вставки и удаления не зависит от размеров списка

как же не зависит? ему же надо сначала найти место куда вставить

@Jewbacabra · 04.09.2014, 11:20

Сообщение от aLarman

ему же надо сначала найти место куда вставить

зачем искать, в метод insert и так передается место, куда вставить. Другой вопрос если перед вызовом insert TC будет сам искать место вставки в список, но к времени метода insert это не относится.

@aLarman · 04.09.2014, 12:15

Сообщение от Jewbacabra

в метод insert и так передается место, куда вставить

так это место надо самому указать - так что поиск места имеет место быть

Добавлено через 15 секунд

Не по теме:

странная фраза получилась

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Tester64 420 / 357 / 47 Регистрация: 22.05.2013 Сообщений: 2,518

	Реализовать динамический список с добавлением, изменением и удалением элементов по индексу 02.09.2014, 03:43. Показов 3910. Ответов 19 Метки нет (Все метки) Подскажите класс, для хранения динамических списков классов. Не хочу изобретать велосипед, а пока ничего адекватного не нашел... В Делфи есть TList. В яве есть List<int> my. Вроде и в с++ есть list<int> list_int; Но насколько я понял, это больше похоже на стек, чем на список (или я ошибаюсь?)... Нужно добавлять записи, сортировать их, получать с любого места по номеру(счетчику)(перебирать), удалять по номеру, ... Подскажите хотя-бы название класса (не охота вычитывать про все варианты в учебнике на 1000 страниц). Несколько раз встречал примеры как написать подобный список с нуля - могу конечно, но может есть готовый... 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	02.09.2014, 07:54
	Как раз std::list тебе и подойдёт. 1

@0x10 3258 / 2060 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	02.09.2014, 08:52
	std::vector 1