sorting - 标准排序使 std::vector 无效

问题描述

我在 std::sort 中发现了一个错误，特别是在 QuickSort 的某些实现中，我不知道问题是否出在一般算法中。

本质：

当元素小于 16 时所有规范，因为 std::sort 使用插入排序。

当有 17 个或更多元素时，使用快速排序并限制元素数量的对数的递归深度，但向量在第一次 __introsort_loop 迭代时有时间恶化。

当许多相同的元素时存在向量损坏。通过用无效迭代器替换有效迭代器而发生损坏。

其他容器也可能破裂，我没有检查。

一个简单的例子，使用“int”类型的向量，对于更复杂的对象 - 在排序时崩溃，因为无效的对象被传递给比较函数：

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

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */

  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
  };

  /* recursion */

  if (left < j)
        quickSort(arr, left, j);

      if (i < right)
            quickSort(arr, i, right);
}

int main()
{
  for( int i = 0 ; i < 1 ; i++ )
  {
    //std::vector<int> v({5, 6, 1, 6, 2, 6, 3, 6, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6});//reproducible with this
    std::vector<int> v(19, 6);//reproducible with this also
    std::sort(std::begin(v), std::end(v), [&v]( const int & left, const int & right )
                                          {
//                                          std::cout << " left=" << left << ", right=" << right << std::endl;
                                            bool b = left <= right;
                                            return b;
                                          }
              );
//    quickSort(v.data(), 0, v.size());
 for( const auto & result : v )
 {
    std::cout << "results: " << result << std::endl;
 }
  }

  std::cout << "Hello World!\n";
}

有人可以遇到这种行为快速排序吗？

标签： sortingstdquicksort

sorting - 标准排序使 std::vector 无效

问题描述

解决方案

推荐阅读