[数据结构与算法]函数式编程（一）查询容器内元素

函数式编程（一）查询容器内元素

参照《函数式编程C++》这本书内容，同时很推荐该书，要有c++17及以上的基础。

总体来说，就是讲解如何通过函数方式，实现查询容器内元素的功能。

首先，可以通过输入filterfunction，查询到容器内符合filter条件的容器元素。

template <typename FilterFunction>  // 定义filter模板
std::vector<std::string> names_for(
		const std::vector<person_t> &people,
		FilterFunction filter)
{
	std::vector<std::string> result;

	for (const person_t& person: people) {  // 循环遍历符合条件的元素
		if (filter(person)) {
			result.push_back(name(person));
		}
	}

	return result; // 返回结果容器
}

然而，这种操作必然会产生内存的消耗，过程中拷贝复制，需要优化。

于是，采用了一个递归调用的方式来实现。

template <typename T>
T tail(const T &collection) {  
    return T(collection.cbegin() + 1, collection.cend());  // 返回容器下一个元素
}
template <typename T, typename C>
C prepend(T &&item, C collection) {
    C result(collection.size() + 1);
    result[0] = std::forward<T>(item);  // 右值转移
    std::copy(collection.cbegin(), collection.cend(), result.begin() + 1);
    return result;
}
template <typename FilterFunction>  // 定义filter模板
std::vector<std::string> names_for(
        const std::vector<person_t> &people,
        FilterFunction filter)
{
    if (people.empty()) {
        return {};

    } else {
        const auto head = people.front();
        const auto processed_tail = names_for(  // 递归调用，tail为移动到容器下一个元素
                tail(people),
                filter);

        if (filter(head)) {
            return prepend(name(head), processed_tail); // prepend，将元素插入到结果容器中
        } else {
            return processed_tail; 
        }
    }
}

然而，这种递归在其函数的调用开销会很大，在容器体量较大时，有堆栈溢出的风险，

于是，采用尾递归调用方式，即递归后不做任何处理，将中间需要创建结果容器的步骤移除。

template <typename FilterFunction, typename Iterator>  // 定义filter模板
std::vector<std::string> names_for_helper(
        Iterator people_begin,
        Iterator people_end,
        FilterFunction filter,
        std::vector<std::string> previously_collected)  // 追加了结果集参数，这样不需要每次获取结果集
{
    if (people_begin == people_end) {	// 递归结束
        return previously_collected;
    } else {
        const auto head = *people_begin;
        if (filter(head)) {
            previously_collected.push_back(name(head));
            
        }
		return names_for_helper(	// 直接操作容器
                    people_begin + 1,
                    people_end,
                    filter,
                    previously_collected);
    }
}

附：

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <fstream>
#include <algorithm>
#include <iterator>

#include "person.h"

//#define USE_RECURSIVE_IMPLEMENTATION
#define USE_TAIL_RECURSIVE_IMPLEMENTATION

std::string name(const person_t &person)
{
    return person.name();
}

bool is_female(const person_t &person)
{
    return person.gender() == person_t::female;
}

bool is_not_female(const person_t &person)
{
    return !is_female(person);
}

template <typename T>
T tail(const T &collection)
{
    return T(collection.cbegin() + 1, collection.cend());
}

template <typename T, typename C>
C prepend(T &&item, C collection)
{
    C result(collection.size() + 1);
    result[0] = std::forward<T>(item);
    std::copy(collection.cbegin(), collection.cend(), result.begin() + 1);
    return result;
}

#ifdef USE_RECURSIVE_IMPLEMENTATION
template <typename FilterFunction>
std::vector<std::string> names_for(
        const std::vector<person_t> &people,
        FilterFunction filter)
{
    if (people.empty()) {
        return {};

    } else {
        const auto head = people.front();
        const auto processed_tail = names_for(
                tail(people),
                filter);

        if (filter(head)) {
            return prepend(name(head), processed_tail);
        } else {
            return processed_tail;
        }
    }
}
#else
template <typename FilterFunction>
std::vector<std::string> names_for(
		const std::vector<person_t> &people,
		FilterFunction filter)
{
	std::vector<std::string> result;

	for (const person_t& person: people) {
		if (filter(person)) {
			result.push_back(name(person));
		}
	}

	return result;
}
#endif

#ifdef USE_TAIL_RECURSIVE_IMPLEMENTATION
template <typename FilterFunction, typename Iterator>
std::vector<std::string> names_for_helper(
        Iterator people_begin,
        Iterator people_end,
        FilterFunction filter,
        std::vector<std::string> previously_collected)
{
    if (people_begin == people_end) {
        return previously_collected;

    } else {
        const auto head = *people_begin;

        if (filter(head)) {
            previously_collected.push_back(name(head));
            
        }
		return names_for_helper(
                    people_begin + 1,
                    people_end,
                    filter,
                    previously_collected);

    }
}

template <typename FilterFunction, typename Iterator>
std::vector<std::string> names_for(
        Iterator people_begin,
        Iterator people_end,
        FilterFunction filter)
{
        return names_for_helper(people_begin,
                                people_end,
                                filter,
                                {});
}
#endif

int main(int argc, char *argv[])
{
	std::cout << "Hello world!" << std::endl;
	    std::vector<person_t> people {
        { "David"  , person_t::male   },
        { "Jane"   , person_t::female },
        { "Martha" , person_t::female },
        { "Peter"  , person_t::male   },
        { "Rose"   , person_t::female },
        { "Tom"    , person_t::male   }
    };
#ifdef USE_TAIL_RECURSIVE_IMPLEMENTATION
	auto names = names_for(people.begin(), people.end(), is_female);
#else
	auto names = names_for(people, is_female);
#endif
    
    for (const auto& name: names) {
        std::cout << name << '\n';
    }

	return 0;
}