Home > database >  How to get maximum element in a vector that belongs to a range?
How to get maximum element in a vector that belongs to a range?

Time:09-16

Although there is an explicit for loop solution for the same, I was looking for a solution to get the max in a vector in a given range.

E.g. let's say a vector has 3,5,7,9,5,1,6,7,4,2 and the given range is [4,8] then the max element should be 7.

I was looking for a one liner/short solution using some inbuilt std library functions for the same.

The array contains all positive numbers.

This is what I have tried :

int max = -1;
for (i = 0; i < n; i  )
    if (arr[i] > max && arr[i] >= low && arr[i] <= high)
        max = arr[i];

I am just looking for a simple standard library vector solution.

CodePudding user response:

Not always it pays off to squeeze too much in a single line, or to use algorithms always, especially when the loop is clear and readable. Anyhow, if you like you can use std::accumulate. The binary operation is rather close to your original code, I just used the conditional operator instead of an if:

auto x = std::accumulate(arr.begin(),arr.end(),-1,[high,low](int accu,int elem){
    return (elem > accu && elem >= low && elem <= high ) ? elem : accu;
});

Live Demo

CodePudding user response:

Similar to @Yksisarvinen's answer, but using std::tuple's < to shorten it.

This has a precondition that there is at least one element within range in the input.

#include <cassert>
#include <algorithm>
#include <tuple>
#include <vector>

int main() {
    std::vector<int> arr {3,5,7,9,5,1,6,7,4,2};
    int lowerLimit = 4;
    int upperLimit = 8;
    
    auto inRange = [lowerLimit, upperLimit](int value)
    {
        return value >= lowerLimit && value <= upperLimit;
    };
    auto compare = [inRange](int lhs, int rhs) {
        return std::tuple(inRange(lhs), lhs) < std::tuple(inRange(rhs), rhs);
    };
    
    assert(!arr.empty());
    assert(std::any_of(arr.begin(), arr.end(), inRange));
    auto it = std::max_element(arr.begin(), arr.end(), compare);
    int max = *it;
}

CodePudding user response:

This is far from being a one liner (unless you consider helper functions to not be part of the code, then it sure is one line), but if you really want to use standard algorithms, you need a comparison function that will conform to strict weak ordering.

bool inRange(int value, int lowerLimit, int upperLimit)
{
    return value >= lowerLimit && value <= upperLimit;
}

std::vector<int> arr {3,5,7,9,5,1,6,7,4,2};
    
int lowerLimit = 4;
int upperLimit = 8;
auto compare = [lowerLimit, upperLimit](int l, int r){
    if(inRange(l, lowerLimit, upperLimit) && inRange(r, lowerLimit, upperLimit)) {
        // both values are in range, so compare them
        return l < r;
    } else if (inRange(r, lowerLimit, upperLimit)) {
        // r is in range, l is not, l should compare smaller
        return true;
    } else if (inRange(l, lowerLimit, upperLimit)) {
        // l is in range, r is not, r should compare smaller
        return false;
    } else {
        // both are out of range, compare them normally to keep strict weak ordering requirements
        return l < r;
    }
};

auto maxIter = std::max_element(std::begin(arr), std::end(arr), compare);
std::cout << "Max value is " << *maxIter;

CodePudding user response:

While others have shown feasible solutions using standard algorithms, I would like to suggest one similar to std::max_element implementation. Here, you will get more flexibility what to do, when you provide a non-valid range to the algorithm function.

#include <iterator> std::iterator_traits

template<typename Iterator>
using EleType = typename std::iterator_traits<Iterator>::value_type;

template< class Iterator>
auto my_max_element(Iterator first, const Iterator last,
    EleType<Iterator> minValue, EleType<Iterator> maxValue)
{
    Iterator largest = first;
    for (; first != last;   first)
        if (minValue <= *first && *first <= maxValue && *largest < *first)
            largest = first;
    // final range check for the largest element
    return (minValue <= *largest && *largest <= maxValue) ? largest : last;
}

(See a Live Demo)

CodePudding user response:

Here's one that utilizes the two standard lib functions std::sort and std::find_first_of:

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

// Find max element of sample vector within range of val_range.
using namespace std;

int main()
{
    vector<int> sample = { 3,5,7,9,5,1,6,7,4,2 };
    vector<int> val_range = { 4,8 };

    // Sort in reverse order
    sort(sample.begin(), sample.end(), greater<int>());
    vector<int>::iterator it = find_first_of(sample.begin(), sample.end(), val_range.begin(), val_range.end(), [](int value, int max_val) {return value <= max_val;} );
    cout << (*it) << endl;
}

See Live Demo

  • Related