logo标签列表

寻找“掩码向量”中最小元素的位置。

c++vector
3
我有一个数值向量和一个由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和lambda表达式）来完成，最好不要使用for循环？

就单次调用而言，使用算法和迭代并检查需要检查的内容之间没有实质性的效率差异。 - Kenny Ostrom
1
我需要...那你尝试了什么？它是如何失败的？请提供您最好的尝试的 [mre]。您至少能够在忽略掩码的情况下找到最小值吗？ - Yunnosch
2
@infinitezero -- 但是这样你将失去原始向量中项目的索引，我相信OP正在请求它。 - PaulMcKenzie
1
感谢您重新开启，并对一开始可能不够清晰表示歉意。 - orbit
@PepijnKramer 问题已经重新开放。请随意发表回答。 - Ch3steR
显示剩余7条评论
4个回答
5
您可以将其转化为一个组合向量，使用最大双替换掩码值，并将其与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循环不需要额外的空间（即合并后的向量），而且可以在单次运行中完成，而transform和min_element则需要两次运行才能产生相同的结果。

因此，有时候还是需要使用“老派”的循环。

1
啊，使用 int max 的 transform 很聪明。绝对比我的回答更简洁/更好。这也会在整个掩码关闭的情况下返回 int max。 - scohe001
提问者的简单for循环更有效率，而且我还要补充说它更易读。不过还是谢谢你的回答，很有意思！ - orbit
2
你可以创建一个辅助类，将这些向量组合成结构体的单个向量，以便于使用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();

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

1
您可以使用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
}

演示

使用，我们可以使用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
}

演示

0
这是另一种方法：手动编写循环，或者创建一个中间数据结构供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;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接