Algoritmo de C++ como 'groupby' de python

Question

¿Hay alguna transformación de C++ que sea similar a itertools.groupby()?

Por supuesto, podría escribir fácilmente el mío, pero preferiría aprovechar el comportamiento idiomático o redactar uno de los rasgos proporcionados por el STL o 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

¿Cuál es el punto de inflamación de la biblioteca estándar de C++ con un algoritmo que es una línea de código?

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

También, echar un vistazo a std::multimap, podría ser justo lo que necesita.

UPDATE:

El de una sola línea que he proporcionado no está bien optimizado para el caso en su vector ya está ordenada. Se pueden reducir un número de búsquedas de mapas si recordamos el iterador del objeto previamente insertado, por lo que es la "clave" del siguiente objeto y hacemos una búsqueda solo cuando la tecla está cambiando. Por ejemplo:

#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

Esto realmente no responde a su pregunta, pero por el gusto de hacerlo, implementé un iterador group_by. Tal vez alguien le resultará útil:

#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

Recientemente he descubierto cppitertools.

Cumple con esta necesidad exactamente como se describe. de

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

Answer 4

Eric Niebler ranges library proporciona una vista group_by.

de acuerdo con los documentos, es una biblioteca de solo cabecera y se puede incluir fácilmente.

Se supone que debe entrar en el espacio estándar de C++, pero se puede usar con un compilador reciente de C++ 11.

mínima ejemplo de trabajo:

#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] } 
} 

(. Compilé esto con sonido metálico 3.9.0 y --std=c++11)