算法的泛化过程

算法的泛化过程

• 传统做法：写一个针对某种特定容器的算法，例如在 array 中查找特定值。
• 缺点：算法过于依赖容器实现细节（如数组大小 arraysize），无法复用。

基础版本：array 专用 find

int* find(int* arrayHead, int arraySize, int value) {
    for (int i = 0; i < arraySize; ++i)
        if (arrayHead[i] == value)
            break;
    return &(arrayHead[i]);
}

• 返回找到的元素位置指针，或“最后元素的下一位置（end）”以表示未找到。
• 注意：这里的 end 概念比 nullptr 更通用，因为它能推广到其他容器。

改进：区间式 find

int* find(int* begin, int* end, int value) {
    while (begin != end && *begin != value)
        ++begin;
    return begin;
}

• 在区间 [begin, end) 内查找 value。
• 更抽象：不依赖容器大小，只要有起始指针和结束指针。

int ia[7] = {0,1,2,3,4,5,6};
int* end = ia + 7;
int* ip = find(ia, end, 4);

if (ip == end) cout << "not found\n";
else cout << "found: " << *ip << endl;

泛型化：模板版本

template<typename T>
T* find(T* begin, T* end, const T& value) {
    while (begin != end && *begin != value)
        ++begin;
    return begin;
}

• value 使用 const 引用传递，避免对象过大时的复制成本。
• 适用于任意类型的数组，只要满足以下操作：
  1. != 比较
  2. * 解引用
  3. ++ 前置递增
  4. 可复制（作为返回值）

再抽象：迭代器版本

仅依赖“指针式行为”的对象即可：

template<class Iterator, class T>
Iterator find(Iterator begin, Iterator end, const T& value) {
    while (begin != end && *begin != value)
        ++begin;
    return begin;
}

• 迭代器（iterator） 是一种“行为类似指针”的对象。
• 只要容器提供符合要求的迭代器，find 就可以在其上运行（如 vector, list, deque 等）。
• 这就是 算法泛化（generalization） 的核心。