C++11 使用boost::coroutine2 有栈协程实现

因为本机没有安装 g++ 9.x，所以不具备开启C++20的功能。而《Design Patterns in Modern C++》一书中却有一个使用协程编写二叉树迭代器的示例。如果你是C++20的编译器，建议直接使用标准库的std::generator类，比这个清晰，高效，大致写法如下，

image.png

怎么样，是不是又骚又靓丽。

如果你跟我一样，只能使用12年以前的C++11编译器，例如g++ 7.x，那么下面这篇文章是一个可行的替代方案。

还有一个方案是使用boost的outcome库，但是对boost版本要求比较高，得一个一个试，放弃了。你要知道我平时用的多的两个库是OpenCV和boost，boost动了，OpenCV可能不兼容，所以尽量不要干这种事儿，太恶心了。[其中boost::outcome库的实现方案和std差不多，直接换下名称空间就行了，非常直观，这里就不废话了]

本次方案使用boost::coroutines2::coroutine的push_type和pull_type实现。兼容C++11以上版本。

conanfile.txt

[requires]
boost/1.72.0
opencv/4.5.3



[generators]
cmake

CMakeLists.txt

cmake_minimum_required(VERSION 3.3)

project(90_binary_tree_iterator_coroutine)

set(ENV{PKG_CONFIG_PATH} "$ENV{PKG_CONFIG_PATH}:/usr/local/lib/pkgconfig/")

set ( CMAKE_CXX_FLAGS "-pthread")
set(CMAKE_CXX_STANDARD 17)
add_definitions(-g)
set(${CMAKE_BINARY_DIR} ${CMake_CURRENT_SOURCE_DIR}/build)


include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake)
conan_basic_setup()



include_directories(${INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRS})

file( GLOB main_file_list ${CMAKE_CURRENT_SOURCE_DIR}/*_test.cpp) 
file( GLOB sources ${CMAKE_CURRENT_SOURCE_DIR}/*.cc)

foreach( main_file ${main_file_list} )
    file(RELATIVE_PATH filename ${CMAKE_CURRENT_SOURCE_DIR} ${main_file})
    string(REPLACE ".cpp" "" file ${filename})
    add_executable(${file}  ${main_file} ${sources})
    target_link_libraries(${file} PRIVATE  pthread)
    target_link_libraries(${file} PRIVATE  ${CONAN_LIBS})


endforeach( main_file ${main_file_list})

binary_tree_iterator_coroutine.hpp

#ifndef _FREDIRC_BINARY_TREE_ITERATOR_COROUTINE_HPP_
#define _FREDIRC_BINARY_TREE_ITERATOR_COROUTINE_HPP_

#include <boost/coroutine2/all.hpp>
#include <string>

template <typename T>
using coroutine = boost::coroutines2::coroutine<T>;

template <typename T>
struct BinaryTree;

template <typename T>
struct Node {
    T value {};

    Node<T>* left{nullptr}, *right{nullptr}, *parent{nullptr};

    BinaryTree<T>* tree{nullptr};

    Node(T value_): value(value_) {}

    Node(T value_, Node<T>* left_, Node<T>* right_):
        value(value_), left(left_), right(right_) {
        // 初始化左子节点和右子节点的树为同一棵树
        this->left->tree = this->right->tree = tree;
        // 初始化左子节点和右子节点的父节点为当前节点
        this->left->parent = this->right->parent = this; 
    }

    void setTree(BinaryTree<T>* t) {
        tree = t;
        if(left) left->tree = t;
        if(right) right->tree = t;
    }
    
    ~Node() {
        if(left) delete left;
        if(right) delete right;
    }
};


template <typename T>
struct BinaryTree {
    
    Node<T>* root {nullptr};

    BinaryTree(Node<T>* root_):
        root(root_) {
            root->setTree(this);
        }
    
    ~BinaryTree() {
        if(root) {
            delete root;
        }
    }

   
};

template <class T>
void post_order(typename coroutine<Node<T>*>::push_type& sink, Node<T>* node) { 
    if(node->left) {    
        post_order<T>(sink, node->left); 
    }   
    if(node->right) { 
        post_order<T>(sink, node->right); 
    } 
    sink(node); 
} 

using cort_string_node = coroutine<Node<std::string>*>;

#endif

oop_test.cpp

#include <iostream>
#include <string>
#include <sstream>
#include "log.h"
#include <utility>
#include <memory>
#include <cstring>
#include <vector>
#include <iterator>
#include "binary_tree_iterator_coroutine.hpp"

#define BOOST_TEST_MODULE BinaryTreeIteratorCoRoutine
#include "test.hpp"


BOOST_AUTO_TEST_SUITE(Suite01, *fixture<SuiteSetUp>())

BOOST_AUTO_TEST_CASE(BinaryTreeIteratorCoRoutineTest) {
    BinaryTree<std::string> family (
        new Node<std::string>("me",        
        new Node<std::string>("Mother",
            new Node<std::string>("Mother's mother"),
            new Node<std::string>("Mother's father")),
        new Node<std::string>("father"))
    );

    cort_string_node::pull_type source([&](cort_string_node::push_type& sink){
        post_order<std::string>(sink, family.root);
    });

    for(auto const& node: source) {
        std::cout << node->value << std::endl;
    }
}

BOOST_AUTO_TEST_SUITE_END()

上面代码要注意的一个地方是post_order第一个参数的前面要加个typename，这8个字母一个字母一块钱，坑得很。原因是模板参数里面带有多个命名空间限定的话，还外带这种 <T>参数的话，编译器默认不认定为模板，会触发编译错误。

程序输出如下，

image.png