实现类型安全的容器元素统计函数 -

题目

实现类型安全的容器元素统计函数

信息

类型：问答
难度：⭐⭐

考点

函数模板, 容器泛型编程, 类型萃取, SFINAE

快速回答

实现一个通用的统计函数 count_occurrences，要求：

接受任意标准容器和查找值作为参数
返回该值在容器中出现的次数
确保类型安全（容器元素类型与查找值类型必须匹配）
支持自定义比较逻辑（可选）

核心实现要点：

使用函数模板接受容器类型和值类型
通过 std::enable_if 约束容器类型
使用类型萃取确保元素类型兼容
通过迭代器遍历容器统计

## 解析

问题背景与要求

需要实现泛型的容器元素统计功能，要求类型安全且支持各种标准容器（vector, list, set等）。重点考察模板编程中类型约束、容器泛型处理和编译期检查的能力。

解决方案代码

#include <type_traits>
#include <iterator>

template<typename Container, typename T>
auto count_occurrences(const Container& c, const T& value) 
    -> typename std::enable_if<
        std::is_same<
            typename std::iterator_traits<typename Container::const_iterator>::value_type,
            typename std::decay<T>::type
        >::value,
        size_t
    >::type 
{
    size_t count = 0;
    for (const auto& elem : c) {
        if (elem == value) {
            ++count;
        }
    }
    return count;
}

// 支持自定义比较器的重载版本
template<typename Container, typename T, typename Comparator>
auto count_occurrences(const Container& c, const T& value, Comparator comp) 
    -> typename std::enable_if<
        std::is_same<
            typename std::iterator_traits<typename Container::const_iterator>::value_type,
            typename std::decay<T>::type
        >::value,
        size_t
    >::type 
{
    size_t count = 0;
    for (const auto& elem : c) {
        if (comp(elem, value)) {
            ++count;
        }
    }
    return count;
}

原理说明

类型安全机制：使用 std::enable_if + std::is_same 确保容器元素类型与查找值类型匹配
类型萃取：std::iterator_traits 获取容器元素类型，std::decay 消除引用/const修饰
SFINAE应用：当类型不匹配时从重载集中剔除，避免运行时错误
泛型迭代：基于范围的for循环适配所有标准容器

最佳实践

优先使用 const auto& 避免元素拷贝
通过 std::decay 处理各种值类型（左值/右值/const）
提供自定义比较器重载增强灵活性
返回 size_t 保证足够大的计数范围

常见错误

类型不匹配：未检查元素类型导致隐式转换问题
迭代器失效：在循环中修改容器（本实现使用const引用避免）
值语义误用：大型对象未使用引用传递导致性能问题
命名冲突：未限制模板范围导致匹配非容器类型

扩展知识

C++20概念：可用 requires 替代SFINAE实现更简洁的类型约束：

template<typename Container, typename T>
requires requires {
    typename Container::const_iterator;
    requires std::is_same_v<
        std::iter_value_t<typename Container::const_iterator>,
        std::decay_t<T>>;
}
size_t count_occurrences(const Container& c, const T& value) { ... }

性能优化：对有序容器（set/map）使用 equal_range 实现O(log n)复杂度
异常安全：确保比较操作不抛出异常（noexcept声明）

使用示例

#include <vector>
#include <list>
#include <set>

struct Person {
    std::string name;
    bool operator==(const Person& other) const { 
        return name == other.name; 
    }
};

int main() {
    // 正确使用示例
    std::vector<int> v{1,2,3,2};
    auto n = count_occurrences(v, 2); // 返回2

    std::set<std::string> s{"A", "B", "A"};
    auto m = count_occurrences(s, "A"); // 返回1（set自动去重）

    // 自定义类型
    std::list<Person> people{{"Alice"}, {"Bob"}, {"Alice"}};
    auto p = count_occurrences(people, Person{"Alice"});

    // 类型安全检查（编译错误）
    // count_occurrences(v, "hello"); 

    // 自定义比较器
    auto ci_compare = [](const std::string& a, const std::string& b) {
        return std::equal(a.begin(), a.end(), b.begin(), b.end(),
            [](char c1, char c2) { 
                return std::tolower(c1) == std::tolower(c2);
            });
    };
    std::vector<std::string> words{"Apple", "apple", "Orange"};
    auto ci_count = count_occurrences(words, "APPLE", ci_compare); // 返回2
}