STL algorithm to find all tuples with the first element within a range
I have a list of tuples, the list is sorted by the first element of the tuple, and the second and last elements are in random order. Now I want to find all tuples with the first element inside the range, i.e. Return all tuples for ( tuple.first>-X
and tuple.first<X
). Among all the returned tuples, I need to find the maximum and minimum value in the second element of the tuples. How can the STL algorithm implement this?
source to share
Since it is already sorted, you can use equal_range
to get a couple of iterators that limit the range of "interesting" tuples:
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);
Then you can just loop over that range and log the minimum and maximum values you see:
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
So ... this is not one STL algorithm.
Note: std::min_element
and std::max_element
exist, but this means that the loop will repeat twice over the range, but it is possible.
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;
Note that it gives a tuple, not a member .second
.
source to share
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;
I guess boost :: can be replaced with std :: if you have a recent compiler (I don't).
source to share