На пути к пониманию nth_element
Мне трудно понять, как я должен использовать std::nth_element, так как я немного ржавый
Судья говорит:
Переставляет элементы в ассортименте
[first,last)таким образом, что элемент в n-й позиции является элементом, который будет в этой позиции в отсортированной последовательности.
Я хочу взять n-й элемент подмножества вектора, поэтому я подумал сделать что-то вроде этого:
std::nth_element (v.begin()+start-0, v.begin()+nTh-1, v.begin()+end);
будет означать взять подмножество вектора v, от start, до end (эксклюзивно), а затем, воображая, что это подмножество отсортировано, расположите nTh элемент.
Кажется, что мое понимание выключено, так как этот игрушечный пример:
#include <iostream>
#include <algorithm>
#include <vector>
int main () {
std::vector<int> myvector;
// set some values:
for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::random_shuffle (myvector.begin(), myvector.end());std::nth_element (myvector.begin() + 1 - 0, myvector.begin()+5-1, myvector.begin() + 5);
std::cout << *(myvector.begin()+5-1) << std::endl;
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
печатает 9 в качестве запрошенного элемента, в то время как я ожидаю 5. Что мне не хватает, пожалуйста?
Решение
Пытаться:
std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());
вместо :
std::nth_element (myvector.begin() + 1,
myvector.begin() + 4,
myvector.begin() + 5);
Вы перетасовываете и затем звоните nth_element только для подпоследовательности. Таким образом, вы не можете узнать, каким должен быть возвращаемый элемент. Если вы делаете это для всей последовательности, то ответ 5.
Другие решения
Я хочу взять n-й элемент подмножества вектора, поэтому я подумал
делать что-то вроде этого:std :: nth_element (v.begin () + start-0, v.begin () + nTh-1, v.begin () + end);
будет означать взять подмножество вектора v, с самого начала, до
конец (исключительный), а затем воображая, что это подмножество отсортировано,
Расположите элемент nTh.
Да это правда.
Но при этом любые элементы в позициях от v [0] до v [start-1] и от v [end] до v [v.size () — 1] не будут частью перестановки nth_element, они останутся там, где они есть. Ваше начало и конец как часть nth_element () исключили эти элементы от перестановки.
Я думаю ты хочешь
std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());
который рассматривается весь вектор (1-й и 3-й аргументы для nth_element).
Это означает, что независимо от того, где random_shuffle имеет перемешанные элементы
std::random_shuffle (myvector.begin(), myvector.end());
поскольку nth_element учитывает весь вектор, 2-й аргумент для nth_element, 5-й элемент в myvector, если отсортирован, должен быть 5. Обратите внимание, что из-за способа работы nth_element предыдущие элементы будут меньше 5 (и в любом порядке) и Следующие элементы будут более 5 (и в любом порядке).