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;
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
.
std::iota
to generate list of indexes.std::min_element
to get the smallest from the given list.
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
}
with c 20 we can use std::ranges
.
std::views::iota
to generate list of indexes.std::views::filter
for filtering out based on a mask.std::ranges::min_element
to find the smallest elements in the given range.
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
}
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;
}