Что я пытаюсь сделать
У меня есть метод, который разделяет вещи. Этот метод не сортирует массив полностью; он просто разделяет массив так, что все элементы на одной стороне (некоторого заранее определенного «центра» или «значения средней точки» - хотя это не должно приводить к равномерному разбиению) меньше «центра» и все элементы на другой стороне больше, чем центр. Точка: это не «сортировка» в традиционном смысле; это раздел.
Когда я делю вещи, мне нужно держать ключ; так что, когда все поменяно местами, ключ поменялся местами; и если в какой-то момент в будущем я захочу отменить раздел, я могу изменить порядок вещей на основе ключа.
Очевидно, чтобы переставить вещи на основе значения ключа, я мог бы сделать что-то вроде
std::vector< std::pair< std::size_t , my::thingie > > vp;
std::vector< std::size_t >::iterator itKey( key.begin() );
// itThingie_begin and itThingie_end exist; I don't have direct access to the container
my::thingie::iterator itThingie( itThingie_begin );
for (; itKey != key.end(); ++itKey; ++itThingie ) vp.push_back( *itKey, *itThingie );
std::sort( vp.begin() , vp.end() , &comp_pair_first );
itThingie = itThingie_begin;
for ( std::vector< std::pair< std::size_t , my::thingie > >::const_iterator p=vp.begin(); p!=vp.end(); ++p, ++itThingie ) *itThingie = p->second;
То есть я мог бы скопировать все ключ и данные в пару; и отсортировать пару по ее первому значению (ключу), используя пользовательский предикат сравнения (или с boost :: bind); а затем скопируйте все данные обратно. Я это понимаю. Это не идеально, потому что у меня, вероятно, есть пара сотен мегабайт штук, и вышеупомянутый подход включает в себя копирование этого во временный, сортировку временного и последующее копирование обратно.
Это также не идеально, потому что мой метод разбиения, как он существует в настоящее время, нуждается в начальных и конечных итераторах ключа И вещи (потому что он должен менять оба при каждом обмене). Более того, - и вот кикер - я должен переписать свой метод разбиения, если есть два набора штук; У меня есть ключ, вещь, которая определяет сторону раздела, и еще одна багажная вещь, у которой есть другая информация, которую я хочу использовать для других алгоритмов.
Теперь, разумеется, я не хочу переписывать метод разделения каждый раз Я хочу включить какой-то другой итератор для обмена "в тандоме" с разделом.
Так что, как и раньше, я мог бы скопировать все эти вещи во временную std :: pair (или вложенные пары, если мне нужно поменять местами несколько вещей в тандеме), а затем разбить ее на части, посмотрев сначала на std :: pair ::, а затем скопировать временные данные обратно ...
Но это чрезвычайно расточительно, потому что каждая дополнительная «багажная» вещь, которую я добавляю, также, вероятно, сотни мегабайт.
Я знаю, что мог бы сделать это таким образом. Я не хочу делать это таким образом, потому что это слишком много памяти.
Как я хочу это сделать
Проблема, которую я описал выше, заключается просто в работе с итераторами в тандеме. Поэтому я хотел бы иметь коллекцию итераторов, которая абстрагирует содержимое этой коллекции.
Я хочу иметь коллекцию итераторов. Я называю эту коллекцию питером (это пара итераторов). Когда кто-то меняет два питера, один действительно выполняет std :: iter_swap на своих первых итераторах (а также на своих вторых итераторах).
Я хочу иметь итератор Питера (называемый Питератором), который имеет все характеристики итератора, но когда он увеличивается и уменьшается, он увеличивает и уменьшает первый и второй итераторы Питера. Когда piterator разыменовывается, он должен возвращать ссылку на piter, который является коллекцией итераторов. Все расстояния могут быть измерены по первому компоненту питера. Или, в общем, если есть какой-либо вопрос, на который необходимо ответить, и неясно, какой итератор должен на него ответить, тогда на него должен ответить первый итератор питера.
Если я хочу создать питератор, который может использовать итератор в большем числе итераторов, я могу создать питератор, чей питер содержит итератор (первый) и еще один питератор (второй).
Итак, вот что я попробовал (я также пытался использовать boost :: iterator_facade, но у меня возникла та же проблема - как описано ниже.)
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <iterator>
//
// pair of iterators
//
template <typename T,typename U>
struct piter : public std::pair<T,U>
{
piter() : std::pair<T,U>() {};
piter( T const & l , U const & r ) : std::pair<T,U>(l,r) {};
piter( std::pair<T,U> const & p ) { this->first = p.first; this->second = p.second; };
//piter( std::pair<T,U> const p ) { this->first = p.first; this->second = p.second; };
template <typename OT, typename OU>
piter( piter<OT,OU> const & p ) : std::pair<T,U>::first(p.first), std::pair<T,U>::second(p.second) {}
piter<T,U> & operator=( piter<T,U> const & rhs )
{
if( &rhs != this ) { *this->first = *rhs.first; *this->second = *rhs.second; }
return *this;
};
friend void swap( piter<T,U> & lhs, piter<T,U> & rhs )
{
using std::swap;
std::cout << "piter::swap; WAS: " << *lhs.first << " <-> " << *rhs.first << std::endl;
std::iter_swap(lhs.first,rhs.first);
std::iter_swap(lhs.second,rhs.second);
std::cout << "piter::swap; NOW: " << *lhs.first << " <-> " << *rhs.first << std::endl;
};
};
//
// iterator of pair of iterators
//
template <typename T, typename U>
class piterator : public std::iterator< std::random_access_iterator_tag,
piter<T,U>,
std::ptrdiff_t,
piter<T,U> *,
piter<T,U> & >
{
typedef piterator<T,U> iter;
public: // Traits typedefs, which make this class usable with algorithms which need a random access iterator.
typedef std::random_access_iterator_tag iterator_category;
typedef piter<T,U> value_type;
typedef std::ptrdiff_t difference_type;
typedef piter<T,U> * pointer;
typedef piter<T,U> & reference;
public:
piterator() {};
piterator( iter const & rhs ) { this->mp.first = rhs.mp.first; this->mp.second = rhs.mp.second;};
piterator( pointer rhs ) { this->mp.first = rhs->first; this->mp.second = rhs->second; };
//piterator( reference const rhs ) { this->mp.first = rhs.first; this->mp.second = rhs.second; };
piterator( value_type const rhs ) { this->mp.first = rhs.first; this->mp.second = rhs.second; };
iter & operator=( iter const & rhs )
{
if ( &rhs != this ){ this->mp.first = rhs.mp.first; this->mp.second = rhs.mp.second; };
return *this;
}
friend void swap( iter & lhs , iter & rhs )
{
using std::swap;
std::cout << "piterator::swap; WAS: lhs " << *lhs->first << " rhs " << *rhs->first << std::endl;
swap(lhs.mp,rhs.mp);
std::cout << "piterator::swap; NOW: lhs " << *lhs->first << " rhs " << *rhs->first << std::endl;
}
public: // Comparison
// Note: it's an error to compare iterators over different files.
bool operator< ( iter const & rhs ) const { return mp.first < rhs.mp.first; }
bool operator> ( iter const & rhs ) const { return mp.first > rhs.mp.first; }
bool operator==( iter const & rhs ) const { return mp.first == rhs.mp.first; }
bool operator!=( iter const & rhs ) const { return mp.first != rhs.mp.first; }
public: // Iteration
iter & operator++() { ++mp.first; ++mp.second; return *this; }
iter & operator--() { --mp.first; --mp.second; return *this; }
iter operator++(int) { iter tmp(*this); ++(*this); return tmp; }
iter operator--(int) { iter tmp(*this); --(*this); return tmp; }
public: // Step
iter & operator+=( difference_type n ) { mp.first += n; mp.second += n; return *this; }
iter & operator-=( difference_type n ) { mp.first -= n; mp.second -= n; return *this; }
iter operator+ ( difference_type n ) { iter result(*this); return result += n; }
iter operator- ( difference_type n ) { iter result(*this); return result -= n; }
public: // Distance
difference_type operator-( iter & rhs ) { return mp.first - rhs.mp.first; }
public: // Access
reference operator*() { return mp; }
reference operator[]( difference_type n ) { return *(*this+n); }
pointer operator->() { return ∓ };
private: // State
value_type mp;
};
template<class T,class U>
bool proxy_comp( piter<T,U> left, piter<T,U> right )
{
std::cout << "proxy_comp: " << *(left.first) << " > " << *(right.first) << " ?=? " << ( *(left.first) > *(right.first) ) << std::endl;
return *left.first > *right.first;
}
int main()
{
std::vector<double> dv(3);
std::vector<int> iv(3);
dv[0] = -0.5; dv[1] = -1.5; dv[2] = -2.5;
iv[0] = 10; iv[1] = 20; iv[2] = 3;
typedef piterator< std::vector<int>::iterator , std::vector<double>::iterator > PAIR_ITER;
typedef PAIR_ITER::value_type PAIR_REF;
PAIR_ITER pair_begin( PAIR_REF( iv.begin() , dv.begin() ) );
PAIR_ITER pair_end( PAIR_REF( iv.end() , dv.end() ) );
std::cout << "paired arrays now:" << std::endl;
for ( PAIR_ITER p = pair_begin; p != pair_end; ++p )
std::cout << *p->first << " " << *p->second << std::endl;
std::cout << "swap 1st and 3rd elements..." << std::endl;
swap(*pair_begin,*(pair_begin+2));
std::cout << "paired arrays now:" << std::endl;
for ( PAIR_ITER p = pair_begin; p != pair_end; ++p )
std::cout << *p->first << " " << *p->second << std::endl;
std::cout << "calling sort..." << std::endl;
std::sort( pair_begin , pair_end , &proxy_comp<std::vector<int>::iterator , std::vector<double>::iterator> );
std::cout << "paired arrays now:" << std::endl;
for ( PAIR_ITER p = pair_begin; p != pair_end; ++p )
std::cout << *p->first << " " << *p->second << std::endl;
return 0;
}
ПРОБЛЕМА Питер и питератор, кажется, работают, когда я пытаюсь использовать его так же, как я использую все другие итераторы, но он не работает корректно с алгоритмами STL.
Приведенный выше код показывает, что питер правильно поменяется, но он не сортируется правильно.
Вывод вышеуказанного кода:
paired arrays now:
10 -0.5
20 -1.5
3 -2.5
swap 1st and 3rd elements...
piter::swap; WAS: 10 <-> 3
piter::swap; NOW: 3 <-> 10
paired arrays now:
3 -2.5
20 -1.5
10 -0.5
calling sort...
proxy_comp: 20 > 3 ?=? 1
proxy_comp: 10 > 3 ?=? 1
paired arrays now:
3 -2.5
3 -2.5
3 -2.5
ВОПРОС:
Что мне нужно изменить, чтобы std :: sort (или, в идеале, stl в целом) корректно работал с piterators?