Блог

Я почти понял многие алгоритмы STL, пока не добрался до алгоритма std::nth_element . Я зациклился на этом; я не знаю, как это работает, и это действительно работает точно.

Для образования и понимания, может ли кто-нибудь объяснить мне, как std::nth_element работает алгоритм?

 std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin()   2, v.end());

for (auto i : v)
    std::cout << i << " ";
std::cout << 'n';
 

Вывод:

 1 0 2 3 6 7 8 5 4 9 
 

• Так где же nth здесь элемент?
• Как и что делает алгоритм?
• Выполняет ли он какую-то частичную сортировку?

Вот некоторые объяснения из cppreference.com:

nth_element является алгоритмом частичной сортировки, который переставляет элементы в [первый, последний) таким образом, что:

• Элемент, на который указывает nth, изменяется на любой элемент, который находился бы в этом положении, если бы [первый, последний) был отсортирован.
• Все элементы до этого нового n-го элемента меньше или равны элементам после нового n-го элемента. Более формально, nth_element частично сортирует диапазон [первый, последний) в порядке возрастания, чтобы условие !(*j < *i) (для первой версии или comp(*j, *i) == false для второй версии) выполнялось для любого i в диапазоне [первый, n-й) и для любого j в диапазоне [n-й, последний). Элемент, помещенный в n-ю позицию, является именно тем элементом, который находился бы в этой позиции, если бы диапазон был полностью отсортирован.

n-й может быть конечным итератором, в этом случае функция не действует.

• Я все еще в замешательстве по этому поводу. Что такое n-й элемент и как реализовать подобный возможный алгоритм?. Ради образования я имитировал многие алгоритмы STL. Большое вам спасибо!

Так где же здесь n-й элемент?

n-й элемент-это индекс 2 at 2 , потому что это то, что вы просили, когда проходили begin() 2 .

Элемент, на который указывает nth, изменяется на любой элемент, который находился бы в этом положении, если бы [первый, последний) был отсортирован.

Это означает, что если бы вектор был отсортирован, порядок элементов был бы

 0 1 2 3 4 5 6 7 8 9 
    ^--- begin()   2
 

Вы попросили иметь 3-й по величине элемент в индексе 2 (3-я позиция), и это то, что делает алгоритм.

Кроме того, он помещает все элементы меньшего размера спереди и все элементы большего размера сзади:

!(*j < *i) (для первой версии или comp(*j, *i) == false для второй версии) выполняется для любого i в диапазоне [первый, n-й) и для любого j в диапазоне [n-й, последний).

Давайте использовать индексы, а не итераторы, тогда для любого i < 2 и для любого j > 2 это так v[i] < v[j] . Другими словами, 1 и 0 то и другое меньше, чем любой элемент в 2 3 6 7 8 5 4 9 .

Я сначала объясню свой код, прежде чем приступать к вашей проблеме

например, у меня есть такой код

 int m_array_biasa[8] {3,2,10,45,33,56,23,47};
 

и я обычно использую его, как

 std::nth_element(m_array_biasa, m_array_biasa   4, m_array_biasa   8);
 

итак, n-й элемент здесь равен 4[33], правило std::nth_element заключается в том, что число слева от n-го должно быть меньше или равно, а число справа должно быть больше n-го

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

итак, данные, которые изначально были

3,2,10,45,33,56,23,47

изменено на

2 3 10 23 33 45 47 56

мое n-е число равно 4[33], поэтому применяются вышеуказанные правила (без учета результата сортировки).

и в результате получается

3 2 10 23 33 56 45 47

обратите внимание выше, позиция 33 не изменилась, но иногда это немного сбивает с толку, например, мы меняем 33 на 1, затем результат

2 1 3 10 23 45 47 56

что здесь произошло, почему число 1 переместилось (заменено на 23), почему оно не осталось таким, как предыдущее число 33, я уже говорил , что сначала мы должны отсортировать данные (см. Сортировку выше), получается, что индекс nth[4] равен 23, затем число 1 заменяется на число 23, почему его следует заменить?, см. Правило nth_element

теперь перейдем к вашему вопросу.

 std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin()   2, v.end());
 

v. begin() содержит 9, v. begin() 2 содержит 6, помните, что nth_element сначала отсортирует его

0 1 2 3 4 5 6 7 8 9

и ваш результат таков

1 0 2 3 6 7 8 5 4 9

n-е[2] выше (в соответствии с вашим v. begin() 2)p равно 2, поэтому 2 здесь похоже на ссылку для других данных, данные до 2 должны быть меньше, чем это, и после этого должно быть больше, чем это