Может кто-нибудь объяснить, почему lower_bound работает таким образом?

Question

Функция lower_bound в C ++ возвращает указатель на первый элемент массива, который как минимум равен x (третий аргумент, переданный функции). Вот код, который я скомпилировал онлайн с помощью онлайн-компилятора для C ++.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(1);
    v.push_back(2);
    cout<<lower_bound(v.begin(),v.end(),2)-v.begin()<<endl;
    return 0;
}

Результат, который я ожидал, был 1, но фактический результат говорит 3. Кто-нибудь может объяснить, почему это так?

Answer 1

Диапазон [first, last) должен быть секционирован относительно выражения element

https://en.cppreference.com/w/cpp/algorithm/lower_bound

Ваш ввод не удовлетворяет этому требованию (не отсортирован), поэтому вывод не определен .

Answer 2

https://en.cppreference.com/w/cpp/algorithm/lower_bound

Диапазон [first, last) должен быть секционирован относительно выражения element < value или comp(element, value), т. Е. Всех элементов, для которых это выражение "истина" должно предшествовать всем элементам, для которых выражение является ложным. Полностью отсортированный диапазон соответствует этому критерию.

Этот порядок:

v.push_back(1);
v.push_back(2);
v.push_back(1);
v.push_back(2);

не соответствует этому критерию.

Answer 3

std :: lower_bound

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

std::sort (v.begin(), v.end()); важно, список номеров должен быть в порядке возрастания.