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

Question

У меня есть неупорядоченный набор, как показано ниже:

[1,2,3,4,6,7,5]

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

IВ настоящее время я делаю следующее.Есть ли более быстрый способ сделать это?

auto it = set_of_ints.begin();
set_of_ints.erase(it);
.....
.....
std::cout << "removed element is: " << *it << std::endl;

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

Answer 1

Нет, нет более быстрого способа удалить элемент набора, чем erase.Если вы не намерены перенести элемент в другой набор, в этом случае extract может быть быстрее в целом.

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

---

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

Постоянное среднее предполагает равномерное распределение ключей и хорошую хэш-функцию.

---

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

Answer 2

Нет, функция-член std::unordered_set::erase является единственной функцией, предназначенной для использования при удалении элементов из набора, а документы говорят:

Сложность
Учитывая экземпляр c unordered_set:
1) Средний регистр: постоянный, худший случай: c.size ()
[...]

Так почемуэто c.size() в худшем случае?Обратите внимание, что erase имеет возвращаемое значение:

Возвращаемое значение
1-2) Итератор, следующий за последним удаленным элементом.
[...]

Функция должна найти «следующий элемент».std::unordered_set сохраняет свои данные в так называемых списках сегментов.В идеале, это следующий доступный слот в том же списке, что и тот, который содержит элемент, который вы удаляете.В худшем случае, это последний доступный слот в каком-то другом ведре (и, следовательно, он масштабируется с размером контейнера).Это зависит от истории вставки / удаления контейнера.Вы можете взглянуть на реализацию libcxx здесь , там есть цикл, пересекающий узлы в списке сегментов (механизм хорошо объяснен ответом @ eeroika ).

---

Кроме того, не это (также из документов по erase):

Ссылки и итераторы для стертых элементов недействительны

Такразыменование итератора it после его удаления из набора - неопределенное поведение.Вы можете исправить это по

auto it = set_of_ints.begin();
const int value = *it;

set_ot_ints.erase(it);

std::cout << "removed element is: " << value << "\n";