Что, если мы будем хранить объекты (записи) размером n в плоском stxxl::vector из символов. Затем определите собственный итератор на основе stxxl::vector::iterator, который просто пропускает n байт при каждом приращении. Это будет работать с std::sort и даже с tbb::sort при использовании std::vector вместо STXXL. Я вижу, что ExtIterator STXXL имеет много дополнительных свойств. Можно ли их правильно определить для такого итератора?
#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;
}
person
Ilia Minkin
schedule
03.07.2015
