使用std::stable_partition整理vector遇错误，求技术解决方案

嘿，我来帮你搞定这个问题！首先得先排查常见的错误点，再给出可行的实现方案～

首先，先排查你可能踩的坑 #

1. s_startswith 函数的越界问题

这是最常见的错误！如果你的函数实现没有检查字符串长度是否大于等于前缀长度，直接访问字符的话，会触发未定义行为（比如崩溃、输出乱码）。比如这种错误实现：

// 错误示例：当字符串长度小于7时，s[i]会越界
bool s_startswith(const std::string& s) {
    const char* prefix = "unknown";
    for (int i=0; i<7; i++) {
        if (s[i] != prefix[i]) return false;
    }
    return true;
}

正确的实现应该先判断长度，再做匹配：

// 推荐实现1：用string的compare方法
bool s_startswith(const std::string& str, const std::string& prefix) {
    if (prefix.size() > str.size()) return false;
    return str.compare(0, prefix.size(), prefix) == 0;
}

// 推荐实现2：用std::equal更简洁
bool s_startswith(const std::string& str, const std::string& prefix) {
    return str.size() >= prefix.size() && std::equal(prefix.begin(), prefix.end(), str.begin());
}

2. 错误定位最后一个":"结尾的元素

如果你用正向的std::find_if，找到的是第一个符合条件的元素，而不是最后一个，这会导致unknown元素被移到错误的位置。正确的做法是从后往前找：

#include <algorithm>
#include <vector>
#include <string>

// 找到最后一个以":"结尾的元素的正向迭代器
auto find_last_colon_element(std::vector<std::string>& vec) {
    auto rit = std::find_if(vec.rbegin(), vec.rend(),
        [](const std::string& s) {
            return !s.empty() && s.back() == ':'; // 先判断非空，避免访问空字符串的back()
        });
    if (rit == vec.rend()) {
        // 如果没有找到任何":"结尾的元素，就把unknown移到vector末尾
        return vec.end();
    }
    // reverse iterator的base()指向元素的下一个位置，所以减1得到元素本身的迭代器
    return rit.base() - 1;
}

实现需求：把unknown元素移到最后一个":"元素正下方 #

如果你一定要用std::stable_partition，可以分两步处理；如果追求直观易维护，直接收集unknown元素再插入的方式更简单。

方案1：直观收集插入法（推荐）

这种方法逻辑清晰，不容易出错，还能保持unknown元素和非unknown元素的相对顺序：

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

// 正确的s_startswith函数（选上面任意一种即可）
bool s_startswith(const std::string& str, const std::string& prefix) {
    return str.size() >= prefix.size() && std::equal(prefix.begin(), prefix.end(), str.begin());
}

// 找到最后一个":"结尾的元素
auto find_last_colon_element(std::vector<std::string>& vec) {
    auto rit = std::find_if(vec.rbegin(), vec.rend(),
        [](const std::string& s) {
            return !s.empty() && s.back() == ':';
        });
    if (rit == vec.rend()) return vec.end();
    return rit.base() - 1;
}

int main() {
    std::vector<std::string> vec = {"a:", "b", "unknown1", "c:", "d", "unknown2", "e"};

    // 1. 找到目标位置
    auto colon_it = find_last_colon_element(vec);

    // 2. 收集所有unknown元素并从原vector删除
    std::vector<std::string> unknown_elements;
    auto it = vec.begin();
    while (it != vec.end()) {
        if (s_startswith(*it, "unknown")) {
            unknown_elements.push_back(std::move(*it)); // 用move避免拷贝
            it = vec.erase(it);
        } else {
            ++it;
        }
    }

    // 3. 把unknown元素插入到最后一个":"元素的紧后面
    auto insert_pos = (colon_it != vec.end()) ? std::next(colon_it) : vec.end();
    vec.insert(insert_pos, unknown_elements.begin(), unknown_elements.end());

    // 输出结果
    for (const auto& s : vec) {
        std::cout << s << "\n";
    }
    return 0;
}

运行结果：

a:
b
c:
unknown1
unknown2
d
e

完全符合需求：所有unknown元素都在最后一个":"元素（c:）的正下方，其他元素保持原有相对顺序。

方案2：用std::stable_partition实现

如果坚持要用stable_partition，可以分两次分区再拼接：

int main() {
    std::vector<std::string> vec = {"a:", "b", "unknown1", "c:", "d", "unknown2", "e"};

    auto colon_it = find_last_colon_element(vec);
    if (colon_it == vec.end()) {
        // 没有":"元素，直接把unknown移到最后
        std::stable_partition(vec.begin(), vec.end(),
            [](const std::string& s) { return !s_startswith(s, "unknown"); });
        return 0;
    }

    // 第一步：分区colon_it之前的元素，把非unknown放在前面，unknown放在后面
    auto part1 = std::stable_partition(vec.begin(), std::next(colon_it),
        [](const std::string& s) { return !s_startswith(s, "unknown"); });

    // 第二步：分区colon_it之后的元素，把非unknown放在前面，unknown放在后面
    auto part2 = std::stable_partition(std::next(colon_it), vec.end(),
        [](const std::string& s) { return !s_startswith(s, "unknown"); });

    // 把colon_it之前的unknown元素移到colon_it之后的unknown元素前面
    vec.splice(part2, vec, part1, std::next(colon_it));

    // 输出结果
    for (const auto& s : vec) {
        std::cout << s << "\n";
    }
    return 0;
}

这个方案的结果和方案1一致，只是用stable_partition完成分区，再用splice拼接unknown元素的位置。

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