C++中std::list<shared_ptr<node>>排序函数未完成排序问题

嘿，我一眼就瞅出问题所在啦！你这段冒泡排序的核心问题是你交换的只是局部变量的副本，根本没碰原列表里的元素。

问题根源拆解 #

你看，当你写 first = *it 和 second = *++it 的时候，其实是把列表中两个 std::shared_ptr<Node> 分别拷贝到了 first 和 second 这两个局部变量里。之后你交换 first 和 second，只是改变了这两个局部变量的值，原列表里的元素完全没被修改——这就像你把书架上的两本书拿下来交换位置，却没把它们放回书架，书架当然还是原样啦！

修正后的冒泡排序代码 #

要解决这个问题，你需要直接操作迭代器指向的原元素，而不是拷贝副本。修改后的代码如下：

do {
    bool check = false;
    auto it = newList.begin();
    auto next_it = std::next(it);
    while (next_it != newList.end()) {
        if (comp_id(*it, *next_it)) {
            // 直接交换列表中的两个元素，而非副本
            std::swap(*it, *next_it);
            check = true;
        }
        ++it;
        ++next_it;
    }
} while (check);

这里做了几个优化：

• 用 bool 类型的 check 替代int，更符合C++的类型规范
• 用 std::next 获取下一个迭代器，避免手动++it可能带来的错误
• 直接对迭代器指向的元素调用 std::swap，真正修改原列表的内容

更高效的替代方案 #

其实 std::list 自带了专门的排序成员函数 std::list::sort，它是为双向链表优化过的排序算法，时间复杂度是O(n log n)，比你手写的冒泡排序（O(n²)）高效得多，而且代码更简洁：

// 如果comp_id的签名是bool(const shared_ptr<Node>&, const shared_ptr<Node>&)
newList.sort(comp_id);

// 或者用lambda表达式直接写比较逻辑（如果需要）
newList.sort([](const std::shared_ptr<Node>& a, const std::shared_ptr<Node>& b) {
    return a->id < b->id; // 假设comp_id的逻辑是比较id大小
});

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