Home > Enterprise >  Find position of min element of a "masked vector"
Find position of min element of a "masked vector"

Time:12-02

I have a vector of some values and a mask vector of 0's and 1's. For example:

std::vector<int>   mask{0,   0,   1,   0,   1,   1,   0};
std::vector<double> vec{7.1, 1.0, 3.2, 2.0, 1.8, 5.0, 0.0};

and I need to find the min element (its index) in vec but only where mask is 1. In this example it is 1.8 at index 4.

Here's my solution using a loop

double minVal = std::numeric_limits<double>::max();
int minIndex;
for (size_t i = 0; i < vec.size();   i)
{
    if (vec[i] < minVal && mask[i] == 1)
    {
        minVal = vec[i];
        minIndex = i;
    }
}

But I was wondering if there is a way to do it by using the standard library (e.g. std::min_element and lambdas), ideally without using the for-loop?

CodePudding user response:

You can transform into a combined vector, using max double as a replacement for masked values, and use that with std::min_element

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

int main()
{
    std::vector<bool> mask{0,   0,   1,   0,   1,   1,   0};
    std::vector<double> vec{7.1, 1.0, 3.2, 2.0, 1.8, 5.0, 0.0};
    std::vector<double> combined;
    
    std::transform(vec.begin(), vec.end(), mask.begin(),
                   std::back_inserter(combined),
                   [](double v, bool mask) {
                       return mask ? v : std::numeric_limits<double>::max(); });
    
    auto it = std::min_element(combined.begin(), combined.end());
    std::cout << "min=" << *it << "\n";
    return 0;
}

See https://ideone.com/FncV2r for a live example.


Getting the index is fairly easy using std::distance

std::cout << "index=" << std::distance(combined.begin(), it) << "\n";

And applying this to the original vector would be

auto index = std::distance(combined.begin(), it);
auto it_vec = vec.begin()   index;

See https://ideone.com/U8AXtm


Keep in mind, that even though this solution uses std algorithms and a lambda, the questioner's simple for loop is more efficient.

This is because the for loop doesn't need extra space (the combined vector), and finishes in a single run, whereas transform and min_element take two turns to produce the same result.

So occasionally, there's a time for "old-fashioned" loops.

CodePudding user response:

You can make a helper class that'll combine those vectors into a single vector of structs to make it easy to use min_element:

template <typename T>
class Masker {
private:
    template <typename V>
    struct Item {
        bool mask;
        V val;
    };
    std::vector<Item<T>> vec;
public:
    Masker(std::vector<bool> mask, std::vector<T> vals) {
        for(size_t i = 0; i < vals.size(); i  ) {
            vec.push_back({mask[i], vals[i]});
        }
    }
    const T& find_min() {
        return (*min_element(vec.begin(), vec.end(),
            [](const auto& lhs, const auto& rhs){ 
                if(!lhs.mask) { return false; }
                if(!rhs.mask) { return true; }
                return lhs.val < rhs.val;
            })).val;
    }
};

And then call it like:

std::cout << Masker<double>(mask, vec).find_min();

Live example: https://ideone.com/G6ymGH

CodePudding user response:

You can create an index vector using std::iota. Then use std::min_element.

int main() {
  std::vector<int> mask{0, 0, 1, 0, 1, 1, 0};
  std::vector<double> vec{7.1, 1.0, 3.2, 2.0, 1.8, 5.0, 0.0};
  std::vector<decltype(vec)::size_type> idx(vec.size());
  std::iota(idx.begin(), idx.end(), 0);

  auto idxmin =
      std::min_element(idx.begin(), idx.end(), [&mask, &vec](auto i, auto j) {
        auto max_v = std::numeric_limits<double>::max();
        auto v  = mask[i] ? vec[i] : max_v;
        auto v2 = mask[j] ? vec[j] : max_v;
        return v < v2;
      });

  std::cout << vec[*idxmin] << " at index " << *idxmin; // 1.8 at index 4
}

Demo

with we can use std::ranges.

int main() {
  std::vector<int> mask{0, 0, 1, 0, 1, 1, 0};
  std::vector<double> vec{7.1, 1.0, 3.2, 2.0, 1.8, 5.0, 0.0};
  auto idx = std::views::iota(0lu, vec.size()) |
             std::views::filter([&mask](auto i) { return mask[i] == 1; });
  auto idxmin = std::ranges::min_element(
      idx, [&vec](auto i, auto j) { return vec[i] < vec[j]; });

  std::cout << vec[*idxmin] << " at index " << *idxmin; // 1.8 at index 4
}

Demo

CodePudding user response:

This is yet another pair of approaches : hand code a loop, or create an intermediate datastructure for use in std::min_element.

#include <utility>
#include <algorithm>
#include <stdexcept>
#include <vector>
#include <limits>
#include <iostream>

struct entry_t
{
    entry_t(std::size_t i, int m, double v) :
        index{i},
        mask{m},
        value{v}
    {
    }
    
    std::size_t index;
    int mask;
    double value;
};

auto combine(const std::vector<int>& mask, const std::vector<double>& values)
{
    if (mask.size() != values.size()) throw std::invalid_argument("vector sizes don't match");
    
    std::vector<entry_t> entries;

    for (std::size_t n = 0; n < values.size();   n)
    {
        entries.emplace_back(n, mask[n], values[n]);
    }
    
    return entries;
}


auto find_masked_min_index(const std::vector<int>& mask, const std::vector<double>& values)
{
    if (mask.size() != values.size()) throw std::invalid_argument("vector sizes don't match");

    double min = std::numeric_limits<double>::max();
    std::size_t index = 0;

    for (std::size_t n = 0; n < values.size();   n)
    {
        if ((mask[n] == 1) && (values[n] < min))
        {
            index = n;
            min = values[n];
        }
    }

    return index;
}

int main()
{
    std::vector<int>   mask{ 0,   0,   1,   0,   1,   1,   0 };
    std::vector<double> vec{ 7.1, 1.0, 3.2, 2.0, 1.8, 5.0, 0.0 };

    // method one, hand coded
    auto index = find_masked_min_index(mask, vec);
    std::cout << "Minimum is at index : " << index << ", value = " << vec[index] << "\n";

    // method two, create a combined datastructure 
    auto combined = combine(mask, vec);

    // use std::min_element
    auto it = std::min_element(combined.begin(), combined.end(), [](const auto& lhs, const auto& rhs)
    {
        return ((lhs.mask == 1) && (lhs.value < rhs.value));
    });

    std::cout << "Minimum is at index : " << it->index << ", value = " << it->value << "\n";

    return 0;
}
  • Related