Получение самого правого элемента в unordered_set (или печать содержимого в обратном порядке)

Question

У меня есть unordered_set следующим образом:

unordered_set <long> valueSet;

/*the following insertion is done in order (from 1 to 10000), 
 *unordered_set will keep the elements based on the insertion order, right, 
 *just like in a vector ?
**/

for(long i = 1; i <= 10000;++i)
{
        valueSet->insert(i);
}

Затем я выполнил другую функцию, которая стерла около 85% элементов в этом unordered_set.(Элементы, которые должны быть удалены, зависят от логики этой функции, но это не имеет значения, поскольку все элементы были изначально вставлены по порядку).

Теперь после стирания некоторых элементов в unordered_set,Я хочу напечатать последний элемент, который все еще остается в этом unordered_set.Например, элементы 9997, 9998, 9999 и 10000 были стерты, поэтому самый большой оставшийся элемент в этом наборе - 9996. Как это сделать?
Если используется базовый набор, я могу сделать следующее:

set <long>::reverse_iterator it = valueSet.rbegin();
cout << *it << endl;

В наборе у нас есть reverse_iterator, а также rbegin (), но его нет в unordered_set.Причина, по которой я не сделал базовый набор, заключается в том, что мне нужен размер элемента для масштабирования до 10 ^ 8.Использование обычного набора (основанного на красно-черных деревьях) действительно убьет производительность (особенно, когда речь идет о вставке и удалении).Как я могу это сделать?Копирование окончательного оставшегося unordered_set в вектор будет работать, но, конечно, это займет время.Как я могу добиться этого, используя более умный способ?Я заметил, что я также не могу сделать что-то вроде:

unordered_set <long>::iterator it = valueSet.end();
//operator -- does not exist here in the unordered_set
it--;

Answer 1

Из того, что я собрал из ваших комментариев, здесь следует использовать std :: bitset или его динамический аналог boost :: dynamic_bitset .Вы получаете O (1) вставки и удаления и O (N) для определения максимального элемента (с помощью линейного поиска).Можно даже утверждать, что нахождение максимума - это амортизированное значение O (1), так как вам нужно сделать не более столько шагов поиска, сколько операций удаления.

Answer 2

Ты не можешь съесть свой торт и съесть его.

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

Если вы не заботитесь о порядке, тогда вам лучше использовать std::deque или std::vector (предпочтительнее первое, если вам нужно вставить спереди).

Answer 3

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

Почему бы просто не использовать std :: vector с самого начала?

Answer 4

Хранить удаленные элементы в векторе.Когда закончите, преобразуйте в кучу.(O (n), где n - количество удаленных элементов) Затем многократно удаляйте максимальное значение из кучи, пока не найдете самый высокий элемент, который не был удален.Это O (m log n), где m - это разница между вашим максимальным значением и ответом.