c++ - 是否可以在运行时定义要在 STXXL 中排序的类型的长度？

Question

我有一个需要内置排序的应用程序，我希望用 STXXL 提供的排序替换现有的排序机制。我已经使用 STXXL 成功地测试了它，但我的问题是，虽然特定的排序运行需要对固定长度的字符串进行操作，但长度是在运行时确定的，可以在 10 字节到 4000 字节之间的任何地方。如果实际长度很小，总是允许 4000 字节显然是非常低效的。
对于那些不熟悉 STXXL 的人，我认为这个问题大致等同于在编译时不知道对象大小的情况下定义一个 std::vector。但是，我不是 C++ 专家 - 该应用程序是用 C 语言编写的。
在我的测试中，这是我正在排序的类型:

struct string80
{
    char x[80];
};

这是 STXXL 分类器的类型定义:

typedef stxxl::sorter<string80, sort_comparator80> stxxl_sorter80;  

问题是我不想将数组大小硬编码为“80”。
我能想到的唯一解决方案是定义许多不同长度的结构并在运行时选择最接近的。我错过了一个把戏吗？我是在用 C 而不是 C++ 来思考吗？

Answer 1

如果我们将大小为 n 的对象(记录)存储在一个平坦的 stxxl::vector of chars 中会怎么样。然后，定义一个基于 stxxl::vector::iterator 的自定义迭代器，它在每次递增时仅跳过 n 个字节。当使用 std::vector 而不是 STXXL 时，这将适用于 std::sort 甚至 tbb::sort。我看到 STXXL 的 ExtIterator 有很多额外的特性。是否可以为这样的迭代器正确定义它们？

#include <vector>
#include <cassert>
#include <cstdlib>
#include <stxxl.h>
#include <iostream>
#include <algorithm>

typedef std::vector<char>::iterator It;

class ObjectValue;

//This class defines a reference object that handles assignment operations
//during a sorting
class ObjectReference
{
public:
    ObjectReference() : recordSize_(0) {}
    ObjectReference(It ptr, size_t recordSize) : ptr_(ptr), recordSize_(recordSize) {}

    void operator = (ObjectReference source) const
    {
        std::copy(source.ptr_, source.ptr_ + recordSize_, ptr_);
    }

    void operator = (const ObjectValue & source) const;

    It GetIterator() const
    {
        return ptr_;
    }

    size_t GetRecordSize() const
    {
        return recordSize_;
    }

private:
    It ptr_;
    size_t recordSize_;
};

//This class defines a value object that is used when a temporary value of a
//record is required somewhere
class ObjectValue
{
public:
    ObjectValue() {}
    ObjectValue(ObjectReference prx) : object_(prx.GetIterator(), prx.GetIterator() + prx.GetRecordSize()) {}
    ObjectValue(It ptr, size_t recordSize) : object_(ptr, ptr + recordSize) {}
    std::vector<char>::const_iterator GetIterator() const
    {
        return object_.begin();
    }

private:
    std::vector<char> object_;
};

//We need to support copying from a reference to an object
void ObjectReference::operator = (const ObjectValue & source) const
{
    std::copy(source.GetIterator(), source.GetIterator() + recordSize_, ptr_);
}

//The comparator passed to a sorting algorithm. It recieves iterators, converts
//them to char pointers, that are passed to the actual comparator tha handles
//object comparison
template<class Cmp>
class Comparator
{
public:
    Comparator() {}
    Comparator(Cmp cmp) : cmp_(cmp) {} 

    bool operator () (const ObjectReference & a, const ObjectReference & b) const
    {
        return cmp_(&*a.GetIterator(), &*b.GetIterator());
    }

    bool operator () (const ObjectValue & a, const ObjectReference & b) const
    {
        return cmp_(&*a.GetIterator(), &*b.GetIterator());
    }

    bool operator () (const ObjectReference & a, const ObjectValue & b) const
    {
        return cmp_(&*a.GetIterator(), &*b.GetIterator());
    }

    bool operator () (const ObjectValue & a, const ObjectValue & b) const
    {
        return cmp_(&*a.GetIterator(), &*b.GetIterator());
    }

private:
    Cmp cmp_;
};

//The iterator that operates on flat byte area. If the record size is $n$, it
//just skips $n$ bytes on each increment operation to jump to the next record
class RecordIterator : public std::iterator<std::random_access_iterator_tag, ObjectValue, size_t, RecordIterator, ObjectReference>
{
public:
    RecordIterator() : recordSize_(0) {}
    RecordIterator(It ptr, size_t recordSize) : ptr_(ptr), recordSize_(recordSize) {}
    ObjectReference operator * () const
    {
        return ObjectReference(ptr_, recordSize_);
    }

    ObjectReference operator [] (size_t diff) const
    {
        return *(*this + diff);
    }

    It GetIterator() const
    {
        return ptr_;
    }

    size_t GetRecordSize() const
    {
        return recordSize_;
    }

    RecordIterator& operator ++()
    {
        ptr_ += recordSize_;
        return *this;
    }

    RecordIterator& operator --()
    {
        ptr_ -= recordSize_;
        return *this;
    }

    RecordIterator operator ++(int)
    {
        RecordIterator ret = *this;
        ptr_ += recordSize_;
        return ret;
    }

    RecordIterator operator --(int)
    {
        RecordIterator ret = *this;
        ptr_ -= recordSize_;
        return ret;
    }

    friend bool operator < (RecordIterator it1, RecordIterator it2);
    friend bool operator > (RecordIterator it1, RecordIterator it2);
    friend bool operator == (RecordIterator it1, RecordIterator it2);
    friend bool operator != (RecordIterator it1, RecordIterator it2);
    friend size_t operator - (RecordIterator it1, RecordIterator it2);
    friend RecordIterator operator - (RecordIterator it1, size_t shift);
    friend RecordIterator operator + (RecordIterator it1, size_t shift);

private:
    It ptr_;
    size_t recordSize_;
};

bool operator < (RecordIterator it1, RecordIterator it2)
{
    return it1.ptr_ < it2.ptr_;
}

bool operator > (RecordIterator it1, RecordIterator it2)
{
    return it1.ptr_ > it2.ptr_;
}

bool operator == (RecordIterator it1, RecordIterator it2)
{
    return it1.ptr_ == it2.ptr_;
}

bool operator != (RecordIterator it1, RecordIterator it2)
{
    return !(it1 == it2);
}

RecordIterator operator - (RecordIterator it1, size_t shift)
{
    return RecordIterator(it1.ptr_ - shift * it1.recordSize_, it1.recordSize_);
}

RecordIterator operator + (RecordIterator it1, size_t shift)
{
    return RecordIterator(it1.ptr_ + shift * it1.recordSize_, it1.recordSize_);
}

size_t operator - (RecordIterator it1, RecordIterator it2)
{
    return (it1.ptr_ - it2.ptr_) / it1.recordSize_;
}

namespace std
{
    //We need to specialize the swap for the sorting to work correctly
    template<>
    void swap(ObjectReference & it1, ObjectReference & it2)
    {       
        ObjectValue buf(it1.GetIterator(), it1.GetRecordSize());
        std::copy(it2.GetIterator(), it2.GetIterator() + it2.GetRecordSize(), it1.GetIterator());
        std::copy(buf.GetIterator(), buf.GetIterator() + it1.GetRecordSize(), it2.GetIterator());
    }
}

//Finally, here is the "user"-defined code. In the example, "records" are
//4-byte integers, although actual size of a record can be changed at runtime
class RecordComparer
{
public:
    bool operator ()(const char * aRawPtr, const char * bRawPtr) const
    {
        const int * aPtr = reinterpret_cast<const int*>(aRawPtr);
        const int * bPtr = reinterpret_cast<const int*>(bRawPtr);
        return *aPtr < *bPtr;
    }
};

int main(int, char*[])
{
    size_t size = 100500;
    //Although it is a constant, it is easy to change to in runtime 
    size_t recordSize = sizeof(int);

    std::vector<int> intVector(size);
    std::generate(intVector.begin(), intVector.end(), rand);    
    const char * source = reinterpret_cast<const char*>(&intVector[0]);
    std::vector<char> recordVector;
    std::copy(source, source + recordVector.size(), &recordVector[0]);
    RecordIterator begin(recordVector.begin(), recordSize);
    RecordIterator end(recordVector.end(), recordSize);

    //Sort "records" as blocks of bytes
    std::sort(begin, end, Comparator<RecordComparer>());
    //Sort "records" as usual
    std::sort(intVector.begin(), intVector.end());
    //Checking that arrays are the same:
    for (; begin != end; ++begin)
    {
        size_t i = begin - RecordIterator(recordVector.begin(), recordSize);
        It it = (*(begin)).GetIterator();
        int* value = reinterpret_cast<int*>(&(*it));
        assert(*value == intVector[i]);
    }

    return 0;
}