c++ - C ++算法，如python的'groupby'

Question

是否有任何类似于的 C++ 转换itertools.groupby()？

当然，我可以轻松编写自己的代码，但我更喜欢利用惯用行为或从 STL 或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;
}

score 9 · Accepted Answer

这并不能真正回答您的问题，但为了好玩，我实现了一个 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;
}

score 7 · Accepted Answer

Eric Niebler 的范围库提供了group_by视图。

根据文档，它是一个只有标题的库，可以很容易地包含在内。

它应该进入标准 C++ 空间，但可以与最近的 C++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] }
}

（我用 clang 3.9.0 编译了这个。和--std=c++11）

score 6 · Accepted Answer

我最近发现cppitertools。

它完全按照描述的方式满足了这一需求。

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

score 3 · Accepted Answer

用一行代码的算法来膨胀标准 C++ 库有什么意义？

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';
        }
    }
}

score 1 · Accepted Answer

这个怎么样？

template <typename StructType, typename FieldSelectorUnaryFn>
auto GroupBy(const std::vector<StructType>& instances, const FieldSelectorUnaryFn& fieldChooser)
{
    StructType _;
    using FieldType = decltype(fieldChooser(_));
    std::map<FieldType, std::vector<StructType>> instancesByField;
    for (auto& instance : instances)
    {
        instancesByField[fieldChooser(instance)].push_back(instance);
    }
    return instancesByField;
}

并像这样使用它：

auto itemsByX = GroupBy(items, [](const auto& item){ return item.x; });

score 1 · Accepted Answer

我编写了一个C++ 库以优雅的方式解决这个问题。鉴于你的结构

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

要按y您分组，只需执行以下操作：

std::vector<foo> dataframe;
...
auto groups = group_by(dataframe, &foo::y);

您还可以按多个变量分组：

auto groups = group_by(dataframe, &foo::y, &foo::x);

然后正常遍历组：

for(auto& [key, group]: groups)
{
    // do something
}

它还具有其他操作，例如：subset、concat 等。

score 0 · Accepted Answer

我会简单地使用boolinq.h，其中包括所有 LINQ。没有文档，但使用起来非常简单。

c++ - C ++算法，如python的'groupby'

7 回答 7

Related

Reference