CODEWITHSUNDEEP
c++stl
user1285419
user1285419

Reputation: 2225

STL algorithm to find all tuples with first element within a range

I have a list of tuple, the list was sorted based on the first element of the tuple but the second and last elements are in random order. Now I want to find all tuples with the first element within a range, i.e. return all tuples for (tuple.first>-X and tuple.first<X). Among all these returning tuples, I need to find the maximum and minimum value in the second element of the tuples. How can a STL algorithm implement this?

Upvotes: 3

Views: 1800

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299999

Since it is already sorted, you can use equal_range to get a pair of iterators that delimit 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 simply iterate over this range, and register the minimum and maximum values that 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... it's not a single STL algorithm.

Note: std::min_element and std::max_element do exist, but that would mean looping twice over the range, it's certainly feasible though.

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, and not the .second member.

Upvotes: 1

Ylisar
Ylisar

Reputation: 4291

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 presume boost:: can be replaced with std:: if you have a recent compiler ( I don't ).

Upvotes: 2

Related Questions