根據一些標準分割std :: vector

Question

我有一個包含一些數據的向量。我想根據一些標準將它分成常量的向量數。例如：

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是您的朋友。

---

剛注意到C++ 11標記：上面的代碼是C++ 14。對於C++ 11的兼容性，只需將我用於顯式類型的auto更改爲使用std::array<ForwardIt, 3>作爲返回類型，const std::iterator_traits<ForwardIt>::value_type&用於lambda表達式。

爲了簡潔起見，我會留下這段話，這最後一段完成了C++之前的14個人的答案。

Answer 2

更新：

可能是最STL樣方式：

特點：

1. 基於迭代器這樣的源和目標容器的選擇留給主叫

個

2. 源迭代器可以是移動-迭代器，如果需要移動分區，或保留爲正常迭代器，使複印件

3. 線性時間複雜

4. 結果（參照std::stable_partition）的穩定排序

-

#include <array> 
#include <vector> 
#include <utility> 
#include <cassert> 

using Point=std::pair<int,int>; 

// example split function - could be a function object 
extern std::size_t which_bucket(const Point&); 


template<class Iter, class OutIter, class Which> 
    auto split_n(Iter first, Iter last, 
       OutIter outfirst, std::size_t N, 
       Which&& which) 
{ 
    while (first != last) { 
    auto index = which(*first); 
    assert (index < N); 
    std::next(outfirst, index) -> push_back(*first); 
    ++ first; 
    } 
} 

template<class Iter, class OutIter, class Which> 
    auto split_to(Iter first, Iter last, 
       OutIter outfirst, OutIter outlast, 
       Which&& which) 
{ 
    return split_n(first, last, outfirst, 
        std::distance(outfirst, outlast), 
        std::forward<Which>(which)); 
} 


int main(){ 
    std::vector<Point> source; 
    std::array<std::vector<Point>, 4> dest { }; 

    split_n(source.begin(), source.end(), 
      dest.begin(), dest.size(), 
      which_bucket); 

    // or 

    split_to(source.begin(), source.end(), 
      dest.begin(), dest.end(), 
      which_bucket); 

    // or with move request: 

    split_to(std::make_move_iterator(source.begin()), 
      std::make_move_iterator(source.end()), 
      dest.begin(), dest.end(), 
      which_bucket); 
} 

另一種方式

#include <array> 
#include <vector> 
#include <utility> 

using Point=std::pair<int,int>; 

// example split function - could be a function object 
extern std::size_t which_bucket(const Point&); 


template<class Iter, class Which> 
    auto split4(Iter first, Iter last, Which&& which) 
{ 
    std::array<std::vector<Point>, 4> result {}; 
    while (first != last) { 
    result[which(*first)].push_back(*first); 
    ++first; 
    } 
    return result; 
} 

int main(){ 
    std::vector<Point> data; 

    auto results = split4(data.begin(), data.end(), which_bucket); 
} 

這裏是爲表揚矢量任何自定義分配器的另一種方式：

#include <array> 
#include <vector> 
#include <utility> 

using Point=std::pair<int,int>; 

// example split function - could be a function object 
extern std::size_t which_bucket(const Point&); 


template<class T, class A, class Which> 
    auto split4(const std::vector<T,A>& v, 
       Which&& which) 
{ 
    using vec_type = std::vector<T,A>; 
    std::array<std::vector<T,A>, 4> result { 
    vec_type(v.get_allocator()), 
    vec_type(v.get_allocator()), 
    vec_type(v.get_allocator()), 
    vec_type(v.get_allocator()) 
    }; 
    for (auto& p : v) { 
    result[which(p)].push_back(p); 
    } 
    return result; 
} 

int main(){ 
    std::vector<Point> data; 

    auto results = split4(data, which_bucket); 
}