С ++ stl-совместимый итератор итераторов
То, что я пытаюсь сделать
У меня есть метод, который разделяет вещи. Этот метод не сортирует массив полностью; он просто разделяет массив так, чтобы все элементы с одной стороны (некоторого заранее определенного «центра» или «среднего значения» - хотя это не должно приводить к равному разделению) были меньше, чем «центр» и все элементы на другой стороне больше центра. Точка: это не «сорт» в традиционном смысле; это раздел.
Когда я разбиваю вещи, мне нужно сохранить ключ; так что, когда вещи меняются местами, ключ меняется; и если в какой-то момент в будущем я захочу отменить раздел, я могу изменить порядок вещей на основе ключа.
Очевидно, что для перегруппировки вещей на основе значения ключа я мог сделать что-то вроде
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, который представляет собой набор итераторов. Все расстояния можно измерить по первому компоненту питера. Или, в более общем плане, если есть какой-либо вопрос, на который нужно ответить, и неясно, какой итератор должен на него ответить, то первый итератор питера должен ответить на него.
Если я хочу создать питератора, который может вводитьtandom итератор вместо большего количества итераторов, я могу создать piterator, piter которого содержит итератор (первый) и другой piterator (второй).
Итак, вот что я пробовал (я также пробовал использовать 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 в целом) правильно работал с питераторами?