Splitting std :: vector on some criteria

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 способ сделать это?

По Лучше, я имею в виду: более читаемым ... зависит от итератора ... зависит от некоторых функций 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, если необходимо. (Остерегайтесь, однако, сложность этого подхода O (N * n) для диапазона с n элементами. Вероятно, это будет неоправданно медленным для больших N. С другой стороны, мы получаем свопы вместо копий, что может помочь, если копирование дорого (по сравнению с вызовом which). Если производительность критическая, измерьте.)

Если вам нужен относительный порядок элементов в каждой сохраненной группе, std::stable_partition - твой друг.

---

Только что заметил тег C++ 11: приведенный выше код является C++ 14. Для совместимости с C++ 11 просто измените значение auto s, которое я использовал для явных типов, т. Е.используйте std::array<ForwardIt, 3> в качестве возвращаемого типа и const std::iterator_traits<ForwardIt>::value_type& для лямбда.

Я оставлю это, как для краткости, этот последний абзац завершает ответ для людей до 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); 
}