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

2022-01-24 00:00:00 containers c++ c++11 stl boost

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

Are there any C++ transformations which are similar to itertools.groupby()?

当然，我可以轻松编写自己的代码，但我更喜欢利用惯用行为，或者从 STL 或 boost 提供的功能中组合一个.

Of course I could easily write my own, but I'd prefer to leverage the idiomatic behavior or compose one from the features provided by the STL or 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;
}

推荐答案

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

What is the point of bloating standard C++ library with an algorithm that is one line of code?

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

另外，看看 std::multimap，它可能正是你所需要的.

Also, take a look at std::multimap, it might be just what you need.

更新:

当你的向量已经排序时，我提供的单行没有很好地优化.如果我们记住先前插入对象的迭代器，则可以减少许多映射查找，因此它是下一个对象的键"，并且仅在键更改时才进行查找.例如:

The one-liner I have provided is not well-optimized for the case when your vector is already sorted. A number of map lookups can be reduced if we remember the iterator of previously inserted object, so it the "key" of the next object and do a lookup only when the key is changing. For example:

#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 << "---
";
        for (auto & f : p.second) {
            std::cout << '	' << f.x << " '" << f.y << "' / " << f.z << '
';
        }
    }
}

相关文章