查找 "masked vector" 的最小元素的位置

Question

我有一个包含一些值的向量和一个包含 0 和 1 的掩码向量。例如：

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};

并且我需要在 vec 中找到最小元素（它的索引），但仅在 mask 为 1 的位置。在本例中，它在索引 4 处为 1.8。

这是我使用循环的解决方案

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;
    }
}

但我想知道是否有一种方法可以通过使用标准库（例如 std::min_element 和 lambdas）来实现，最好不使用 for 循环？

Answer 1

您可以创建一个助手 class，它将这些向量组合成一个结构向量，以便于使用 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;
    }
};

然后这样称呼它：

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

实例：https://ideone.com/G6ymGH

Answer 2

您可以转换为组合 vector，使用 max double 替换掩码值，并将其与 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;
}

查看 https://ideone.com/FncV2r 示例。

使用 std::distance

获取索引相当容易

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

并将其应用于原始向量将是

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

见https://ideone.com/U8AXtm

请记住，即使此解决方案使用标准算法和 lambda，提问者的简单 for 循环更有效。

这是因为 for 循环不需要额外的 space（组合向量），并且在单个运行中完成，而 transform 和 min_element轮流两次产生相同的结果。

所以偶尔会有“老式”循环的时候。

Answer 3

您可以使用 std::iota 创建索引向量。然后使用 std::min_element.

std::iota 生成索引列表。
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

和c++20 we can use std::ranges.

std::views::iota 生成索引列表。
std::views::filter 用于根据掩码进行过滤。
std::ranges::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};
  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

Answer 4

这是另一对方法：手动编写循环代码，或创建用于 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;
}

查找 "masked vector" 的最小元素的位置

Find position of min element of a "masked vector"

c++

vector