是快速排序线程安全的？

StackOverflow https://stackoverflow.com/questions/2424505

  •  19-09-2019
  •  | 
  •  

题

我有一个使用qsort排序结构的MFC CArray一些旧的代码，但我看到偶尔坠毁的可能的下降到多个线程同时调用qsort。我使用的代码看起来是这样的：

struct Foo
{
  CString str;
  time_t t;

  Foo(LPCTSTR lpsz, time_t ti) : str(lpsz), t(ti)
  {
  }
};

class Sorter()
{
public:
    static void DoSort();
    static int __cdecl SortProc(const void* elem1, const void* elem2);
};

...

void Sorter::DoSort()
{
  CArray<Foo*, Foo*> data;
  for (int i = 0; i < 100; i++)
  {
    Foo* foo = new Foo("some string", 12345678);
    data.Add(foo);
  }

  qsort(data.GetData(), data.GetCount(), sizeof(Foo*), SortProc);
  ...
}

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = (Foo*)elem1;
  Foo* foo2 = (Foo*)elem2;
  // 0xC0000005: Access violation reading location blah here
  return (int)(foo1->t - foo2->t);
}

...

Sorter::DoSort();

我将重构这个可怕代码来使用std::sort代替，但不知道是否以上实际上是不安全的？

编辑：Sorter::DoSort实际上是静态函数，但不使用静态变量本身

。

EDIT2：该SortProc功能被改变以匹配实际的代码

有帮助吗？

解决方案

您的问题并不一定有什么做用线saftey。

的

排序回调函数在指针的每个项目，而不是物品本身。既然你是排序Foo*你真正想要做的是访问参数Foo**，像这样的：

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = *(Foo**)elem1;
  Foo* foo2 = *(Foo**)elem2;
  if(foo1->t < foo2->t) return -1;
  else if (foo1->t > foo2->t) return 1;
  else return 0;
}

其他提示

您SortProc没有返回正确的结果，这可能是由一些假设的数据，那么，整理您完成整理之后会导致内存损坏。你甚至可以导致快速排序为腐败，因为它试图排序，但当然以实现不同而不同。

有关的qsort比较函数必须返回负如果第一对象是小于第二，零，如果它们是相等的，并且正否则。您当前的代码永远只返回0或1，返回1，当您应该返回负。

int __cdecl Sorter::SortProc(const void* ap, const void* bp) {
  Foo const& a = *(Foo const*)ap;
  Foo const& b = *(Foo const*)bp;
  if (a.t == b.t) return 0;
  return (a.t < b.t) ? -1 : 1;
}

C ++并没有真正了解线程安全的任何保证。关于你可以说的最多的是，要么多个读取器或一个作家的数据结构将确定。各位读者和作家的任意组合，并且需要以某种方式连载访问。

既然你标记MFC标记你的问题，我想你应该选择多线程运行时库中项目设置。

现在，你的代码是线程安全的，但没用，因为DoSort-方法只使用局部变量，甚至不返回任何东西。如果要排序的数据是分拣机的一员，那么它是不是安全地从多个线程调用该函数。在gerenal，阅读了关于重入，这可能会给你一个的想法是什么你需要看出来的。

什么使它线程安全的，你的对象是否是线程安全的，例如，使快速排序线程安全的，你必须确保任何写或读或和对象是线程安全的。

在并行线程手册页列出了不是线程安全所需的标准功能。的qsort不在其中，所以它需要是线程安全在POSIX

HTTP：//www.kernel .ORG / DOC /人-页/在线/页/ man7 / pthreads.7.html

我找不到适用于Windows相当于名单，虽然如此，这是不是一个真正的回答你的问题。我会有点惊讶，如果它是不同的。

要知道什么是“线程安全的”，在这种情况下意味着，虽然。这意味着可以同时调用相同的功能上不同的阵列 - 通过的qsort是安全的，这并不意味着对相同数据的并发访问（它不是）

。

作为警告的话，你可能会发现std::sort是不一样快qsort。如果您发现试图std::stable_sort。

我曾经写过基于代码中的BWT压缩机提出了我马克·尼尔森博士多布斯，当我把它变成类我发现，经常sort是慢了很多。 stable_sort固定的速度的问题。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top