0

出于愚蠢的原因，我想编写一个具有以下签名的函数（其中(^)代表 Apple 对 C++ 的“块”扩展）：

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

其中函数是根据 来实现的std::sort。（请注意，我不能使用qsort，因为它需要一个函数指针，而不是块指针；我不能使用qsort_b，因为我可能没有 Apple 的标准库。我不会接受涉及的答案qsort_b。）

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

请提供工作代码。魔鬼在细节中；我不是在问“我该如何使用std::sort？”

4

3 回答 3

1

要使用std::sort，您必须编写一个迭代器类和一个将块包装在仿函数对象中的类。自己实现快速排序似乎是一种更短的选择。

顺便说一句：该块应该返回 bool，而不是 void，对吗？

于 2013-01-02T00:27:17.050 回答
1

从这个开始：

struct memblockref {
  void* location;
  size_t size;
  memblockref( void* loc, size_t s ):location(loc), size(s) {}
  memblockref& operator=( memblockref const& right ) {
    Assert( size == right.size );
    memcpy( location, right.location, std::min( size, right.size ));
    return *this;
  }
private:
  memblockref( memblockref const& ) = delete; // or leave unimplemented in C++03
  memblockref() = delete; // or leave unimplemented in C++03
};

然后使用http://www.boost.org/doc/libs/1_52_0/libs/iterator/doc/iterator_facade.html为您的内存缓冲区创建 memblockref 的迭代器。

然后将块转换为函数指针，或将其包装在 lambda 或仿函数中，然后调用std::sort，在此处调用基于块的比较locationleft 和 right 的字段memblockref。

您可能必须专攻swap或也必须专攻iter_swap，但也许不必。

于 2013-01-02T01:11:33.987 回答
1

做到这一点比看起来应该的要难——尽管std::sort显然比 更强大qsort，但两者之间的阻抗不匹配足以使后者在前者方面的实施成为一项艰巨的任务。

尽管如此，还是可以做到的。这是用作主力的my_qsort_b（此处称为block_qsort）的工作实现。std::sort该代码改编自作为练习完成的实现qsort，std::sort并通过调用块进行了简单修改以进行比较。该代码经过测试可在 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));
}

如果block_qsort需要从 C 调用，您可以声明它extern "C"，因为它在其接口中不使用 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;
}
于 2013-10-19T20:40:31.273 回答