Два условия для find_if

Question

В std::vector<unsigned int> я хочу найти позицию элемента, которая является максимальным числом, меньшим определенного числа. Например:

v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 

Я хочу, чтобы найти число, которое является максимальным меньше 8. Это число 7.

Следующий код не является правильным, но это, вероятно, что я хочу получить.

std::vector<unsigned int>::iterator pnt = std::find_if (v.begin(), v.end(), [](const unsigned int& x) { return x < 8; && x == MAX; }); 

Answer 1

Если вектор всегда отсортирован, то вы можете сделать это в логарифмической сложности

auto it = std::lower_bound(v.begin(), v.end(), 8); // first value >= 8 
auto m = *((it != v.begin())? --it : it);   

Если вектор несортированный, но может быть изменен, вы можете сделать это в 2 этапа:

auto it = std::partition(v.begin(), v.end(), [](int x) { x < 8 }); 
auto m = *(it != v.begin())? std::max_element(v.begin(), it) : it); 

Если вы не можете изменить свой вектор, вы можете сделать это вручную

auto max = 0; 
for (elem: v) { 
    if (elem < 8) 
     m = std::max(elem, m); 
} 
// m is now the max of all elements < 8 

Оба этих двух конечных подхода имеют линейную сложность. Последнее можно обобщить, используя filter_iterator из библиотеки Boost.Iterator, но затем вы уже глубоко впарите в землю шаблонов, так что делайте это только в том случае, если у вас есть повторная потребность в такой магии.

Answer 2

Я бы сделал функцию, которая проверяет наличие каких-либо значений внутри вектора, и если это не вызывает ошибку. Тогда я бы сохранил каждое значение, которое ниже максимального, но выше, чем самое высокое в настоящее время. Вот как я его реализую.

unsigned smaller_than (const std::vector<unsigned int>& v, unsigned max) { 

    bool intial_found = false; 
    unsigned largest; 
    unsigned i; 
    for (i = 0; i < v.size() ;++i){ 
     if (v [i] < max){ 
      largest = v[i]; 
      intial_found = true; 
      break; 
     } 
    } 
    if (! intial_found) { 
     throw "oops";/*of course you make a Nice std::exception for this case*/ 
    } 
    for ( ; i < v.size(); i++) { 
     if (v[i] < max && v [i] > largest){ 
      largest = v[i]; 
     } 
    } 
    return largest; 
}