Ошибка при использовании erase для std::vector

@Undisputed · Регистрация: 10.06.2014

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

Почему в случае удаления элемента из вектора с помощью передачи итератора в erase, который соответствует позиции удаляемого элемента возникает ошибка(сегфолт)?
Но при этом с той же позиции итератора которая приводит к сегфолту при удалении, получается вывести значение
Т.е при очистки элемента получаем сегфолт, а при выводе значения адрес каким то образом оказывается валидным и значение выводится успешно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//g++  4.9.3
 
#include <iostream>
#include <vector>
 
int main()
{
    int index = 1000;
    int vectorSize = 5;
    
    std::vector<int> v(vectorSize);
    v[index] = 2;
 
    std::vector<int>::iterator nth = v.begin() + (vectorSize - 1);//ошибка при erase, если число которое прибавляется к begin больше количества элементов в векторе
    v.erase(nth);
 
    std::cout << *(v.begin()+index);//но при этом значение успешно выводится для адреса v.begin() + index т.е 1000
}

http://rextester.com/HLMWX81901 валидно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//g++  4.9.3
 
#include <iostream>
#include <vector>
 
int main()
{
    int index = 1000;
    int vectorSize = 5;
    
    std::vector<int> v(vectorSize);
    v[index] = 2;
 
    std::vector<int>::iterator nth = v.begin() + (index - 1);//ошибка при erase, если число которое прибавляется к begin больше количества элементов в векторе
    v.erase(nth);
 
    std::cout << *(v.begin()+index);//но при этом значение успешно выводится для адреса v.begin() + index т.е 1000
}

http://rextester.com/WEJQZS47437 сегфолт

Добавлено через 11 минут
Вот, может так будет нагляднее

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//g++  4.9.3
 
#include <iostream>
#include <vector>
 
int main()
{
    int index = 1000;
    int vectorSize = 5;
    
    std::vector<int> v(vectorSize);
    v[index] = 2;
 
    std::vector<int>::iterator nth = v.begin() + index;//ошибка при erase, если число которое прибавляется к begin больше количества элементов в векторе -1
    //v.erase(nth); если убрать комментарий, будет сегфолт
 
    std::cout << *(nth);//но при этом значение успешно выводится для адреса v.begin() + index т.е 1000
}

http://rextester.com/DNZR40402

Комментарий модератора

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

@rikimaru2013 · 22.12.2016, 13:15

Сообщение от GbaLog-

Везде, где нужно хранить пару элементов, но порядок важен.

А я бы такое не использовал(((

@DrOffset · 22.12.2016, 13:18

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

И где вы советуете такое использовать?

В boost есть контейнер flat_map построенный по такому принципу - упорядоченный вектор пар.

@Undisputed · 22.12.2016, 13:23 **[ТС]**

DrOffset,
Не обошлось без твоей большой помощи, за что тебе ещё раз спасибо )) что бы реализовать такой контейнер, достаточно обойтись заменой аллокатора? Или ещё что то нужно будет сделать?
По использованию своего аллокатора для map не могу найти доступную информацию
Может ты знаешь где можно прочитать об этом более подробно? Что бы у меня появилось достаточно знаний для того что бы запрограммировать это

Добавлено через 1 минуту
И ещё важно что бы все операции с данными контейнера (поиск, вставка, пометить кусок как свободный) происходили за константное время

Добавлено через 1 минуту
А map насколько понимаю использует двоичный поиск, а это уже не константное время как минимум для поиска
так же он будет тратить время на то что бы хранить ключи упорядоченно
это все лишняя трата ресурсов которая мне не нужна

@DrOffset · 22.12.2016, 13:32

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

И ещё важно что бы все операции с данными контейнера (поиск, вставка, пометить кусок как свободный) происходили за константное время

Экий ты

Хочешь, чтобы все "бесплатно" было?
О-характеристики вставки и поиска останутся теми же, аллокатор на это не повлияет. Если тебя устраивает хеш-контейнер по характеристикам, то можно попробовать поменять аллокатор у unordered_map.

Вообще, в таких специальных случаях каждое решение нужно рассматривать отдельно. Например, если нужен быстрый поиск и относительно быстрая вставка, а элементы должны храниться в непрерывном куске памяти и при этом они поддерживают быстрый swap, то можно действительно сделать вектор пар (с резервом памяти), сначала добавить туда все элементы, потом разом отсортировать, а потом за O(log(n)) искать в нем бинарным поиском. Все за и против решаются профилированием и требованиями конкретной задачи. При этом надо понимать, что абстрактная оценка O(1) в конкретном случае (на практике) может быть хуже, чем абстрактная O(log(n)) из-за свойств данных, которые мы обрабатываем. Поэтому только профилирование.

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

Может ты знаешь где можно прочитать об этом более подробно?

Навскидку, в книге Александреску был раздел, посвященный написанию своего аллокатора. Полный исходный код доступен в его библиотеке Loki. Но эта тема уже не совсем для начинающих.

@Undisputed · 22.12.2016, 14:09 **[ТС]**

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

Если тебя устраивает хеш-контейнер по характеристикам, то можно попробовать поменять аллокатор у unordered_map.

Да. Наверное все таки буду смотреть в сторону unordered_map

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

При этом надо понимать, что абстрактная оценка O(1) в конкретном случае (на практике) может быть хуже, чем абстрактная O(log(n)) из-за свойств данных, которые мы обрабатываем.

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

Добавлено через 1 минуту

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

Экий ты Хочешь, чтобы все "бесплатно" было?

Готов платить сложностью реализации )) Осталось выяснить какие есть варианты и как они реализуются

@hoggy · 22.12.2016, 14:41

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

очевидно что второй вариант оказался в 10 раз быстрее чем обычный new

забить и не париццо?

@Undisputed · 22.12.2016, 14:43 **[ТС]**

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

забить и не париццо?

Никак нет

Добавлено через 1 минуту
Иначе какой смысл писать на С++

@hoggy · 22.12.2016, 14:49

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

Никак нет

у вас там всего 5 элементов.
это экономия уже даже не на спичках, а на микробах

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

Иначе какой смысл писать на С++

смысл в том, что умные контейнеры писались умными дядьками.
умные компиляторы умеют строить умный машинный код.

программы на плюсах эффективнее
какого нибудь питона просто потому что плюсы.

а оптимизировать есть смысл только если будут реальные тормоза.
и только те места, на которые реально укажет профайл.

не над тромбовать себе моск)))

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

@Undisputed · 22.12.2016, 14:56 **[ТС]**

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

у вас там всего 5 элементов.

Это для примера было 5

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

какого нибудь питона просто потому что плюсы

Я так сказал к тому, что на питонах люди почти не думают о ресурсах и скорости, работает ну и ладно

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

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

Согласен. Но если заранее известно что можно сделать быстрее чем есть по умолчанию, то почему бы и нет

За одно и детали изучить, левел ап как никак

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

на СО есть кучка простых но годных реализаций

Поищу. Спасибо

@hoggy · 22.12.2016, 15:22

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

Я так сказал к тому, что на питонах люди почти не думают о ресурсах и скорости, работает ну и ладно

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

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

Но если заранее известно что можно сделать быстрее чем есть по умолчанию, то почему бы и нет

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

я уже молчу, про то, что если вы там парсить xml собрались,
то первая же однократная операция чтения данных с диска,
и все эти ваши оптимизации не заметит даже центральный процессор

@Undisputed · 22.12.2016, 15:29 **[ТС]**

hoggy,
Ну можно же 1 раз реализовать, а потом использовать там где нужно

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

)

@rikimaru2013 · 22.12.2016, 16:54

Не по теме:

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

программы на плюсах эффективнее
какого нибудь питона просто потому что плюсы.

сказал как отрезал) :p

Добавлено через 1 минуту

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

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

Абсолютно верно - оставлю тут даже ссылку https://rsdn.org/article/philosophy/Complexity.xml

@DrOffset · 22.12.2016, 17:09

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

Готов платить сложностью реализации

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

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

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

Если данные таковы, что их хеширование занимает значительное время, или хеш-функция дает большое число коллизий, то о константном времени речь идти не может.
Оценка времени в константу дается для общего случая, а конкретный профит или его отсутствие можно получить только на конкретных данных. На конкретных данных и конкретном железе вполне может быть так (просто как пример), что неэффективная в общем случае пузырьковая сортировка будет лучше, чем quicksort.

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

Не понимаю, какое отношение обработка данных имеет к поиску/вставке/удалению?

А вставка, поиск и удаление - это не обработка?

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

@Undisputed · 22.12.2016, 17:29 **[ТС]**

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

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

Не понимаю

Хеш ведь вычисляется за константное время(ну или почти), так? Вычислили ключ и делаем что нужно, вставку или поиск по ключу (точнее, arr[hashkey] для поиска, arr[hashkey] = value для вставки)

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

или хеш-функция дает большое число коллизий

А нельзя разве реализовать функцию без коллизий?

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

Любой поиск использует характеристики данных

Когда я говорил "поиск" имелось ввиду поиск по ключу а не по значению

@DrOffset · 22.12.2016, 17:38

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

Хеш ведь вычисляется за константное время(ну или почти), так?

С чего бы это? Это зависит от того, что у нас за данные.
Например хеш от строки может быть вполне линейным. При этом, если образовалась коллизия, то нам все-таки потребуется еще и сравнение самих строк.

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

А нельзя разве реализовать функцию без коллизий?

В отдельных случаях можно, см. perfect hash, но это далеко не всегда возможно.

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

Когда я говорил "поиск" имелось ввиду поиск по ключу а не по значению

Это вообще не играет роли. Когда я говорю "данные", я имею в виду в том числе и те данные, которые используются в качестве ключа.

Добавлено через 2 минуты
sys_beginner, вообще советую взять какую-нибудь хорошую книгу по алгоритмам, Седжвика, Кнута или Кормена, и хотя бы полгодика поизучать, а потом уже возвращаться к теме оптимизации. Мы же помним, что "преждевременная оптимизация - корень всех зол"?

@Undisputed · 22.12.2016, 17:48 **[ТС]**

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

Это зависит от того, что у нас за данные.

Т.е например для чисел 0-9 будет приблизительно одинаковое, 10-100 может быть чуть больше чем 0-9?

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

Мы же помним, что "преждевременная оптимизация - корень всех зол"?

Да. Но конкретно в данном случае понимаю что можно реализовать более производительный контейнер хотя бы потому что не будет вызываться new/delete на каждый чих

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

вообще советую взять какую-нибудь хорошую книгу по алгоритмам, Седжвика, Кнута или Кормена, и хотя бы полгодика поизучать

Это очень скучно. Пол года читать книжку не работая над реальными задачами и то что я прочитаю в первые три месяца почти забуду в течении оставшихся 3 месяцев ))
Мне легче дается когда возникает задача и нужно её решить определенным способом
Я долго бьюсь в поисках решения но из за долгих размышлений общие принципы конкретного решения хорошо откладываются

@DrOffset · 22.12.2016, 17:55

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

Это очень скучно.

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

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

Пол года читать книжку не работая над реальными задачами

Вообще никто про это не говорит. В том же Седжвике есть интересные задачки на закрепление материала.

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

Т.е например для чисел 0-9 будет приблизительно одинаковое, 10-100 может быть чуть больше чем 0-9?

С числами проще всего, если предполагается, что число - это и есть его хеш.
Но это лишь частный случай.
Я хотел сказать, что нужно помнить о том, что серебряной пули нет. И утверждать, что какое-то средство всегда лучше - опрометчиво и недальновидно.

@Undisputed · 22.12.2016, 17:59 **[ТС]**

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

С числами проще всего, если предполагается, что число - это и есть его хеш.

А как быть если к примеру у нас массив с 5 элементами, а ключи могут быть 1000,2000 и т.д? В таком ведь случае например для вектора понадобится резервировать количество элементов равное размеру максимального числового ключа? А по факту место нужно только для 5 элементов. Вот мне нужно что то в этом роде. И возможность пометить память пустой если элемент удален что бы занять её другим значением. Ключи могут быть какие угодно (но все числовые)

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

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

Ну если текущий вопрос где то освящен с удовольствием прочту

знать бы где именно

@DrOffset · 22.12.2016, 18:05

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

Ну если текущий вопрос где то освящен с удовольствием прочту

Ну хотя бы википедию прочитать-то можно?

@Undisputed · 23.12.2016, 10:28 **[ТС]**

DrOffset,
Пришел к тому, что хеш таблица не поможет для решения данной задачи
Ошибка при использовании erase для std::vector
плюс нужна константная сложность для поиска по индексу/удаления/вставки

Попробую объяснить почему
Насколько я понимаю, хеш функция без коллизий реализуется использованием отстатка деления индекса на фиксированное количество элементов(плюс ещё какие то не понятные мне побитовые операции и сдвиги что бы избавиться от коллизий).

Но как это работает до меня не доходит. Ведь например есть массив из 5 элементов, так? Если туда передать десять разных ключей, то получится что будет либо коллизия, либо выход за границы массива. Для коллизий прочитал что используют связные списки. Но что если списки мне не нужны. Ну не нужно мне хранить под одним ключом несколько значений.
Когда следует применять perfect hash, так и не понял

Но явно не в моем случае, да?

Добавлено через 8 минут
Помоему в решении данного вопроса нужна идеология того аллокатора который ты помог мне разобрать
Но как туда прикрутить индексы с константной сложностью для добавления/удаления/поиска по индексу пока не могу понять
Но чую там что то нужно изменить т.к на одном списке в данной задаче далеко не уедешь

Добавлено через 3 минуты
Пока самый тупой вариант который пришел мне в голову это создать обычный массив Type *t = new Type[size] и зарезервировать место для хранения большого числа элементов. Тогда сложность вроде будет константная. Да?
Но допустим в конкретном случае у меня будет 5 элементов в массиве с индексами 1000,2000,3000,4000,5000. Выходит из за 5 элементов мне нужно будет зарезервировать место для 5000 элементов что слишком много. А дальше если появится индекс с ещё большим числом, прибавить ещё места в массиве что бы сохранить этот индекс
Но может быть реально и 3000 элементов, когда как.

Новые блоги и статьи Все статьи Все блоги /
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .

@Undisputed 901 / 478 / 93 Регистрация: 10.06.2014 Сообщений: 2,700
	22.12.2016, 13:23 [ТС]
	DrOffset, Не обошлось без твоей большой помощи, за что тебе ещё раз спасибо )) что бы реализовать такой контейнер, достаточно обойтись заменой аллокатора? Или ещё что то нужно будет сделать? По использованию своего аллокатора для map не могу найти доступную информацию Может ты знаешь где можно прочитать об этом более подробно? Что бы у меня появилось достаточно знаний для того что бы запрограммировать это Добавлено через 1 минуту И ещё важно что бы все операции с данными контейнера (поиск, вставка, пометить кусок как свободный) происходили за константное время Добавлено через 1 минуту А map насколько понимаю использует двоичный поиск, а это уже не константное время как минимум для поиска так же он будет тратить время на то что бы хранить ключи упорядоченно это все лишняя трата ресурсов которая мне не нужна 0

@Undisputed 901 / 478 / 93 Регистрация: 10.06.2014 Сообщений: 2,700
	22.12.2016, 15:29 [ТС]
	hoggy, Ну можно же 1 раз реализовать, а потом использовать там где нужно При этом пользоваться только наружним API контейнера, и говнокод будет скрыт ) 0

@Undisputed 901 / 478 / 93 Регистрация: 10.06.2014 Сообщений: 2,700
	23.12.2016, 10:28 [ТС]
	DrOffset, Пришел к тому, что хеш таблица не поможет для решения данной задачи Ошибка при использовании erase для std::vector плюс нужна константная сложность для поиска по индексу/удаления/вставки Попробую объяснить почему Насколько я понимаю, хеш функция без коллизий реализуется использованием отстатка деления индекса на фиксированное количество элементов(плюс ещё какие то не понятные мне побитовые операции и сдвиги что бы избавиться от коллизий). Но как это работает до меня не доходит. Ведь например есть массив из 5 элементов, так? Если туда передать десять разных ключей, то получится что будет либо коллизия, либо выход за границы массива. Для коллизий прочитал что используют связные списки. Но что если списки мне не нужны. Ну не нужно мне хранить под одним ключом несколько значений. Когда следует применять perfect hash, так и не понял Но явно не в моем случае, да? Добавлено через 8 минут Помоему в решении данного вопроса нужна идеология того аллокатора который ты помог мне разобрать Но как туда прикрутить индексы с константной сложностью для добавления/удаления/поиска по индексу пока не могу понять Но чую там что то нужно изменить т.к на одном списке в данной задаче далеко не уедешь Добавлено через 3 минуты Пока самый тупой вариант который пришел мне в голову это создать обычный массив Type *t = new Type[size] и зарезервировать место для хранения большого числа элементов. Тогда сложность вроде будет константная. Да? Но допустим в конкретном случае у меня будет 5 элементов в массиве с индексами 1000,2000,3000,4000,5000. Выходит из за 5 элементов мне нужно будет зарезервировать место для 5000 элементов что слишком много. А дальше если появится индекс с ещё большим числом, прибавить ещё места в массиве что бы сохранить этот индекс Но может быть реально и 3000 элементов, когда как. 0