我想要做的事情
意思是，我可以将所有的键和数据复制到一对中，并按其第一个值（键）使用自定义比较谓词（或使用boost::bind）对该对进行排序；然后再将所有数据复制回来。我理解了这一点。这并不理想，因为我可能有几百兆字节的东西，上述方法涉及将其复制到临时位置，对临时位置进行排序，然后再将其复制回来。
它也不理想，因为我的分区方法，目前需要键和thingie的开始和结束迭代器（因为每次交换时必须同时交换）。此外，这是个难题——如果有两组thingies，我必须重新编写我的分区方法；我有一个键、一个决定分区方向的thingie，还有一个包裹其他信息的baggage thingie，我想用它来做其他算法。
现在，显然，我不想每次想要包括其他迭代器以与分区“tandom”交换时都重写分区方法。 所以，就像以前一样，我可以将所有这些东西复制到临时std::pair（如果需要交换更多的东西，则为嵌套的pairs），然后通过查看std::pair::first对其进行分区，然后将临时数据复制回来…… 但这是非常浪费的，因为我添加的每个额外的“包裹”thingie也可能是数百兆字节。
我知道我可以这样做。我不想那样做，因为它太浪费内存。 我想要的方式 上面描述的问题只是在迭代器上同时操作的问题之一。因此，我希望拥有一个迭代器集合，它抽象了该集合的内容。
我想要一个迭代器集合。我称之为piter（它是一对迭代器）。当交换两个piter时，实际上是在它们的第一个迭代器上进行std::iter_swap（以及它们的第二个迭代器）。
我想要一个piter迭代器（称为piterator），它具有所有迭代器的特性，但当它增加和减少时，它增加和减少piter的第一个和第二个迭代器。当piterator取消引用时，它应返回对piter的引用，即迭代器集合。所有距离都可以通过piter的第一个组件来测量。或者更一般地说，如果有任何需要回答的问题，并且不清楚哪个迭代器应该回答它，则piter的第一个迭代器应该回答它。
如果我想创建一个piterator，可以在其中tandom迭代多个迭代器，我可以创建一个piterator，其piter包含一个迭代器（第一个）和另一个piterator（第二个）。
所以，这就是我尝试过的（我也尝试使用boost::iterator_facade，但最终遇到了相同的问题——如下所述）。
上面的代码显示，piter可以正确交换元素，但不能正确排序。
上述代码的输出为：
我有一个分割元素的方法。这个方法并不会完全排序数组；它只是将数组划分为两部分，使得所有在某个预定的“中心点”或“中间值”（不必均匀分配）一侧的元素都小于“中心点”，而另一侧的所有元素都大于“中心点”。重点：这不是传统意义上的“排序”，而是一个分割。
当我分割元素时，需要保留一个键，以便随着元素交换，键也被交换；如果将来想撤销分割，则可以根据键重新排列元素。
显然，要根据键值重新排列元素，我可能要做一些类似以下的事情：
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）对该对进行排序；然后再将所有数据复制回来。我理解了这一点。这并不理想，因为我可能有几百兆字节的东西，上述方法涉及将其复制到临时位置，对临时位置进行排序，然后再将其复制回来。
它也不理想，因为我的分区方法，目前需要键和thingie的开始和结束迭代器（因为每次交换时必须同时交换）。此外，这是个难题——如果有两组thingies，我必须重新编写我的分区方法；我有一个键、一个决定分区方向的thingie，还有一个包裹其他信息的baggage thingie，我想用它来做其他算法。
现在，显然，我不想每次想要包括其他迭代器以与分区“tandom”交换时都重写分区方法。 所以，就像以前一样，我可以将所有这些东西复制到临时std::pair（如果需要交换更多的东西，则为嵌套的pairs），然后通过查看std::pair::first对其进行分区，然后将临时数据复制回来…… 但这是非常浪费的，因为我添加的每个额外的“包裹”thingie也可能是数百兆字节。
我知道我可以这样做。我不想那样做，因为它太浪费内存。 我想要的方式 上面描述的问题只是在迭代器上同时操作的问题之一。因此，我希望拥有一个迭代器集合，它抽象了该集合的内容。
我想要一个迭代器集合。我称之为piter（它是一对迭代器）。当交换两个piter时，实际上是在它们的第一个迭代器上进行std::iter_swap（以及它们的第二个迭代器）。
我想要一个piter迭代器（称为piterator），它具有所有迭代器的特性，但当它增加和减少时，它增加和减少piter的第一个和第二个迭代器。当piterator取消引用时，它应返回对piter的引用，即迭代器集合。所有距离都可以通过piter的第一个组件来测量。或者更一般地说，如果有任何需要回答的问题，并且不清楚哪个迭代器应该回答它，则piter的第一个迭代器应该回答它。
如果我想创建一个piterator，可以在其中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;
}
上面的代码显示，piter可以正确交换元素，但不能正确排序。
上述代码的输出为：
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正确地工作？
std::pair不应该被继承，为什么不使用组合（并且放弃 pair，它没有任何作用）。 - Matthieu M.std::partition有什么用处吗？ - Kerrek SB