代码之家 › 专栏 › 技术社区 › WhatABeautifulWorld

创建参考向量的优雅方法

vector sorting algorithm c++

WhatABeautifulWorld · 技术社区 · 7 年前

vector<Foo> inputs

Foo是一个结构,里面有一些分数

struct Foo {
    ...
    float score
    bool winner
}

现在我想按分数对输入进行排序,只把优胜者分配给前三名,但我不想改变原来的输入向量。所以我想我需要创建一个参考向量然后排序?创建参考向量合法吗?有没有优雅的方法?

5 回复 | 直到 7 年前

Pezo 7 年前

如果您真的不想修改原始向量,那么您必须将指针或索引的向量排序到原始向量中。要回答你的部分问题,不,没有办法建立一个参考向量,你不应该这样做。

n std::nth_element (或 std::partial_sort 如果您关心顶部元素的顺序,您可以这样做:

void modify_top_n(std::vector<Foo> &v, int n) {
    std::vector<Foo*> tmp(v.size());
    std::transform(v.begin(), v.end(), tmp.begin(), [](Foo &f) { return &f; });

    std::nth_element(tmp.begin(), tmp.begin() + n, tmp.end(),
        [](const Foo* f1, const Foo *f2) { return f1->score > f2->score; });
    std::for_each(tmp.begin(), tmp.begin() + n, [](Foo *f) {
        f->winner = true;
    });
}

N 条目。我曾经 for_each 只是因为有迭代器范围更容易,所以也可以使用for循环(或 for_each_n 正如Christophe提到的,如果你有C++17)。

Christophe 7 年前

这里有两种不同的方法 vector<Foo*>

vector<Foo*> foor; 
for (auto& x:inputs)
   foor.push_back(&x);

vector<Foo*> foob(inputs.size(),nullptr); 
transform(inputs.begin(), inputs.end(), foob.begin(), [](auto&x) {return &x;});

然后可以使用标准算法 sort

// decreasing order according to score
sort(foob.begin(), foob.end(), [](Foo*a, Foo*b)->bool {return a->score>b->score;});

最后,您可以使用 for_each_n() 算法(如果是C++17)或简单的普通循环。

Online demo

Baum mit Augen 7 年前

给出的唯一示例代码是指针,IMO更适合 std::reference_wrapper 只是提到了,没有说明在这种情况下如何使用它。我要把它修好!

非所有者指针至少有3个缺点:

& , * ,和 -> 在代码中使用它们;
const ),在重载分辨率或转换等方面做一些事情-这些都不是你想要的。我相信每个人都在笑着说 我决不会犯这种愚蠢的错误 但你心里知道,在一个足够长的时间里将发生。

我通常更喜欢 ,其中

只能产生对对象的引用,因此没有任何类似指针的陷阱,并且
通过隐式转换为实引用类型,避免了许多语法问题,从而最大限度地减少了运算符噪声,因为您可以调用转换(传递到函数、初始化引用、范围)- for auto –至少在我们得到提议之前 operator. 或 operator auto .get() 在其他情况下,或者如果你只是想避免这种不一致。尽管如此,我认为这些皱纹并不比指针的皱纹更严重,也不可能是永久性的,因为有各种积极的建议来美化包装器/代理类型的使用。

我建议使用这个或另一个词汇类,尤其是公开的数据。有个实验方案 observer_ptr

所以。。。接受答案中的代码可以这样重写(现在使用 #include

#include <algorithm>
#include <functional>
#include <vector>

// ...

void
modify_top_n(std::vector<Foo>& v, int const n)
{
    std::vector< std::reference_wrapper<Foo> > tmp{ v.begin(), v.end() };

    std::nth_element( tmp.begin(), tmp.begin() + n, tmp.end(),
        [](Foo const& f1, Foo const& f2){ return f1.score > f2.score; } );

    std::for_each( tmp.begin(), tmp.begin() + n,
        [](Foo& f){ f.winner = true; } );
}

这将使用range构造函数来构造 reference_wrapper 从真实的 Foo s、隐式转换为 Foo& 在lambda参数列表中,以避免 reference_wrapper.get() . -&燃气轮机;

当然,这可以概括为:分解为可重用助手函数的主要候选方法是构造 vector< reference_wrapper<Foo> > 福 ,只给一对迭代器- 福 . 但我们总是要给读者留点东西作为练习P

SergeyA 7 年前

回答关于其面值的问题:

不应有引用,不应有引用数组,

对于向量,向量元素必须是可赋值的(而引用是不可赋值的),这是禁止的。

要拥有间接对象的数组或向量,可以使用非拥有指针( std::vector<int*> ),或者,如果需要非指针访问语法,则使用包装器- std::reference_wrapper .

eerorika 7 年前

所以我想我需要创建一个参考向量然后排序?创建参考向量合法吗?

std::reference_wrapper 为此,也可以使用裸指针。

除了Christophe展示的两种方法之外,还有一种方法是transformiterator适配器,它可以用来使用 std::partial_sort_copy .

转换迭代器只是通过调用函数在赋值时转换输入来调整输出迭代器。不过,标准库中没有迭代器适配器,所以您需要自己实现一个,或者使用一个库。