程序设计范式-Week4

泛型编程

泛型编程核心思想

基本思想

• 数据结构和数据类型分离
• 数据结构和算法分离
• 算法和数据类型分离

为什么需要泛型编程？

• 避免为每种数据类型重复编写相同算法
• 提高代码复用性和可维护性
• 提升抽象层次，源代码成为模式

STL 支持泛型编程

两大组成部分

// 容器 - 基础数据结构
vector<int>, list<double>, map<string, int>, set<char>

// 泛型算法 - 常用操作
find(), sort(), merge(), transform()

三大解耦机制

1. 容器：数据类型与数据结构解耦

list<int> intList;      // 相同数据结构，不同数据类型
list<double> doubleList;

2. 迭代器：数据结构与算法解耦

sort(vec.begin(), vec.end());    // 同一算法适用于不同容器
sort(list.begin(), list.end());

3. 函数模板：算法与数据类型解耦

template <typename ElemType>
bool binary_search(const vector<ElemType>&, ElemType&);
// 同一算法适用于不同数据类型

核心优势

一次编写，多处使用：

• 编写一个泛型函数
• 适用于任何兼容的数据类型
• 编译时生成特定版本，保证性能

容器分类概览

两大容器类型

• 顺序容器：vector, list, deque
• 关联容器：map, set, multimap, multiset

通用操作

所有容器都支持：

==, !=, =, empty(), size(), begin(), end(), insert(), erase(), clear()

顺序容器详解

顺序容器性能特征对比

容器	内存结构	随机访问	尾部操作	中间插入/删除	头部操作
vector	连续内存	高（O(1)）	高（O(1) amortized）	低（O(n)）	低（O(n)）
deque	分段连续内存	高（O(1)）	高（O(1)）	低（O(n)）	高（O(1)）
list	双向链表	低（不支持，需遍历）	高（O(1)）	高（O(1)，已知位置）	高（O(1)）

选择策略

vector vs deque：

// 栈场景 - 选 vector
vector<int> stack;
stack.push_back(1);  // 高效
stack.pop_back();

// 队列场景 - 选 deque  
deque<int> queue;
queue.push_back(1);  // 两端操作都高效
queue.push_front(2);
queue.pop_front();

deque vs list：

// 需要随机访问 - 选 deque
deque<int> dq;
dq[5] = 10;  // 支持随机访问

// 需要频繁中间插入 - 选 list
list<int> lst;
auto it = lst.begin();
advance(it, 5);
lst.insert(it, 10);  // 中间插入高效

重要成员函数

构造与初始化：

list<string> slist;                    // 空容器
list<string> slist(1024);              // 指定大小，默认值
list<string> slist(1024, "Hi");        // 指定大小和值

int arr[6] = {1,2,3,4,5,6};
list<int> ilist(arr, arr+6);           // 迭代器范围初始化

list<string> slist2(slist1);           // 拷贝构造

插入操作：

// 四种 insert 重载
iterator insert(iterator position);                    // 插入默认值
iterator insert(iterator position, ElemType value);    // 插入指定值
void insert(iterator position, int count, ElemType value); // 插入多个值
void insert(iterator1 position, iterator2 first, iterator2 last); // 插入范围

删除操作：

iterator erase(iterator position);                    // 删除单个元素
iterator erase(iterator first, iterator last);        // 删除范围

注意： list 迭代器不支持偏移算术（如 it + 5）

关联容器详解

核心概念

map/multimap：

• 存储键值对 pair<key, value>
• 内部使用搜索树，高效查找
• map：键唯一；multimap：键可重复

set/multiset：

• 只存储键
• set：键唯一；multiset：键可重复

使用示例

基本操作：

#include <map>
#include <string>

map<string, int> wordCount;                  // 定义
map<string, int>::iterator it;               // 迭代器

// 访问元素
it = wordCount.begin();
cout << it->first << "---" << it->second;    // 键---值

// 插入/更新
wordCount["hello"] = 1;                      // 存在则更新，不存在则插入

安全查找：

// 危险方式 - 可能意外插入
if (1 != wordCount["hello"]) { /* ... */ }   // 如果不存在会插入！

// 安全方式 - 使用 find
it = wordCount.find("hello");
if (it != wordCount.end()) {                 // 找到元素
    cout << it->second;
}

// 或使用 count
int cnt = wordCount.count("hello");
if (0 != cnt) {                             // 存在至少一个
    // 处理找到的元素
}

关键要点总结

容器选择决策树

1. 需要随机访问？ → 选 vector 或 deque
2. 需要频繁两端操作？ → 选 deque
3. 需要频繁中间插入删除？ → 选 list
4. 需要键值映射？ → 选 map/multimap
5. 只需要唯一键集合？ → 选 set/multiset

find() 函数实现

需求1：整数版本的 find()

int* find(vector<int>& vec, int iValue) {
    for (int iX = 0; iX < vec.size(); iX++) {
        if (vec[iX] == iValue) {
            return &vec[iX];//返回指针
        }
    }
    return nullptr;
}

使用：

int main(){
    vector<int> numbers = {1, 3, 5, 7, 9};
    int* result = find(numbers, 1);
    if (result != nullptr) {
        cout << "Found: " << *result << endl;
    } else {
        cout << "Not found" << endl;
    }
}

需求2：泛型版本的 find()

// 模板版本的 find 函数
// T 可以是任何支持 operator== 的类型
template<typename T>
T* find(vector<T>& vec, const T& value) {
    for (size_t i = 0; i < vec.size(); ++i) {
        if (vec[i] == value) {
            return &vec[i];//返回指针
        }
    }
    return nullptr;
}

使用（不限类型）：

int main() {
    // 测试 int 类型
    vector<int> numbers = {1, 3, 5, 7, 9};
    int* result1 = find(numbers, 5);
    if (result1 != nullptr) {
        cout << "Found int: " << *result1 << endl;  // 输出: Found int: 5
    }

    // 测试 string 类型
    vector<string> words = {"apple", "banana", "cherry"};
    string* result2 = find(words, string("banana"));
    if (result2 != nullptr) {
        cout << "Found string: " << *result2 << endl;  // 输出: Found string: banana
    }

    // 测试 double 类型
    vector<double> prices = {1.99, 2.50, 3.75};
    double* result3 = find(prices, 2.50);
    if (result3 != nullptr) {
        cout << "Found double: " << *result3 << endl;  // 输出: Found double: 2.5
    }

    // 测试未找到的情况
    int* result4 = find(numbers, 100);
    if (result4 == nullptr) {
        cout << "100 not found!" << endl;
    }

    return 0;
}

需求3：支持数组容器

// ✅ 通用 find 函数：适用于任何连续内存（数组、vector.data()、普通指针等）
// 参数：指向首元素的指针，元素个数，要查找的值
template<typename T>
T* find(T* begin, size_t count, const T& value) {
    for (size_t i = 0; i < count; ++i) {
        if (begin[i] == value) {
            return &begin[i];  // 返回指向匹配元素的指针
        }
    }
    return nullptr;
}

// ✅ 为 std::vector 提供便捷重载（保持原来的调用方式）
template<typename T>
T* find(vector<T>& vec, const T& value) {
    return find(vec.data(), vec.size(), value);
}

使用：

int main() {
    // ===== 测试 std::vector =====
    vector<int> numbers = {1, 3, 5, 7, 9};
    int* result1 = find(numbers, 5);
    if (result1) {
        cout << "Found in vector: " << *result1 << endl;
    }

    // ===== 测试普通数组（C-style array）=====
    int arr[] = {10, 20, 30, 40, 50};
    size_t arr_size = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度

    int* result2 = find(arr, arr_size, 30);  // 直接传数组名（退化为指针）
    if (result2) {
        cout << "Found in array: " << *result2 << endl;
    }

    // ===== 测试字符串数组 =====
    string str_arr[] = {"cat", "dog", "bird"};
    size_t str_arr_size = sizeof(str_arr) / sizeof(str_arr[0]);
    
    string* result3 = find(str_arr, str_arr_size, string("dog"));
    if (result3) {
        cout << "Found in string array: " << *result3 << endl;
    }

    // ===== 测试未找到 =====
    int* result4 = find(arr, arr_size, 999);
    if (!result4) {
        cout << "999 not found in array!" << endl;
    }

    return 0;
}