सी ++ एल्गोरिदम जैसे पायथन 'ग्रुपबी'

Question

क्या कोई सी ++ रूपांतरण है जो itertools.groupby() के समान हैं?

बेशक मैं आसानी से अपना खुद का लिख ​​सकता हूं, लेकिन मैं मूर्खतापूर्ण व्यवहार का लाभ उठाना चाहता हूं या एसटीएल या 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

एक एल्गोरिथ्म है कि कोड की एक पंक्ति है के साथ मानक सी ++ पुस्तकालय सूजन की बात क्या है?

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

इसके अलावा, std::multimap पर एक नज़र डालें, यह हो सकता है आप बस क्या जरूरत है।

अद्यतन:

एक लाइनर मैं मामले के लिए अच्छी तरह से अनुकूल नहीं है जब आपके वेक्टर पहले से ही क्रमबद्ध किया जाता है प्रदान की है। अगर हम पहले डाले गए ऑब्जेक्ट के इटरेटर को याद करते हैं तो कई मानचित्र लुकअप को कम किया जा सकता है, इसलिए यह अगली ऑब्जेक्ट की "कुंजी" है और जब कुंजी बदल रही है तो केवल एक लुकअप करें। उदाहरण के लिए:

#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

यह वास्तव में आपके प्रश्न का उत्तर नहीं है, लेकिन मनोरंजन के लिए, मैं एक group_by इटरेटर कार्यान्वित किया। हो सकता है कि किसी को यह उपयोगी मिल जाएगा:

#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

मैं हाल ही में खोजे cppitertools।

यह वर्णन की गई बिल्कुल इस आवश्यकता को पूरा करता है।

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

Answer 4

एरिक Niebler के ranges library एक group_by दृश्य प्रदान करता है।

दस्तावेज़ों के अनुसार यह केवल एक शीर्षलेख है और इसे आसानी से शामिल किया जा सकता है।

इसे मानक सी ++ स्पेस में जाना है, लेकिन हाल ही में सी ++ 11 कंपाइलर के साथ इसका उपयोग किया जा सकता है।

न्यूनतम काम कर उदाहरण:

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

(। मैं बजना 3.9.0 के साथ इस संकलित और --std=c++11)