c++ - 根据 std::sort() 实现 qsort()

Question

出于愚蠢的原因，我想编写一个具有以下签名的函数(其中 (^) 代表 Apple 的 "blocks" 对 C++ 的扩展):

extern "C" my_qsort_b(void *arr, size_t nelem, size_t eltsize, int (^)(const void *, const void *));

函数根据 std::sort 实现。 (请注意，我不能使用 qsort，因为它采用函数指针，而不是 block 指针；而且我不能使用 qsort_b，因为我可能没有 Apple 的标准库.我不会接受涉及qsort_b的答案。)

是否可以使用 std::sort 在 C++ 中实现此功能？还是我必须从头开始编写自己的快速排序实现？

请提供工作代码。细节决定成败；我不是在问“我如何使用 std::sort？”

Answer 1

这样做比看起来更难 — 尽管 std::sort 显然比 qsort 更强大，但两者之间的阻抗不匹配足以使根据前者实现后者是一项艰巨的任务。

不过，还是可以的。这是 my_qsort_b 的工作实现(此处称为 block_qsort)，它使用 std::sort 作为主力。该代码根据作为练习完成的 std::sort 改编自 qsort 的实现，并经过简单修改以通过调用 block 进行比较。代码经过测试可以在 x86_64 Linux 上编译和使用 clang++ 3.3。

#include <algorithm>
#include <cstring>

struct Elem {
  char* location;
  size_t size;
  bool needs_deleting;
  Elem(char* location_, size_t size_):
    location(location_), size(size_), needs_deleting(false) {}
  Elem(const Elem& rhs): size(rhs.size) {
    location = new char[size];
    *this = rhs;
    needs_deleting = true;
  }
  Elem& operator=(const Elem& rhs) {
    memcpy(location, rhs.location, size);
    return *this;
  }
  ~Elem() {
    if (needs_deleting)
      delete[] location;
  }
};

struct Iter: public std::iterator<std::random_access_iterator_tag, Elem> {
  Elem elem;

  Iter(char* location, size_t size): elem(location, size) {}
  // Must define custom copy/assignment to avoid copying of iterators
  // making copies of elem.
  Iter(const Iter& rhs): elem(rhs.elem.location, rhs.elem.size) {}
  Iter& operator=(const Iter& rhs) {elem.location = rhs.elem.location; return *this;}

  char* adjust(ptrdiff_t offset) const {
    return elem.location + ptrdiff_t(elem.size) * offset;
  }

  // Operations required for random iterator.
  Iter operator+(ptrdiff_t diff) const {return Iter(adjust(diff), elem.size);}
  Iter operator-(ptrdiff_t diff) const {return Iter(adjust(-diff), elem.size);}
  ptrdiff_t operator-(const Iter& rhs) const {
    return (elem.location - rhs.elem.location) / ptrdiff_t(elem.size);
  }
  Iter& operator++() {elem.location=adjust(1); return *this;}
  Iter& operator--() {elem.location=adjust(-1); return *this;}
  Iter operator++(int) {Iter old = *this; ++*this; return old;}
  Iter operator--(int) {Iter old = *this; --*this; return old;}
  bool operator!=(const Iter& rhs) const {return elem.location != rhs.elem.location;}
  bool operator==(const Iter& rhs) const {return elem.location == rhs.elem.location;}
  bool operator<(const Iter& rhs) const {return elem.location < rhs.elem.location;}

  Elem& operator*() {return elem;}
};

struct Cmp_adaptor {
  typedef int (^Qsort_comparator)(const void*, const void*);
  Qsort_comparator cmp;
  Cmp_adaptor(Qsort_comparator cmp_) : cmp(cmp_) {}
  bool operator()(const Elem& a, const Elem& b) {
    return cmp(a.location, b.location) < 0;
  }
};

void block_qsort(void* base, size_t nmemb, size_t size,
                 int (^compar)(const void *, const void *))
{
  Iter begin = Iter(static_cast<char*>(base), size);
  std::sort(begin, begin + nmemb, Cmp_adaptor(compar));
}

如果需要从 C 调用 block_qsort，您可以将其声明为 extern "C"，因为它在其接口(interface)中不使用 C++ 功能。要测试该功能，请编译并运行此附加代码:

// test block_qsort

#include <iostream>
#include <cstring>

int main(int argc, char** argv)
{
  // sort argv[1..argc].
  block_qsort(argv + 1, argc - 1, sizeof (char*),
              ^int (const void* a, const void* b) {
                return strcmp(*(char**) a, *(char**) b);
              });
  for (++argv; *argv; argv++)
    std::cout << *argv << std::endl;
  return 0;
}