Алгоритм STL для поиска всех кортежей с первым элементом в диапазоне

Question

У меня есть список кортежей, список отсортирован по первому элементу кортежа, но второй и последний элементы расположены в случайном порядке. Теперь я хочу найти все кортежи с первым элементом в пределах диапазона, то есть вернуть все кортежи для (tuple.first>-X и tuple.first<X). Среди всех этих возвращаемых кортежей мне нужно найти максимальное и минимальное значение во втором элементе кортежей. Как алгоритм STL может реализовать это?

Answer 1

ListType::iterator itrFirst = std::find_if( ls.begin(), ls.end(), boost::bind( &TupleType::get< 0 >, _1 ) >= rangeStart );
ListType::iterator itrLast = std::find_if( itrFirst, ls.end(), boost::bind( &TupleType::get< 0 >, _1 ) > rangeEnd );
for( ;itrFirst != itrLast; ++itrFirst ) // Print keys for elements in range
    std::cout << itrFirst->get<0>() << std::endl;

Я предполагаю, что boost :: может быть заменен на std ::, если у вас есть последний компилятор (у меня нет).

Answer 2

Поскольку он уже отсортирован, вы можете использовать equal_range, чтобы получить пару итераторов, которые разграничивают диапазон «интересных» кортежей:

It const begin = std::lower_bound(list.begin(), list.end(),
                                  [X](Tuple const& t) {
                                      return t.first > -X;
                                  });

It const end = std::upper_bound(begin, list.end(),
                                [X](Tuple const& t) {
                                    return t.first < X;
                                });

std::pair<It,It> const range = std::make_range(begin, end);

Затем вы можете просто выполнить итерацию по этому диапазону и зарегистрировать минимальное и максимальное значения, которые вы видите:

int min = INT_MAX, max = INT_MIN;

for (Tuple const& t: range) {
  if (t.second < min) { min = t.second; }
  if (t.second > max) { max = t.second; }
}

// min and max are correctly set

Итак ... это не единственный алгоритм STL.

Примечание: std::min_element и std::max_element действительно существуют, но это будет означать повторение цикла дважды по диапазону, хотя это, безусловно, возможно. Tuple const& min = *std::min_element(range.first, range.second, [](Tuple const& left, Tuple const& right) { return left.second < right.second; }); Tuple const& max = *std::max_element(range.first, range.second, [](Tuple const& left, Tuple const& right) { return left.second < right.second; }); // Or as noted by Vitali, slightly more efficient: auto const minmax = std::minmax_element(range.first, range.second, [](Tuple const& left, Tuple const& right) { return left.second < right.second; }); Tuple const& min = *minmax.first; Tuple const& max = *minmax.second; Обратите внимание, что он дает кортеж, а не член .second.