面试题：C++ SFINAE 与模板元编程的深度优化及泛化应用

Question

设计一个通用的C++模板库，利用SFINAE和模板元编程技术实现类型安全的异构容器（heterogeneous container）。这个容器需要支持高效的元素插入、删除和访问操作，并且要在编译期根据插入元素的类型决定合适的数据存储策略（例如，对于小型POD类型使用栈上存储，对于大型复杂类型使用堆上存储）。同时，利用SFINAE实现容器对不同迭代器类型的自适应遍历操作，要求尽可能优化性能并保持代码的通用性和可扩展性。请提供完整的模板类和相关函数的实现代码，并解释关键部分的设计思路和SFINAE的具体应用。

Answer 1

#include <type_traits>
#include <memory>
#include <iostream>
#include <vector>

// 用于存储小型POD类型的栈上存储结构
template <typename T, size_t N>
struct StackStorage {
    T data[N];
    size_t size = 0;

    void push(const T& value) {
        if (size < N) {
            data[size++] = value;
        }
    }

    void pop() {
        if (size > 0) {
            --size;
        }
    }

    T& operator[](size_t index) {
        return data[index];
    }

    const T& operator[](size_t index) const {
        return data[index];
    }
};

// 用于存储大型复杂类型的堆上存储结构
template <typename T>
struct HeapStorage {
    std::vector<T> data;

    void push(const T& value) {
        data.push_back(value);
    }

    void pop() {
        if (!data.empty()) {
            data.pop_back();
        }
    }

    T& operator[](size_t index) {
        return data[index];
    }

    const T& operator[](size_t index) const {
        return data[index];
    }
};

// 根据类型选择存储策略的模板
template <typename T>
struct StorageSelector {
    using type = std::conditional_t<
        std::is_pod<T>::value && sizeof(T) <= 16,
        StackStorage<T, 10>,
        HeapStorage<T>
    >;
};

// 异构容器模板类
template <typename... Ts>
class HeterogeneousContainer {
private:
    template <typename T, typename = void>
    struct EnableIfIterable {
        static const bool value = false;
    };

    template <typename T>
    struct EnableIfIterable<T, std::void_t<decltype(std::begin(std::declval<T>())), decltype(std::end(std::declval<T>()))>> {
        static const bool value = true;
    };

    template <typename T>
    using EnableIfIterable_t = std::enable_if_t<EnableIfIterable<T>::value>;

    template <typename T, typename = void>
    struct IteratorTraits {
        using type = void;
    };

    template <typename T>
    struct IteratorTraits<T, std::void_t<decltype(std::begin(std::declval<T>()))>> {
        using type = decltype(std::begin(std::declval<T>()));
    };

    template <typename T>
    using IteratorTraits_t = typename IteratorTraits<T>::type;

    template <size_t I, typename Func, typename... Args>
    auto visit_helper(Func&& func, Args&&... args) {
        if constexpr (I < sizeof...(Ts)) {
            using T = std::tuple_element_t<I, std::tuple<Ts...>>;
            auto& storage = std::get<StorageSelector<T>::type>(storages);
            for (size_t j = 0; j < storage.size; ++j) {
                auto result = std::invoke(func, storage[j], std::forward<Args>(args)...);
                if (result) return result;
            }
            return visit_helper<I + 1>(std::forward<Func>(func), std::forward<Args>(args)...);
        } else {
            return std::optional<>();
        }
    }

    template <typename T, typename Func, typename... Args>
    auto visit_type_helper(Func&& func, Args&&... args) {
        for (size_t i = 0; i < sizeof...(Ts); ++i) {
            if constexpr (std::is_same_v<std::tuple_element_t<i, std::tuple<Ts...>>, T>) {
                auto& storage = std::get<StorageSelector<T>::type>(storages);
                for (size_t j = 0; j < storage.size; ++j) {
                    auto result = std::invoke(func, storage[j], std::forward<Args>(args)...);
                    if (result) return result;
                }
            }
        }
        return std::optional<>();
    }

    std::tuple<typename StorageSelector<Ts>::type...> storages;

public:
    // 插入元素
    template <typename T>
    void insert(const T& value) {
        using Storage = typename StorageSelector<T>::type;
        std::get<Storage>(storages).push(value);
    }

    // 删除元素
    template <typename T>
    void remove(const T& value) {
        using Storage = typename StorageSelector<T>::type;
        auto& storage = std::get<Storage>(storages);
        for (size_t i = 0; i < storage.size; ++i) {
            if (storage[i] == value) {
                storage[i] = storage[storage.size - 1];
                storage.pop();
                break;
            }
        }
    }

    // 访问元素
    template <typename Func, typename... Args>
    auto visit(Func&& func, Args&&... args) {
        return visit_helper<0>(std::forward<Func>(func), std::forward<Args>(args)...);
    }

    template <typename T, typename Func, typename... Args>
    auto visit_type(Func&& func, Args&&... args) {
        return visit_type_helper<T>(std::forward<Func>(func), std::forward<Args>(args)...);
    }

    // 自适应遍历操作
    template <typename Iter, typename Func, typename = EnableIfIterable_t<Iter>>
    void traverse(Iter iter, Func&& func) {
        using IT = IteratorTraits_t<Iter>;
        for (IT it = std::begin(iter); it != std::end(iter); ++it) {
            visit([&func, &it](auto& value) {
                if constexpr (std::is_same_v<std::decay_t<decltype(value)>, std::decay_t<decltype(*it)>>) {
                    func(value, *it);
                }
            });
        }
    }
};

关键部分设计思路

1. 存储策略选择：

   • 使用std::conditional_t和std::is_pod以及sizeof(T)来判断类型是否为小型POD类型。如果是，则使用StackStorage在栈上存储；否则使用HeapStorage在堆上存储。
   • StorageSelector模板类根据类型T选择合适的存储策略。

2. 异构容器实现：

   • HeterogeneousContainer模板类使用std::tuple来存储不同类型的元素，每个元素的存储结构由StorageSelector确定。
   • insert函数根据元素类型选择合适的存储结构并插入元素。
   • remove函数根据元素类型找到对应的存储结构并删除元素。
   • visit函数使用模板递归和std::invoke对容器中的所有元素应用给定的函数对象，并返回第一个非空的结果。visit_type函数则只对特定类型的元素应用函数对象。

3. 自适应遍历操作：

   • 使用SFINAE技术通过EnableIfIterable模板类来判断迭代器类型是否可迭代。只有可迭代的类型才能调用traverse函数。
   • traverse函数利用IteratorTraits获取迭代器类型，并遍历迭代器，同时使用visit函数对容器中与迭代器元素类型相同的元素应用给定的函数对象。

SFINAE的具体应用

1. 判断类型是否可迭代：

   • EnableIfIterable模板类利用std::void_t和decltype检查类型是否有std::begin和std::end成员函数，以此判断类型是否可迭代。只有可迭代的类型才能通过SFINAE约束，使得traverse函数在编译期只对可迭代类型实例化。

2. 获取迭代器类型：

   • IteratorTraits模板类利用std::void_t和decltype获取迭代器类型。这使得traverse函数能够在编译期获取迭代器类型，以便进行遍历操作。