从对象列表中获取具有特定成员值的所有对象

Question

来自向量

std::vector<S> structures;

包含

类型的结构

struct S {
    double x;
    double y;
    double weight;
};

我想重复获取所有具有特定权重的结构，即我想执行以下伪代码：

do 1000 times:
   weight = GetASpecificWeight()
   MatchingStructures = structures.GetAllStructuresWithWeight(weight)

为了有效地做到这一点，我想对 structures 向量进行排序并在每次迭代中进行二进制搜索。

如何使用 std:: 代码实现它？

Answer 1

可以使用 std::sort and finding the range of elements that have the specified weight can be done with std::equal_range.

对矢量进行排序

然而，正如丹尼尔在评论中指出的那样，getASpecificWeight() returns 可能是双倍而不是 Structure，因此为了调用 equal_range我们需要创建一个虚拟的 Structure 或一个函数对象来比较 double 和 Structures 与所需的语义。单个 lambda 不起作用，因为二进制搜索需要能够比较 Structures 和两种方式的权重。

备选方案 1：使用虚拟结构

首先，让我们创建一个虚拟对象 Structure，因为这样代码更少。

总的来说，它可能看起来像这样

auto sort_structure_by_weight_asc = [](Structure const& s1, Structure const& s2) {
    return s1.weight < s2.weight;
};

std::sort(structures.begin(), structures.end(),
          sort_structure_by_weight_asc);

for (auto i = 0; i < 1000; ++i) {
    auto weight = GetASpecificWeight();
  
    auto const dummy_structure = Strucutre{0.0, 0.0, weight};  
    auto range = std::equal_range(structures.cbegin(), structures.cend(),
                                  dummy_structure, sort_structure_by_weight_asc);

    if (range.first != structures.cend() && range.second != structures.cbegin()) {
       // do whatever you want here
       // if the `if`-condition isn't satisfied, no structure
       // had weight `weight`.
    }
}

如果您需要修改structures向量中的元素，您可以在对std::equal_range和[=28=的调用中替换cbegin和cend ]-条件分别为begin/end。

备选方案 2：手工制作的函数对象

但是，我个人认为创建虚拟结构不是很干净，所以让我们看看自定义函数对象如何改进代码。

函数对象本身可以定义为

struct ComparatorStructureToWeightAsc {
    bool operator()(Structure const& s, double weight) const {
        return s.weight < weight;
    }

    bool operator()(double weight, Structure const& s) const {
        return weight < s.weight;
    }
};

那么代码将如下所示：

std::sort(structures.begin(), structures.end(),
          [](auto const& s1, auto const& s2) { return s1.weight < s2.weight; });

for (auto i = 0; i < 1000; ++i) {
    auto weight = GetASpecificWeight();
   
    auto range = std::equal_range(structures.cbegin(), structures.cend(),
                                  weight, ComparatorStructureToWeightAsc);

    if (range.first != structures.cend() && range.second != structures.cbegin()) {
       // do whatever you want here
       // if the `if`-condition isn't satisfied, no structure
       // had weight `weight`.
    }
}

备选方案 3：使用 Boost。Functional/OverloadedFunction

如您所见，我不擅长命名事物，因此必须命名用于比较结构和权重的函数对象有点尴尬，特别是如果它仅用于这个地方。如果您可以访问 Boost，特别是 Boost.Functional/OverloadedFunction，您可以使用两个 lambda 表达式而不是手工制作的函数对象。

代码如下所示：

std::sort(structures.begin(), structures.end(),
          [](auto const& s1, auto const& s2) { return s1.weight < s2.weight; });

for (auto i = 0; i < 1000; ++i) {
    auto weight = GetASpecificWeight();
   
    auto range = std::equal_range(structures.cbegin(), structures.cend(), weight, 
                                  boost::make_overloaded_function(
                                    [](Structure const& s, double weight) { return s.weight < weight; },
                                    [](double weight, Structure const& s) { return weight < s.weight; }));

    if (range.first != structures.cend() && range.second != structures.cbegin()) {
       // do whatever you want here
       // if the `if`-condition isn't satisfied, no structure
       // had weight `weight`.
    }
}

从对象列表中获取具有特定成员值的所有对象

Get all objects with a specific member value from a list of objects

c++

sorting

search

std

备选方案 1：使用虚拟结构

备选方案 2：手工制作的函数对象

备选方案 3：使用 Boost。Functional/OverloadedFunction