代码之家 › 专栏 › 技术社区 › Rob

qsort线程安全吗?

qsort mfc c++

Rob · 技术社区 · 14 年前

qsort 排序MFC CArray 但我看到偶尔的撞击 快速排序 同时。我使用的代码如下所示:

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

8 回复 | 直到 14 年前

SoapBox 14 年前

你的问题不一定与线程安全有关。

sort回调函数接受指向每个项的指针,而不是项本身。既然你在分类 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;
}

Roger Pate Roger Pate 14 年前

您的SortProc没有返回正确的结果,这可能会导致内存损坏,原因是假设数据在您完成排序后已排序。您甚至可以在qsort尝试排序时将其引入损坏,但这当然会因实现而异。

如果第一个对象小于第二个对象,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;
}

anon anon 14 年前

C++并不能真正保证线程安全。你能说的最多的是,多个读卡器或者一个数据结构的编写器都可以。读者和作者的任意组合,你需要以某种方式序列化访问。

Kirill V. Lyadvinsky 14 年前

因为你把你的问题贴上了 MFC 我想您应该在项目设置中选择多线程运行时库。

Björn Pollex 14 年前

现在,您的代码是线程安全的,但毫无用处,因为DoSort方法只使用局部变量,甚至不返回任何内容。如果正在排序的数据是Sorter的成员,那么从多个线程调用函数是不安全的。在gerenal中,仔细阅读 reentrancy ,这可能会让你知道你需要注意什么。

uray 14 年前

使它线程安全的是,无论您的对象是线程安全的,例如,要使qsort线程安全,您必须确保向对象写入或从对象读取的任何内容都是线程安全的。

Steve Jessop 14 年前

pthreads手册页列出了不需要线程安全的标准函数。qsort不在其中,所以它必须是线程安全的 在POSIX中 .

http://www.kernel.org/doc/man-pages/online/pages/man7/pthreads.7.html

不过,我找不到与Windows对应的列表,因此这并不能真正回答您的问题。如果不一样的话我会有点惊讶。

-2

graham.reeds 14 年前

std::sort 速度不如 qsort . 如果你真的找到了,试试看 std::stable_sort .

我曾经根据马克·尼尔森在《多布斯博士》一书中的代码编写了一个BWT压缩器,当我把它转换成类时,我发现它是有规律的 sort stable_sort 修正了速度问题。