На пути к пониманию nth_element

Question

Мне трудно понять, как я должен использовать 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. Что мне не хватает, пожалуйста?

Answer 1

Я хочу взять 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 (и в любом порядке).

Answer 2

Попробуйте:

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 .