程序设计范式-Week5

泛型编程

find() 函数实现

需求3 既能查数组，也能查 vector

核心目标（Request 3 的真正意图）
写一个 find() 函数，它既能查数组，也能查 vector，但函数内部完全不知道（也不关心）数据是来自数组还是 vector。

核心思想：分而治之

• 分离关注点：算法不关心数据的具体存储形式
• 统一接口：用相同的方式处理数组和 vector
• 抽象迭代：通过指针操作隐藏容器细节

改进的 find() 函数实现

template <typename ElemType>
ElemType* find(const ElemType* first, const ElemType* last, const ElemType& value) {
    // 安全检查：确保指针有效
    if (!first || !last) return 0;
    
    // 使用指针迭代：first 不断递增直到等于 last
    for (; first != last; first++) {
        // 解引用指针比较值
        if (*first == value) return first;
    }
    return 0;
}

关键改进：

1. 哨兵指针：last 指向最后一个元素的下一个位置
2. 指针解引用：用 *first 替代数组下标访问
3. 范围表示：[first, last) 半开区间

向量安全性问题

危险用法：

vector<string> svec;  // 空向量
// 以下代码在空向量时会崩溃：
find(&svec[0], &svec[svec.size()], search_value);
// &svec[0] 访问空向量的第一个元素 - 未定义行为
// &svec[svec.size()] 越界访问 - 未定义行为

安全辅助函数

template <typename ElemType>
inline ElemType* begin(const vector<ElemType>& vec) {
    return vec.empty() ? 0 : &vec[0];  // 空向量返回空指针
}

template <typename ElemType>
inline ElemType* end(const vector<ElemType>& vec) {
    // 修正：应该使用 &vec[0] + vec.size()
    return vec.empty() ? 0 : &vec[0] + vec.size();
}

完整实现

#include <vector>
#include <iostream>

using namespace std;

// 改进的查找函数实现
template <typename ElemType>
ElemType* safe_find(const ElemType* first, const ElemType* last, const ElemType& value) {
    // 安全检查：确保指针有效
    if (!first || !last) return nullptr;
    
    // 使用指针迭代：first 不断递增直到等于 last
    for (; first != last; first++) {
        // 解引用指针比较值
        if (*first == value) return const_cast<ElemType*>(first);
    }
    return nullptr;
}

// 安全的向量起始位置获取函数
template <typename ElemType>
inline ElemType* vector_begin(const vector<ElemType>& vec) {
    return vec.empty() ? nullptr : const_cast<ElemType*>(&vec[0]);
}

// 安全的向量结束位置获取函数
template <typename ElemType>
inline ElemType* vector_end(const vector<ElemType>& vec) {
    return vec.empty() ? nullptr : const_cast<ElemType*>(&vec[0]) + vec.size();
}

// 演示使用示例
int main() {
    // 测试用例1：正常向量
    vector<int> numbers = {1, 3, 5, 7, 9, 2, 4, 6, 8};
    int target = 5;
    
    int* result = safe_find(vector_begin(numbers), vector_end(numbers), target);
    if (result != nullptr) {
        cout << "找到元素 " << target << " 在位置 " << (result - vector_begin(numbers)) << endl;
    } else {
        cout << "未找到元素 " << target << endl;
    }
    
    // 测试用例2：空向量（安全处理）
    vector<string> empty_vec;
    string search_value = "test";
    
    string* empty_result = safe_find(vector_begin(empty_vec), vector_end(empty_vec), search_value);
    if (empty_result == nullptr) {
        cout << "空向量安全处理：返回空指针" << endl;
    }
    
    // 测试用例3：字符串向量
    vector<string> words = {"apple", "banana", "cherry", "date"};
    string word_target = "cherry";
    
    string* word_result = safe_find(vector_begin(words), vector_end(words), word_target);
    if (word_result != nullptr) {
        cout << "找到单词: " << *word_result << endl;
    }
    
    return 0;
}

需求4 支持 list 容器

问题：list 的内存布局不同
解决方案：迭代器抽象 (看后面迭代器类型与使用) 迭代器：封装底层指针操作的对象

• 重载 ++, *, ==, != 等操作符
• 提供统一的访问接口

迭代器类型与使用

定义：

#include <vector>
#include <list>
#include <string>

vector<string> svec;

// 不同类型的迭代器
vector<string>::iterator it;           // 普通迭代器（可读写）
vector<string>::const_iterator conit;  // 常量迭代器（只读）
vector<string>::reverse_iterator rit;  // 反向迭代器

使用：

// 遍历vector
for (vector<string>::iterator it = svec.begin(); it != svec.end(); it++) {
    cout << *it << ' ';           // 解引用访问元素
    cout << it->size() << endl;   // 通过->访问成员
}

// 遍历list（语法相同！）
list<string> slist;
for (list<string>::iterator it = slist.begin(); it != slist.end(); it++) {
    cout << *it << ' ';
}

迭代器类型兼容性

vector<int> v = {1, 2, 3};

int* p = &v[0];                    // 原生指针
vector<int>::iterator it1;         // vector迭代器
vector<int>::const_iterator it2;   // 常量迭代器
vector<string>::iterator it3;      // 不同类型迭代器
list<int>::iterator it4;           // 不同容器迭代器

// 类型兼容性测试
it1 = p;        // ⚠️ 可能工作，不安全（如果vector迭代器是指针的包装）
it1 = it2;      // ❌ 错误：const_iterator 不能赋给 iterator
it2 = it1;      // ✅ 可以：iterator 可以赋给 const_iterator
it1 = it3;      // ❌ 错误：不同类型
it1 = it4;      // ❌ 错误：不同容器

需求4完整实现

#include <vector>
#include <list>
#include <iostream>
using namespace std;

template <typename IteratorType, typename ElemType>
IteratorType find(IteratorType first, IteratorType last, const ElemType& value) {
    for (; first != last; first++) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

int main() {
    const int asize = 8;
    int ia[asize] = {1, 1, 2, 3, 5, 8, 13, 21};
    
    // 不同容器，相同初始化方式
    vector<int> ivec(ia, ia + asize);
    list<int> ilist(ia, ia + asize);
    
    // 相同find函数，不同容器
    // 1. 数组
    int* pa = find(ia, ia + asize, 13);
    if (pa != ia + asize) {
        cout << "Found in array: " << *pa << endl;
    }
    
    // 2. vector
    vector<int>::iterator it_v = find(ivec.begin(), ivec.end(), 13);
    if (it_v != ivec.end()) {
        cout << "Found in vector: " << *it_v << endl;
    }
    
    // 3. list
    list<int>::iterator it_l = find(ilist.begin(), ilist.end(), 13);
    if (it_l != ilist.end()) {
        cout << "Found in list: " << *it_l << endl;
    }
    
    return 0;
}

线性范围概念

[first, last) 半开区间

• 元素数量：last - first
• 空范围：[p, p) 是有效的空范围
• 标准表示：STL 算法的统一范围表示

向量遍历的多种方式

1. 下标风格

// 基本版本（可能有问题）
for (int i = 0; i < v.size(); ++i) {
    // 使用 v[i] 或 v.at(i)
}

// 正确版本
for (vector<T>::size_type i = 0; i < v.size(); ++i) {
    // 使用 v[i] 或 v.at(i)
}

2. 迭代器风格

for (vector<T>::iterator p = v.begin(); p != v.end(); ++p) {
    // 使用 *p
}

3. 范围 for 循环

// 明确类型
for (vector<T>::value_type x : v) {
    // 使用 x（值拷贝）
}

// 自动类型推导 + 引用（避免拷贝）
for (auto& x : v) {
    // 使用 x（引用，可修改元素）
}

// 自动类型推导 + 常量引用
for (const auto& x : v) {
    // 使用 x（只读）
}

泛型算法概述

STL 算法分类

STL 提供 70+ 独立于容器和数据类型的算法：

70+ 独立于容器和数据类型的算法：

• 搜索算法：find(), count(), adjacent_find(), find_if(), count_if(), binary_search(), find_first_of()
• 排序与排序相关：merge(), partial_sort(), partition(), random_shuffle(), reverse(), rotate(), sort()
• 复制、删除与替换：copy(), remove(), remove_if(), replace(), replace_if(), swap(), unique()
• 关系算法：equal(), includes(), mismatch()
• 生成与变换：fill(), for_each(), generate(), transform()
• 数值算法：accumulate(), adjacent_difference(), partial_sum(), inner_product()
• 集合算法：set_union(), set_difference()

简单示例：元素存在性检查

#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;

bool Have_Elem(const vector<int>& vec, int search_value) {
    // 获取最大值（注意：max_element返回迭代器）
    auto max_iter = max_element(vec.begin(), vec.end());
    if (max_iter == vec.end() || *max_iter < search_value) {    
        cout << "No enough elements" << endl;
        return false;   
    }
    
    // 复制并排序以进行二分查找
    vector<int> temp(vec.size());
    copy(vec.begin(), vec.end(), temp.begin());
    sort(temp.begin(), temp.end());
    
    return binary_search(temp.begin(), temp.end(), search_value);
}

泛型算法设计演进

需求5 支持用户自定义比较

原始版本：硬编码比较

vector<int> filter(const vector<int>& vec, int threshold) {
    vector<int> nvec;
    for (int i = 0; i < vec.size(); i++)
        if (vec[i] < threshold)  // 硬编码 < 操作
            nvec.push_back(vec[i]);
    return nvec;
}

方案一：函数指针

// 使用函数指针支持自定义比较
vector<int> filter_ver1(const vector<int>& vec, int threshold, 
                       bool (*pred)(int, int)) {
    vector<int> nvec;
    for (int i = 0; i < vec.size(); i++) {
        if (pred(vec[i], threshold)) {
            nvec.push_back(vec[i]);
        }
    }
    return nvec;
}

// 比较函数
bool less_than(int v1, int v2) {
    return v1 < v2;
}

bool greater_than(int v1, int v2) {
    return v1 > v2;
}

// 使用
vector<int> lt_10 = filter_ver1(ivec, 10, less_than);
vector<int> gt_5 = filter_ver1(ivec, 5, greater_than);

函数对象（Function Objects）

预定义函数对象

#include <functional>

// 算术函数对象
plus<int>, minus<int>, negate<int>, multiplies<int>, divides<int>, modulus<int>

// 关系函数对象  
less<int>, less_equal<int>, greater<int>, greater_equal<int>, equal_to<int>, not_equal_to<int>

// 逻辑函数对象
logical_and<int>, logical_or<int>, logical_not<int>

使用示例：

// 降序排序
sort(vec.begin(), vec.end(), greater<int>());

// 序列元素相乘
vector<int> fibon, triangle, result;
transform(fibon.begin(), fibon.end(), triangle.begin(),
          back_inserter(result), multiplies<int>());

函数对象适配器

绑定器适配器：

// 将二元函数对象转换为一元函数对象
bind1st(less<int>(), 10)    // 绑定第一个参数为10：10 < x
bind2nd(less<int>(), 10)    // 绑定第二个参数为10：x < 10

取反适配器：

not1(bind2nd(less<int>(), 10))  // 一元取反：!(x < 10) 即 x >= 10
not2(less<int>())               // 二元取反：!(x < y) 即 x >= y

方案2：函数对象 + find_if

vector<int> filter_ver2(const vector<int>& vec, int threshold, less<int> lt) {
    vector<int> nvec;
    vector<int>::const_iterator it = vec.begin();
    
    // 使用 find_if 和绑定器
    while ((it = find_if(it, vec.end(), bind2nd(lt, threshold))) != vec.end()) {
        nvec.push_back(*it);
        it++;
    }
    return nvec;
}

// 使用
vector<int> result = filter_ver2(ivec, 10, less<int>());

完全泛型版本

template<typename InputIter, typename OutputIter, 
         typename ElemType, typename Comp>
OutputIter filter(InputIter first, InputIter last, 
                  OutputIter at, const ElemType& thres, Comp pred) {
    while ((first = find_if(first, last, bind2nd(pred, thres))) != last) {
        *at++ = *first++;
    }
    return at;
}

STL 迭代器概述

迭代器核心概念

• 泛化指针：跟踪数据结构的起始、结束和其他位置
• 类对象：存储内存地址，指向容器元素
• 内置操作：提供统一的访问接口

iterator++     // 移动到下一个元素
iterator--     // 移动到上一个元素  
*iterator      // 访问迭代器指向位置的值
iterator->member // 访问成员

iostream 迭代器

需求6：从标准输入读取字符串，排序后输出

传统解决方案：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string word;
    vector<string> text;
    
    // 手动读取和存储
    while (cin >> word) {
        text.push_back(word);
    }
    
    sort(text.begin(), text.end());
    
    // 手动输出
    for (int i = 0; i < text.size(); i++) {
        cout << text[i] << endl;
    }
}

使用 iostream 迭代器：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>  // 需要包含迭代器头文件
using namespace std;

int main() {
    // 输入流迭代器
    istream_iterator<string> is(cin);     // 绑定到标准输入
    istream_iterator<string> eof;         // 结束迭代器
    
    vector<string> text;
    
    // 一行代码完成读取和存储
    copy(is, eof, back_inserter(text));
    
    sort(text.begin(), text.end());
    
    // 输出流迭代器
    ostream_iterator<string> os(cout, " ");  // 绑定到标准输出，分隔符为空格
    
    // 一行代码完成输出
    copy(text.begin(), text.end(), os);
}

文件绑定版本

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    // 绑定到文件流
    ifstream inFile("in.txt");
    ofstream outFile("out.txt");
    
    if (!inFile || !outFile) {
        cerr << "Failed to open files" << endl;
        return -1;
    }
    
    istream_iterator<string> is(inFile);  // 绑定到输入文件
    istream_iterator<string> eof;
    
    vector<string> text;
    copy(is, eof, back_inserter(text));
    sort(text.begin(), text.end());
    
    ostream_iterator<string> os(outFile, " ");  // 绑定到输出文件
    copy(text.begin(), text.end(), os);
    
    return 0;
}

迭代器适配器

问题：容器空间不足

int main() {
    int size = 8;
    int ia[size] = {12, 8, 4, 13, 65, 3, 0, 20};
    vector<int> ivec(ia, ia + size);
    
    int ia2[size];              // 数组已分配空间
    vector<int> ivec2;          // 空vector，无预分配空间
    
    // ✅ 数组有足够空间 - 正常工作
    filter(ia, ia + size, ia2, 10, less<int>());
    
    // ❌ vector 空间不足 - 运行时错误！
    filter(ivec.begin(), ivec.end(), 
           ivec2.begin(), 10, greater<int>());
}

解决方案：插入适配器

插入适配器类型：

#include <iterator>  // 需要包含适配器头文件

// 1. back_inserter - 使用 push_back()
back_inserter(container)        // 在末尾插入

// 2. inserter - 使用 insert()，指定插入位置  
inserter(container, position)   // 在指定位置插入

// 3. front_inserter - 使用 push_front()
front_inserter(container)       // 在开头插入

用法：

int main() {
    int size = 8;
    int ia[size] = {12, 8, 4, 13, 65, 3, 0, 20};
    vector<int> ivec(ia, ia + size);
    
    int ia2[size];              // 数组
    vector<int> ivec2;          // 空vector
    list<int> ilist2;           // 空list
    
    // 数组不支持插入适配器，必须预分配空间
    filter(ia, ia + size, ia2, 10, less<int>());
    
    // ✅ 使用 back_inserter - 自动扩展vector
    filter(ivec.begin(), ivec.end(), 
           back_inserter(ivec2), 10, greater<int>());
    
    // ✅ 使用 front_inserter - 适合list
    filter(ivec.begin(), ivec.end(),
           front_inserter(ilist2), 10, greater<int>());
    
    return 0;
}