Algorytm C++ podobny do "groupby" Pythona

Question

Czy są jakieś transformacje C++, które są podobne do itertools.groupby()?

Oczywiście mogłem łatwo napisać własne, ale wolę wykorzystać zachowanie idiomatyczne lub skomponować je z funkcji zapewnianych przez STL lub boost.

#include <cstdlib> 
#include <map> 
#include <algorithm> 
#include <string> 
#include <vector> 

struct foo 
{ 
     int x; 
     std::string y; 
     float z; 
}; 

bool lt_by_x(const foo &a, const foo &b) 
{ 
     return a.x < b.x; 
} 

void list_by_x(const std::vector<foo> &foos, std::map<int, std::vector<foo> > &foos_by_x) 
{ 
     /* ideas..? */ 
} 

int main(int argc, const char *argv[]) 
{ 
     std::vector<foo> foos; 
     std::map<int, std::vector<foo> > foos_by_x; 

     std::vector<foo> sorted_foos; 
     std::sort(foos.begin(), foos.end(), lt_by_x); 
     list_by_x(sorted_foos, foos_by_x); 

     return EXIT_SUCCESS; 
} 

Answer 1

Jaki jest sens wzdęcia standardowej biblioteki C++ z algorytmem, który jest jednym wierszem kodu?

for (const auto & foo : foos) foos_by_x[foo.x].push_back(foo); 

Zobacz także std::multimap, może to być dokładnie to, czego potrzebujesz.

UPDATE:

Jednej-liner mam pod warunkiem nie jest dobrze zoptymalizowany dla przypadku, gdy wektor jest już posortowana. Liczba wyszukiwań map może zostać zmniejszona, jeśli pamiętamy iterator wcześniej wstawionego obiektu, więc jest to "klucz" następnego obiektu i sprawdzanie tylko wtedy, gdy klucz się zmienia. Na przykład:

#include <map> 
#include <vector> 
#include <string> 
#include <algorithm> 
#include <iostream> 

struct foo { 
    int   x; 
    std::string y; 
    float  z; 
}; 

class optimized_inserter { 
    public: 
    typedef std::map<int, std::vector<foo> > map_type; 

    optimized_inserter(map_type & map) : map(&map), it(map.end()) {} 

    void operator()(const foo & obj) { 
     typedef map_type::value_type value_type; 
     if (it != map->end() && last_x == obj.x) { 
      it->second.push_back(obj); 
      return; 
     } 
     last_x = obj.x; 
     it = map->insert(value_type(obj.x, std::vector<foo>({ obj }))).first; 
    } 

    private: 
    map_type   *map; 
    map_type::iterator it; 
    int    last_x; 
}; 

int main() 
{ 
    std::vector<foo> foos; 
    std::map<int, std::vector<foo>> foos_by_x; 

    foos.push_back({ 1, "one", 1.0 }); 
    foos.push_back({ 3, "third", 2.5 }); 
    foos.push_back({ 1, "one.. but third", 1.5 }); 
    foos.push_back({ 2, "second", 1.8 }); 
    foos.push_back({ 1, "one.. but second", 1.5 }); 

    std::sort(foos.begin(), foos.end(), [](const foo & lhs, const foo & rhs) { 
      return lhs.x < rhs.x; 
     }); 

    std::for_each(foos.begin(), foos.end(), optimized_inserter(foos_by_x)); 

    for (const auto & p : foos_by_x) { 
     std::cout << "--- " << p.first << "---\n"; 
     for (auto & f : p.second) { 
      std::cout << '\t' << f.x << " '" << f.y << "'/" << f.z << '\n'; 
     } 
    } 
} 

Answer 2

To naprawdę nie odpowiedzieć na to pytanie, ale dla zabawy, I wdrożone iterator group_by. Może ktoś uzna to za przydatne:

#include <assert.h> 
#include <iostream> 
#include <set> 
#include <sstream> 
#include <string> 
#include <vector> 

using std::cout; 
using std::cerr; 
using std::multiset; 
using std::ostringstream; 
using std::pair; 
using std::vector; 

struct Foo 
{ 
    int x; 
    std::string y; 
    float z; 
}; 

struct FooX { 
    typedef int value_type; 
    value_type operator()(const Foo &f) const { return f.x; } 
}; 



template <typename Iterator,typename KeyFunc> 
struct GroupBy { 
    typedef typename KeyFunc::value_type KeyValue; 

    struct Range { 
    Range(Iterator begin,Iterator end) 
    : iter_pair(begin,end) 
    { 
    } 

    Iterator begin() const { return iter_pair.first; } 
    Iterator end() const { return iter_pair.second; } 

    private: 
     pair<Iterator,Iterator> iter_pair; 
    }; 

    struct Group { 
    KeyValue value; 
    Range range; 

    Group(KeyValue value,Range range) 
    : value(value), range(range) 
    { 
    } 
    }; 


    struct GroupIterator { 
    typedef Group value_type; 

    GroupIterator(Iterator iter,Iterator end,KeyFunc key_func) 
    : range_begin(iter), range_end(iter), end(end), key_func(key_func) 
    { 
     advance_range_end(); 
    } 

    bool operator==(const GroupIterator &that) const 
    { 
     return range_begin==that.range_begin; 
    } 

    bool operator!=(const GroupIterator &that) const 
    { 
     return !(*this==that); 
    } 

    GroupIterator operator++() 
    { 
     range_begin = range_end; 
     advance_range_end(); 
     return *this; 
    } 

    value_type operator*() const 
    { 
     return value_type(key_func(*range_begin),Range(range_begin,range_end)); 
    } 


    private: 
     void advance_range_end() 
     { 
     if (range_end!=end) { 
      typename KeyFunc::value_type value = key_func(*range_end++); 
      while (range_end!=end && key_func(*range_end)==value) { 
      ++range_end; 
      } 
     } 
     } 

     Iterator range_begin; 
     Iterator range_end; 
     Iterator end; 
     KeyFunc key_func; 
    }; 

    GroupBy(Iterator begin_iter,Iterator end_iter,KeyFunc key_func) 
    : begin_iter(begin_iter), 
    end_iter(end_iter), 
    key_func(key_func) 
    { 
    } 

    GroupIterator begin() { return GroupIterator(begin_iter,end_iter,key_func); } 

    GroupIterator end() { return GroupIterator(end_iter,end_iter,key_func); } 

    private: 
    Iterator begin_iter; 
    Iterator end_iter; 
    KeyFunc key_func; 
}; 


template <typename Iterator,typename KeyFunc> 
inline GroupBy<Iterator,KeyFunc> 
    group_by(
    Iterator begin, 
    Iterator end, 
    const KeyFunc &key_func = KeyFunc() 
) 
{ 
    return GroupBy<Iterator,KeyFunc>(begin,end,key_func); 
} 


static void test() 
{ 
    vector<Foo> foos; 
    foos.push_back({5,"bill",2.1}); 
    foos.push_back({5,"rick",3.7}); 
    foos.push_back({3,"tom",2.5}); 
    foos.push_back({7,"joe",3.4}); 
    foos.push_back({5,"bob",7.2}); 

    ostringstream out; 

    for (auto group : group_by(foos.begin(),foos.end(),FooX())) { 
    out << group.value << ":"; 
    for (auto elem : group.range) { 
     out << " " << elem.y; 
    } 
    out << "\n"; 
    } 

    assert(out.str()== 
    "5: bill rick\n" 
    "3: tom\n" 
    "7: joe\n" 
    "5: bob\n" 
); 
} 

int main(int argc,char **argv) 
{ 
    test(); 
    return 0; 
} 

Answer 3

Niedawno odkryłem cppitertools.

Spełnia tę potrzebę dokładnie tak, jak opisano.

https://github.com/ryanhaining/cppitertools#groupby

Answer 4

Eric Niebler na ranges library zapewnia group_by pogląd.

Według dokumentów jest to biblioteka tylko dla nagłówków i można ją łatwo dołączyć.

Powinien wejść w standardową przestrzeń C++, ale może być używany z ostatnim kompilatorem C++ 11.

minimalny przykład praca:

#include <map> 
#include <vector> 
#include <range/v3/all.hpp> 
using namespace std; 
using namespace ranges; 

int main(int argc, char **argv) { 
    vector<int> l { 0,1,2,3,6,5,4,7,8,9 }; 
    ranges::v3::sort(l); 
    auto x = l | view::group_by([](int x, int y) { return x/5 == y/5; }); 
    map<int, vector<int>> res; 

    auto i = x.begin(); 
    auto e = x.end(); 
    for (;i != e; ++i) { 
     auto first = *((*i).begin()); 
     res[first/5] = to_vector(*i); 
    } 

    // res = { 0 : [0,1,2,3,4], 1: [5,6,7,8,9] } 
} 

(. I to skompilowany z brzękiem 3.9.0 i --std=c++11)