优雅地同时遍历多个容器

问:给定容器 C1, C2, C3, … Cn, 且已知 size(C1) == size(C2) == … == size(Cn);
如何优雅地

      for (c1, c2, c3... cn) in (C1, C2, C3, ... Cn):
        // do something

意义:可能会有两个同样大小的变长容器(vector 啊 list 啊 map 啊 blabla),确认是同样大小了,希望对其中索引相同的元素做某些事情,这种需求不属于最常见的一类,但属于一般都会遇到的一类。

答:
为了直观感受 “不优雅”, “丑陋的”,展示一下现有条件下可能的实现:

    C1_T::iterator iter1 = C1.begin();
    C2_T::iterator iter2 = C2.begin();
    ...
    Cn_T::iterator itern = Cn.begin();

    for (; iter1 != C1.end(); ++iter1, ++iter2, ++iter3, ... ++itern) {
      // do something
    }

这是 C++03 的实现。简直丑得丧心病狂。另一种方法是使用索引:

    for (int i = 0; i < C1.size(); ++i) {
      // do something
    }

这个就要求 Cx 实现 [] 操作符,而 Container Concept 并不要求实现者实现 operator [],
事实上把该方法把容器限制在了 vector,array,bitset 等内从而不具有通用性。

C++11 和 14 目前没有找到可能的更好看的实现。

当然 stackoverflow 上推荐 boost 的
zip_iterator。那个确实挺优雅的,但我们要自己搞。

关于优雅的定义,那个 for … in 的代码就很优雅。当然我觉得,
iterate(fun_do_something, C1, C2, ... , Cn) 在 C++ 这样的限制条件下也是很优雅的。
前一种做法需要把 (C1, … Cn) 包装成 某种东西,其 begin 和 end (c++11 的 range based
for
要求用户实现 begin 和 end 如果有人不知道的话) 能返回 tuple(最好是
tuple),那么就可以写成如下形式:

    std::for_each(make_enumerable(C1, C2, ... Cn), [&](auto c1, auto c2, ... auto cn) {
      // do something
    });

这里的 for_each 需要 C++1z 的支持(这个叫 uniform for_each)。所以现阶段下,只能写成:

    auto e = make_enumerable(C1, C2, ... Cn)

    std::for_each(begin(e), end(e), [&]( ... ) {
      // do something
    });

这里的 make_enumerable 也是现实里没有的,必须读者自己实现。


以上和本文主旨几乎没有关系。

下面要讲的是另一种的优雅及其实现:

    iterate([&](auto c1, auto c2, ... auto cn) {
      // do something
    }, C1, C2, ... Cn);

首先给出原型:

    template <class F, class CF, class ... C>
    void iterate(F f, CF&& first, C&& ... c);

CF 表示 First Container,我们用这个 容器做 iter != end 的判断。
C … 表示余下的容器,

然后是用法:

    int a[] = {1, 2, 3, 4, 5};
    std::vector<int> b = {2, 4, 6, 8, 10};
    std::array<int, 5> = {1, 3, 5, 7, 9};

    iterate(std::plus<int>(), a, b);

    iterate([](int _1, int _2, int _3) {
      std::cout << _1+_2+_3 << std::endl;
    }, a, b, c);

经过和我妹子讨论,解决方法一共提出三种。并且也会说明,思维定势将如何使人变成傻逼。
首先,作为一个搞了一段时间元编程的较有经验的选手,我的思路是这样的:

  1. 要存 iterator,因为要对 iterator 做 ++ 操作
  2. 由 1) 得,该操作必须在运行期进行,因此,必须使用 std::tuple 存储 iterator. 因为大家基本都是这么写的。std::bind 也是这么存着变量的。并且 std::tuple 是粘合编译期和运行期的利器。
  3. 必须将 tuple 的元素展开成 f 里的参数。即: std::tuple< int, int > param, f(param)是不对的,要把 param 展开成 f(get<0>(param), get<1>(param));
  4. 以上,写一个 tuple to function parameter 的函数。

所以得到实现如下:

    template <class F, class ... T>
    void invoke_and_advance(F f, T& ... t) {
        f(*(t++)...);
    }

    template <int idx>
    struct iterate_unpack_impl {
        template <class F, class Tp, class ... Unpack>
        void operator() (F f, Tp& tp, Unpack& ... args) {
            iterate_unpack_impl<idx-1>()(f, tp, get<idx>(tp), args...);
        }
    };

    template <>
    struct iterate_unpack_impl<0> {
        template <class F, class Tp, class ... Unpack>
        void operator() (F f, Tp& tp, Unpack& ... args) {
            invoke_and_advance(f, get<0>(tp), args...);
        }
    };

    template <class F, class Tp>
    void iterate_unpack(F f, Tp& tp) {
        iterate_unpack_impl<tuple_size<Tp>::value-1>()(f, tp);
    }

    template <class F, class CF, class ... C>
    void iterate(F f, CF&& first, C&& ... c) {
        auto ifirst = begin(first);
        auto tp = make_tuple(begin(first), begin(c)...);

        while (ifirst++ != end(first)) {
            iterate_unpack(f, tp);
        }
    }

解释一下元编程基本技巧:tuple 元素展开成 function 里面的参数。

这个在标准库和 boost 里有广泛的应用。特点是看似函数很多,内联一下消失个一干二净。

原理是通过一个

  func(Tuple<Args...> tp, Extracted_Args ... args);

然后通过给 func 特化 tuple 的索引,拉出这次需要 extract 的参数。而这次弄出来的参数又会成为 args… 里的一员,传入到下一次调用中。

在上面也就是:

    template <int idx>
    struct iterate_unpack_impl {
        template <class F, class Tp, class ... Unpack>
        void operator() (F f, Tp& tp, Unpack& ... args);
    }

这里的 idx 就是 get(tuple) 中的索引,后面跟着已经拉出来的参数。
这样的实现又臭又长,显得特别装逼不让人看懂。

顺便注意一下 iterate 原型里的 完美转发。也可以是 const T&, 但这样的话就不能对 元素做操作了。同理我也没用 cbegin 和 cend。

我妹的实现如下:

    template <class F, class IterFirst, class ... Iter>
    void invoke_and_advance(F f, IterFirst first, IterFirst last, Iter ... iter) {
        if (first != last) {
            f(*first, *iter++ ...);
            invoke_and_advance(f, ++first, last, ++iter...);
        }
    }

    template <class F, class CFirst, class ... Container>
    void iterate(F f, CFirst&& fc, Container&& ... c) {
        invoke_and_advance(f, begin(fc), end(fc), begin(c)...);
    }

乍看一下是有问题的,递归,自己调自己,基本上是不让编译器做优化了。在不开 O 的时候的测试也证明,在 vector 的大小到 10w+ 的时候,就会爆调用栈。
可是我没考虑到的是,这里是尾递归,开完 O2 照样内联个一干二净,最后的汇编码和我的实现相比只差了两行。

第三个实现,致命一击:

    template <class F, class IterFirst, class ... Iter>
    void invoke_and_advance(F f, IterFirst first, IterFirst last, Iter ... iter) {
        while (first != last) {
            f(*(first++), *(iter++) ...);
        }
    }

    template <class F, class CFirst, class ... Container>
    void iterate(F f, CFirst&& fc, Container&& ... c) {
        invoke_and_advance(f, begin(fc), end(fc), begin(c)...);
    }

应该是最优雅的实现了。

以上的教训是,不要形成思维定势一样的想法,什么什么问题用什么什么手段解,元编程本身就又臭又长,如果不取点巧的话简直是没法看了。


另:我能想到的以上代码存在的问题:
1. 为了使 f 符合 callable 的定义,应该使用 invoke(f, c1, c2, …); 这样的调用。当然 invoke 还没进标准。。。
2. 返回值应该能推导。
3. *iter++ 带来的可能的性能损失。这个感觉会优化掉。没看过汇编,不知道。不懂

另,基于 C++03 这样的落后语言的情况下,手法只能是 预处理元编程生成 iterate 的 参数 1~50 的函数族,从而把整份代码隐藏在一片一片的 PP 之中了吧。

如果有 03 的限制条件下优雅漂亮的写法,求指教~

One thought on “优雅地同时遍历多个容器

Leave a Reply

Your email address will not be published. Required fields are marked *