Mercury13, Древовидная система может использовать не указатели (адреса), а индексы объектов в ввекторе. Сами ваши объекты создаются и удаляются в каком-то массиве. Свободное место можно в этом массиве организовать в список использую уже имеющееся поля у объектов. В такой структуре вы сможете за O(1) освободить элемент или создать новый. Пометить его пустым, или удаленным.
dollar, QuickSelect'ом надо взять только N-ый элемент один раз. Тогда первые N элементов будут в начале массива (ведь именно так quickselect и гарантирует, что N-ый элемент будет где надо).
Еще раз, quickselect (хоть и с большой константой) работет за линию в худшем случае без каких-либо допущений.
Наличие random'а позволяет на практике получить быстрый линейный алгоритм.
Или есть также алгоритмы быстрее O(n log n), хоть и не линейные, но работающие быстро и не в среднем.
dollar, Ваши поблажки (предположения о распределении чисел) весьма серъезные. Плюс даже с ними ваш алгоритм работает линейно лишь в среднем. Ведь может так оказаться, что все числа в массиве больше 970.
А приведенный мной, работающий за линию в среднем, алгоритм без поблажек - имеет константу примерно 2.
И его модификация с алгоритмом Блюма-Флойда-Пратта-Ривеста-Тарьяна будет работать за O(N) всегда, вне зависимости от размера K. Да, там мделенная константа, но это не важно. Этот алгоритм уже опровергает ваше "строго - никак".
2.Ну да, самый тупой и медленный вариант. Но, возможно, самый простой. А при малых N и небольшом размере массива, возможно, эти недостатки не будут иметь значения.
Этот ваш алгоритм по скорости равен "N раз найти минимум в массиве". Работает за O(M N), где M - длина массива.
Но вы почти додумались до хорошего алгоритма. Надо в acc использовать не массив, а кучу или приоритетную очередь на максимум. Тогда поиск вытесняемого элемента будет за O(log n).
Есть, есть строгие алгоритмы. Работающие за линейную сложность, гарантрованно возвращающие первые N элементов. Правда на практике используются скорее алгоритмы, которые или работют за O(M log N) или за O(M) в среднем (где M - размер массива).
Не надо quickSelect вызвать N раз. После вызова с параметром N первые N элементов уже будут минимальными. N-ый будет на своем месте, а вот все пердыдущие могут быть и перемешаны. Ведь quickselect гарантирует правильность N-ого элемента именно тем, что все левее его - меньше его, а все правее - больше.
А выбор минимума N раз - это самое плохое, что можно сделать.
Если массив маленький, то тупо сортировка будет быстрее чем N раз искать минимум. Если N маленькое, то алгоритм с кучей из моего ответа будет гораздо быстрее.
Армянское Радио, задание кодировки исходников совсем не тоже самое, что подменять строки полностью по какому-то никак нестандартизованному алгоритму, нигде не описанному.
Армянское Радио, Да ну, не верю, что компилятор будет строки константы переписывать. А вдруг они будут по сети посылаться? Или интерпретироваться как числа? Это же тупо набор байт. Я еще готов поверить, что wcout насилует строки при выводе, но это вряд ли. Скорее редактор при сохранении корябит исходник. Но еще более вероятно, что ничего этого не происходит и автор просто запускает что-то не то. Транслит - убогая практика, появившаяся от не поддержки кирилицы в разных сценариях. То, что этот ужас где-то действительно реализован как валидная стратегия локализации - это очень вряд ли.
Spooky 2020, поменяйте русскую строку первую. Добавьте, например, "аба" в конец, перекомпилируйте, запустите. Проверьте, действительно ли порограмма выводит это самое "аба" как "aba"? Я думаю, что вывод не изменится, потому что вы что-то не то компилируете или запускаете.
Приведите минимальный код (удалите все неважное из программы. В идеале оставьте только константу и вывод). Удостоверьтесь, что он именно так себя и ведет.
Такой транслитерации не может нигде происходить. Вы или не то запускаете, или не разобрались с чужим кодом.
Mercury13, Добавлю, что вы пытаетесь детектировать UB через другое UB. То, что оно иногда сработает лишь даст вам ложную илюзию отстуствия UB в вашем коде. Если всякие аналоги valgrind не вариант, то подумайте над тем, как передавать через qt не голые указатели. Хоть guid, хоть индекс в массиве объектов будет тогда уж лучше, если наличие вот этого не-вашего кода так все усложняет, что надо городить всякие хаки для проверки на висячие указатели.
Mercury13, Короче. Я понял. Это у вас оппортунистская проверка - задетектить UB после того, как оно произойдет. Оппортунистское, потому что все-равно может на какой-нибудь системе упасть во время проверки данных не в своей памяти, плюс то что там кто-то левый положет потом может случайно стать равно SCRAMBLE.
И ответ на ваш вопрос - нет, компиялтор может и удалить. Есть всякие платформо-зависимые функции для гарантированного зануления памяти, но как их прикрутить к атомикам - я не знаю. Но вообще компилятор может додуматся, что во время жизни объекта value не меняется и вообще удалить проверку нафиг.
Я бы не городил этот огород, а использовал тот же valgrind для проверки. Ну или, если хотите, то вам придется написать собственный менеджер памяти. Переопределить new и delete и или не удалять память вообще и там внутри где-то как-то помечать (например, выделить на 4 байт больше перед данными). Или где-то запоминать, что память отчищена и проверять на висячие указатели какой-то функцией, отдельной от возможно удаленного объекта.
