首次使用C++迭代器实现通用排序遇到问题求助

嘿，刚上手迭代器的时候确实容易绕晕，我来帮你把思路理清楚——咱们先把你卡住的int版本捋顺，再扩展到支持任意类型的通用版本～

先说说你现有代码的几个小问题 #

• 模板参数Type和Iterator有点冗余：迭代器本身可以通过typename Iterator::value_type获取它指向的元素类型，没必要单独传Type
• 硬转int*直接把函数锁死在int类型上了，完全没法扩展到其他类型
• 同时传数组和迭代器是多余的：迭代器已经能定位到容器的起始/结束位置，不需要再额外传数组

第一步：先写一个支持int容器的迭代器版排序 #

咱们用冒泡排序举例子（你代码里的循环看起来像是在写冒泡），直接用迭代器操作元素，不用依赖数组：

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm> // 用std::swap

using namespace std;

// 针对int类型的排序，只用迭代器参数
void sortInt(vector<int>::iterator beginning, vector<int>::iterator ending) {
    if (beginning == ending) return; // 空容器直接返回

    // 冒泡排序的迭代器实现
    for (auto i = beginning; i != ending - 1; ++i) {
        for (auto j = beginning; j != ending - (i - beginning) - 1; ++j) {
            if (*j > *(j + 1)) { // 解引用迭代器获取元素
                swap(*j, *(j + 1)); // 交换元素
            }
        }
    }
}

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9};
    sortInt(nums.begin(), nums.end());
    
    // 用ostream_iterator输出结果
    copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));
    // 输出：1 1 3 4 5 9
    return 0;
}

这里的关键是用*j解引用迭代器来访问元素，完全不需要数组指针，迭代器已经帮我们定位到了容器里的元素。

第二步：扩展到支持任意类型的通用排序函数 #

只需要把上面的函数改成模板，让迭代器类型作为模板参数，这样不管是int、string还是自定义类型，只要支持比较运算符就能用：

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>

using namespace std;

// 通用排序模板，只需要迭代器参数
template <typename Iterator>
void mySort(Iterator beginning, Iterator ending) {
    if (beginning == ending) return;

    // 这里换成选择排序，比冒泡效率高一点，迭代器实现也更直观
    for (auto current = beginning; current != ending; ++current) {
        auto minElementIter = current;
        // 找当前范围里的最小元素
        for (auto iter = next(current); iter != ending; ++iter) {
            if (*iter < *minElementIter) {
                minElementIter = iter;
            }
        }
        // 交换当前位置和最小元素的位置
        if (minElementIter != current) {
            swap(*current, *minElementIter);
        }
    }
}

int main() {
    // 测试int类型
    vector<int> nums = {3, 1, 4, 1, 5, 9};
    mySort(nums.begin(), nums.end());
    cout << "Sorted ints: ";
    copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // 测试string类型
    vector<string> fruits = {"banana", "apple", "cherry", "date"};
    mySort(fruits.begin(), fruits.end());
    cout << "Sorted strings: ";
    copy(fruits.begin(), fruits.end(), ostream_iterator<string>(cout, " "));
    cout << endl;

    return 0;
}

这个版本的优势：

• 完全通用：只要元素类型支持<运算符，就能直接用
• 迭代器友好：用next(current)代替current+1，对非随机访问迭代器（比如list的迭代器）也兼容（虽然选择排序在list上效率不高，但语法上是支持的）
• 不需要额外的类型参数，迭代器本身就携带了元素类型的信息

第三步：让自定义类型也支持排序 #

如果是你自己定义的结构体/类，只需要重载<运算符就行，比如：

struct Person {
    string name;
    int age;

    // 重载<，按年龄从小到大排序
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

// 然后就可以直接排序vector<Person>了
int main() {
    vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};
    mySort(people.begin(), people.end());
    // 排序后Bob、Alice、Charlie
    return 0;
}

内容的提问来源于stack exchange，提问作者Sangi