基于下一个元素值从vector中移除元素的实现方法

标准库中的remove_if、for_each这类算法是无状态的——它们对每个元素的判断仅依赖元素自身，没法直接处理需要关联前一个元素的删除逻辑。不过可以借助带状态的标准库算法（比如std::accumulate）来实现简洁的代码，或者通过标记+清理的方式结合remove_if完成。

方案1：用std::accumulate构建结果（简洁函数式风格） #

std::accumulate允许我们在遍历过程中维护一个状态（这里是最终的结果容器），完美适配"遇到..则移除前一个元素"的逻辑。这种写法完全依赖标准库算法，代码非常简洁：

#include <vector>
#include <string>
#include <numeric>

// 返回处理后的新vector
std::vector<std::string> process_paths(const std::vector<std::string>& input) {
    return std::accumulate(input.begin(), input.end(), std::vector<std::string>{},
        [](std::vector<std::string>& result, const std::string& current) {
            if (current == ".." && !result.empty()) {
                // 遇到..且结果不为空，移除最后一个元素
                result.pop_back();
            } else {
                // 其他情况直接添加
                result.push_back(current);
            }
            return result;
        });
}

// 如果需要原地修改原vector
void process_paths_inplace(std::vector<std::string>& vec) {
    vec = std::accumulate(vec.begin(), vec.end(), std::vector<std::string>{},
        [](std::vector<std::string>& res, const std::string& s) {
            if (s == ".." && !res.empty()) {
                res.pop_back();
            } else {
                res.push_back(s);
            }
            return res;
        });
}

优缺点 #

• 优点：代码简洁、逻辑清晰，完全利用标准库算法实现，符合函数式编程风格。
• 缺点：会生成新的vector，对于超大容器有一定复制开销；如果必须原地修改，只能通过赋值覆盖原容器。

方案2：标记+remove_if清理（原地修改） #

如果不想生成新容器，可以先遍历标记需要删除的元素，再用remove_if批量移除。注意标记时要避免重复处理连续的..：

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

void process_paths_inplace(std::vector<std::string>& vec) {
    std::vector<bool> to_remove(vec.size(), false);
    
    // 第一遍遍历标记需要删除的元素
    for (size_t i = 1; i < vec.size(); ++i) {
        if (vec[i] == ".." && !to_remove[i-1]) { // 避免重复标记前一个元素
            to_remove[i-1] = true;
            to_remove[i] = true;
            ++i; // 跳过下一个元素，防止连续..的误处理
        }
    }
    
    // 第二遍用remove_if移除标记的元素
    auto new_end = std::remove_if(vec.begin(), vec.end(), 
        [idx = 0, &to_remove](const std::string&) mutable {
            return to_remove[idx++];
        });
    
    vec.erase(new_end, vec.end());
}

优缺点 #

• 优点：原地修改容器，无需额外复制大容器。
• 缺点：需要额外的bool向量存储标记，代码比accumulate方式稍繁琐。

对比：手动循环erase（原生高效写法） #

如果你追求极致的原地修改效率，手动循环结合erase其实也很简洁，虽然没用到标准库算法，但逻辑直观：

#include <vector>
#include <string>

void process_paths_inplace(std::vector<std::string>& vec) {
    for (auto it = vec.begin(); it != vec.end(); ) {
        if (it != vec.begin() && *it == "..") {
            // 删除前一个元素和当前元素，erase返回下一个有效迭代器
            it = vec.erase(std::prev(it), ++it);
        } else {
            ++it;
        }
    }
}

这种写法无需额外空间，处理大容器时性能最优，代码量也不大。

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