1

我正在开发一个定义接口的 SDK，例如

class FooIter
{
    // Move to the next foo, return false if there is none.
    virtual bool Move() = 0;

    // Return a pointer to the current foo.
    virtual const void* GetFoo() = 0;

    // Get the size of a 'foo', which is a fixed-size POD.
    virtual size_t GetFooSize() = 0;

    // Get a comparator for foos.
    virtual const FooComparator* GetComparator() = 0;
};

class FooComparator
{
    virtual int compare(const void* first, const void* second) const = 0;
};

所以基本上， foo 是一种不透明类型，我可以将其视为固定长度的二进制缓冲区 + 和相关的排序函数。

现在，我想在将这些 foo 传递回客户端代码之前对其进行排序。可能有很多foo，所以我必须实现外部排序，但我想使用 std::sort 对初始运行进行排序。

我在想我会分配一个大小为 N * FooIter::GetFooSize() 的缓冲区，使用 FooIter 用 foos 填充它，然后在将其写入磁盘之前使用 std::sort 对其进行排序。

我可以从编写一个迭代器类开始

class FooBufferIter
{
public:
    FooBufferIter(const void* fooAddr, int fooSize) : m_fooAddr(fooAddr), m_fooSize(fooSize) {}

    FooWrapper operator*() {return FooWrapper(m_fooAddr, m_fooSize);}

    FooBufferIter operator++() {return FooBufferIter(m_fooAddr + m_fooSize, m_fooSize);}

    // All other needed iterator methods.
private:
    const void* m_fooAddr;
    int m_fooSize;
};

和 foo 内存的包装类

class FooWrapper
{
public:
    FooWrapper(const void* fooAddr, int fooSize) : m_fooAddr(fooAddr), m_fooSize(fooSize) {}

private:
    const void* m_fooAddr;
    int m_fooSize;
};

我的理解是 std::sort 将使用 std::swap 重新排列序列中的元素。我的问题是我看不到如何在 FooWrapper 上专门化 std::swap 以有效地执行交换（最重要的是，没有动态分配）。我可以逐字节交换，但这似乎也效率低下。

另一种方法是将指针的并行序列排序到我的 Foo 数组中，但我不想这样做，因为在实践中， foo 可能会非常小，因此并行序列可以使用同样多内存作为 foo 序列，我想最大化它们一次可以排序的数量。

还有很好的 ol' qsort 可能更适合这种事情，但我不确定如何将 FooComparator 对象转换为函数指针（FooComparator 可能有多种实现）。

或者有没有更好的方法来解决这个问题？我真的不想编写自己的排序实现，尽管它可能不会太难。

4

1 回答 1

1

我会构建一个 void* 缓冲区，对它们进行排序，然后生成输出缓冲区。

作为第一步。因为容易。然后编写其他所有内容并寻找性能瓶颈。

作为下一步，我将看看是否可以使用完整类型信息进行内部排序。因为最优。

做不到这一点，一个带有专门交换的 pod 块伪引用迭代器。如果性能测试证明进一步优化是合理的，那么对于小型和大型来说，tomfoolery 就会对大的指针和小型的数据进行排序。

但从 KISS 开始，先做必须硬的部分。

于 2013-02-23T23:41:25.117 回答