c++ - 根据某些标准拆分 std::vector

Question

我有一个包含一些数据的 vector 。我想根据某些标准将其拆分为 const 个 vector 。例如:

using Point=std::pair<int,int>;
std::array<std::vector<Point>,4> split_to_4(const std::vector<Point>& data,std::function<size_t(Point)> criteria);
int main(){
    std::vector<Point> data;
    //fill data
    auto results=split_to_4(data,[](const Point& p){
        if(cond1) return 0;
        if(cond2) return 1;
        if(cond3) return 2;
        return 3;
    });
}

实现 split_to_4 的最佳方法是什么？我目前的尝试是:

std::array<std::vector<Point>,4> split_to_4(const std::vector<Point>& data,std::function<size_t(Point)> criteria){
    std::array<std::vector<Point>,4> result;
    for (const auto& p : data){
        areas_regions[criteria(p)].emplace_back(p);
    }
    return result;
}

有更好的..更多 std 方法吗？

更好，我的意思是:更具可读性...取决于迭代器...取决于某些标准函数...

Answer 1

您可以多次调用 std::partition 来执行此操作:

// Returns iterators to the three partition points in the range
template<class ForwardIt, class Which>
auto split4(ForwardIt first, ForwardIt last, Which which) {
    std::array<ForwardIt, 3> ret;
    ret[0] = std::partition(first, last, 
                [&](const auto &v){return which(v) == 0;});
    ret[1] = std::partition(ret[0], last, 
                [&](const auto &v){return which(v) == 1;});
    ret[2] = std::partition(ret[1], last,
                [&](const auto &v){return which(v) == 2;});
    return ret;
}

当然你也可以直接传递和使用条件而不是通过一些which代理。如果您愿意，可以发挥作用。

也可以用一个循环简单地重写它以将其泛化为 splitN如有必要。 (不过请注意，对于具有 n 个元素的范围，此方法的复杂度为 O(N * n)。对于大 N，这可能会慢得不合理。另一方面，我们得到的是交换而不是拷贝，如果复制是昂贵的(与调用 which 相比)。如果性能很关键，请衡量。)

如果您需要保留每个组中元素的相对顺序， std::stable_partition 是你的 friend 。

---

刚注意到C++11标签:上面的代码是C++14的。对于 C++11 兼容性，只需更改 auto s 我习惯于显式类型，即使用 std::array<ForwardIt, 3>作为返回类型和 const std::iterator_traits<ForwardIt>::value_type&对于 lambda。

为简洁起见，我将保留原样，最后一段为 C++14 之前的人们完成了答案。