使用std::vector作为底层容器的std::stack（自定义类型）为何失效？

问题根源分析 #

你的代码陷入无限循环的核心原因有两个：

1. 修改栈顶元素的副本而非原元素

在循环中你使用了 auto top = recStack.top();，这会创建栈顶元素的副本。当你修改 top.pivote 或 top.sortStep 时，这些更改只作用于副本，栈中存储的原元素完全没有被更新。这导致每次循环都会重复处理同一个未更新的栈元素：

• 原元素始终保持 pivote=-1，每次都会重新计算分区
• 原元素始终保持 sortStep=SORT_LEFT，每次都会重复推入左子数组任务

2. 左子数组起始索引错误

在推入左子数组任务时，你使用了函数参数 start 而非当前栈元素的 top.start，这会导致处理子数组时起始索引错误，进一步加剧逻辑混乱。

修复方案 #

关键代码修正

1. 使用引用而非副本访问栈顶元素：
   将 auto top = recStack.top(); 改为 auto& top = recStack.top();，确保修改直接作用于栈中的原元素。
2. 修正左子数组的起始索引：
   将 recStack.push(StackElement(start, top.pivote-1, 0, -1)); 改为 recStack.push(StackElement(top.start, top.pivote-1, 0, -1));，使用当前子数组的起始索引而非全局起始索引。

修复后的完整 sort 函数

void sort(int arr[], int start, int endIndex)
{
    std::stack<StackElement, std::vector<StackElement>> recStack;
    recStack.push(StackElement(start, endIndex, 0, -1));
    
    while (!recStack.empty())
    {
        auto& top = recStack.top(); // 使用引用访问原元素

        // 边界判断：子数组无需排序
        if (top.start >= top.endIndex) {
            recStack.pop();
            continue;
        }

        // 计算分区点（仅当未计算时）
        if (top.pivote == -1) {
            top.pivote = partition(arr, top.start, top.endIndex);
        }

        // 处理左子数组
        if (top.sortStep == SORT_LEFT) {
            recStack.push(StackElement(top.start, top.pivote-1, 0, -1)); // 使用top.start而非全局start
            top.sortStep = SORT_RIGHT; // 更新原元素的排序步骤
        }
        // 处理右子数组
        else if (top.sortStep == SORT_RIGHT) {
            StackElement ele(top.pivote+1, top.endIndex, 0, -1);
            recStack.pop();
            recStack.push(ele);
        }
    }
}

关于deque/list看似正常工作的说明 #

你观察到使用deque或list作为底层容器时程序正常，大概率是测试时的巧合或代码差异（比如无意中使用了引用访问栈顶元素）。实际上，原代码的逻辑错误与底层容器类型无关——只要修改的是副本而非原元素，任何容器都会出现无限循环问题。

后续注意事项 #

• 访问容器元素时，明确区分值拷贝和引用的差异，尤其是需要修改原元素时必须使用引用
• 处理递归转迭代的逻辑时，确保每个状态（如分区点、处理步骤）都能正确持久化到栈中
• 测试时需覆盖多种输入场景，避免因巧合掩盖逻辑错误

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