C ++ stl-compatible iterator iterators

Question

What am i trying to do

I have a method that shares things. This method does not completely sort the array; it simply splits the array in such a way that all elements on one side (of a predetermined "center" or "average value" - this should not lead to an even split, though) is smaller than the "center" and all elements on the other side are larger than the center . Point: this is not a "variety" in the traditional sense; this is the section.

When I share things, I need to hold the key; so when things are exchanged, the key is exchanged; and if at some point in the future I want to cancel the section, I can change the order of things based on the key.

Obviously, to reorder things based on the key value, I could do something like

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; 

Meaning, I can copy the entire key and data into a pair; and sort the pair by the first value (key), using a special comparison predicate (or with boost :: bind); and then copy all the data again. I understand it. This is not ideal, because I probably have a couple of hundred megabytes pieces, and the above approach involves copying this to a temporary one, sorting the temporary one and then copying it later.

It is also not ideal, because my method of separation, as it currently is, needs iterators of the beginning and end of the key AND things (because it has to change like every time it swaps). Moreover, here is the kicker - I have to rewrite my method of separation if there are two sets of objects; I have a key, a thing that decides the section side and another baggage thing that has other information that I want to use for other algorithms.

Now, obviously, I don't want to rewrite the splitting method everytime . I want to include another iterator in it for sharing "in tandom" with a section. So, as before, I could copy it all into a temporary std :: pair (or nested pairs if I need to swap more), and then split it by looking at std :: pair :: first, and then copy the temporary the data is back ... But this is unusually wasteful, because every added “baggage” thing that I add is also probably hundreds of megabytes.

I know I can do it. I do not want to do this because it is too intense for memory.

How i want to do it

The problem that I described above is just one of the operations in iterators in tandem. Therefore, I would like to have a collection of iterators that abstracts the contents of this collection.

I want to have a set of iterators. I call this collection Peter (it's a pair of iterators). When you change two peters, one really does std :: iter_swap on its first iterators (as well as their second iterators).

I want to have a piter iterator (called a piter) that has all the characteristics of an iterator, but when it increases and decreases, it increases and decreases the first and second iterators of the piter. When the piterator breaks, it should return a link to piter, which is a collection of iterators. All distances can be measured by the first component of the peter. Or more generally, if there is any question that needs to be answered, and it is not clear what it should answer, then the first iterator of St. Petersburg should answer it.

If I want to create a piterator that can use the in-tandom iterator for more iterators, I can create a piterator whose piter contains an iterator (first) and another piterator (second).

So here is what I tried (I also tried using boost :: iterator_facade, but in the end I have the same problem as described below).

 #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 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 &mp; }; 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; } 

PROBLEM Peter and the Peterrator seem to work when I try to use it, like the way I use all other iterators, but it does not work correctly with STL algorithms.

The above code shows that piter swaps correctly, but it does not sort correctly.

The output of the above code:

  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 

QUESTION:

What do I need to change so that std :: sort (or, ideally, stl as a whole) works correctly with St. Petersburg?

Answer 1

OK The problem is how stl moves memory. He used swap () all the time, then everything will be fine, but sometimes it happens (from gnu stl_algo.h __insertion_sort)

 if (__comp(*__i, *__first)) { // COPY VALUE INTO TEMPORARY MEMORY typename iterator_traits<_RandomAccessIterator>::value_type __val = _GLIBCXX_MOVE(*__i); // MOVE MEMORY AROUND _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); // COPY TEMPORARY VALUE BACK *__first = _GLIBCXX_MOVE(__val); } 

So, we see that the :: value_type iterator should store the value. It cannot, by itself, be a pointer. If it was a pointer, then it completes the cancellation of the pseudo-context approach shown above.

Therefore, we need to create a helper class, which is a set of VALUES values, not a set of ITERATORS. We can return this helper class when the pit dereferencing operator is constant, for example,

 value_type operator*() const { return helper_class_value_collection_ctor( _args_ ); }; 

Thus, we can store values ​​in new memory.

In addition, we need to create another helper class, which is a set of ITERATORS, unlike VALUES, so expressions like

 *piterator_a = *piterator_b 

. If * piterator_a is returned by value, then setting these values ​​is pointless because the return value is temporary. Thus, in this case, we need a dereference operator to return a reference type (a collection of iterators), which will be stored as a private member variable of the piterator.

 reference operator*() { return private_reftype_variable; }; 

So, this completely leads to the following.

 #include <vector> #include <iostream> #include <utility> #include <iterator> #include <algorithm> // forward decl template <typename T,typename U> struct piterator_iterators; template <typename T,typename U> struct piterator_values { // This class holds memory; it is a value_type // It only serves the purpose of // allowing the stl to hold temporary values when moving memory around. // If the stl called sort(), then this class wouldn't be necessary. // // Note that the memory may be set by a piterator_iterators class, // which is a pseudo-value_type that points at memory, instead of holding memory. // // YOU NEED THIS SO THAT // typename piterator<T,U>::value_type Tmp = *piterator_a // PLACES THE VALUES INTO SOME (ACTUAL) TEMPORARY MEMORY, AS OPPOSED // TO CREATING A NEW POINTER TO EXISTING MEMORY. typedef typename T::value_type first_value; typedef typename U::value_type second_value; first_value first; second_value second; piterator_values() {}; piterator_values( first_value const & first , second_value const & second ) : first(first), second(second) {}; piterator_values( piterator_values<T,U> const & rhs ) : first(rhs.first), second(rhs.second) { }; piterator_values( piterator_iterators<T,U> const & rhs ) : first(*rhs.first), second(*rhs.second) { }; piterator_values<T,U> & operator=( piterator_values<T,U> const & rhs ) { if( &rhs != this ) { first = rhs.first; second = rhs.second; } return *this; }; piterator_values<T,U> & operator=( piterator_iterators<T,U> const & rhs ) { if( &rhs != this ) { first = *rhs.first; second = *rhs.second; } return *this; }; friend void swap( piterator_values<T,U> & lhs, piterator_values<T,U> & rhs ) { using std::swap; swap(lhs.first,rhs.first); swap(lhs.second,rhs.second); }; }; template <typename T,typename U> struct piterator_iterators { T first; U second; // This class does not hold memory; it points at existing memory. // It is a pseudo-value_type. When the piterator dereferences, it // will return a piterator_iterators object IF it is a nonconst reference. // This class is used as a "reference" for an actual iterator, // so assignment operators change the value of the thing pointed at, // as opposed to reseting the address of what is being pointed at. // // YOU NEED THIS SO THAT // *piterator_a = *piterator_b // MAKES SENSE. // IF THE DEREFERENCE PASSED A piterator_values, // THEN IT WOULD ONLY MODIFY A TEMPORARY, NOT THE ACTUAL THING // piterator_iterators() {}; piterator_iterators( T const & first , U const & second ) : first(first), second(second) {}; piterator_iterators( piterator_iterators<T,U> const & rhs ) : first(rhs.first), second(rhs.second) {}; piterator_iterators<T,U> & operator=( piterator_iterators<T,U> const & rhs ) { if( &rhs != this ) { *first = *rhs.first; *second = *rhs.second; } return *this; }; piterator_iterators<T,U> & operator=( piterator_values<T,U> const & rhs ) { *first = rhs.first; *second = rhs.second; return *this; }; friend void swap( piterator_iterators<T,U> & lhs, piterator_iterators<T,U> & rhs ) { using std::swap; std::iter_swap(lhs.first,rhs.first); std::iter_swap(lhs.second,rhs.second); }; }; // // iterator of pair of iterators // template <typename T, typename U> class piterator : public std::iterator< std::random_access_iterator_tag, piterator_values<T,U>, std::ptrdiff_t, piterator_iterators<T,U> *, piterator_iterators<T,U> & > { typedef piterator<T,U> iter; public: typedef std::random_access_iterator_tag iterator_catagory; typedef typename piterator<T,U>::value_type value_type; typedef typename piterator<T,U>::difference_type difference_type; typedef typename piterator<T,U>::pointer pointer; typedef typename piterator<T,U>::reference reference; typedef piterator_iterators<T,U> value_of_reference; //typedef typename piterator_iterators<T,U> & reference; public: piterator() {}; piterator( iter const & rhs ) { mp.first = rhs.mp.first; mp.second = rhs.mp.second; }; piterator( value_of_reference const rhs ) { mp.first = rhs.first; mp.second = rhs.second; }; piterator( T const first, U const second ) { mp.first = first; mp.second = second; }; iter & operator=( iter const & rhs ) { if ( &rhs != this ) { mp.first = rhs.mp.first; mp.second = rhs.mp.second; }; return *this; } friend void swap( iter & lhs , iter & rhs ) { using std::swap; swap(lhs.mp,rhs.mp); } public: // Comparison 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; } difference_type operator+ ( iter const & rhs ) { return mp.first + rhs.mp.first; } difference_type operator- ( iter const & rhs ) { return mp.first - rhs.mp.first; } public: // Distance difference_type operator-( iter & rhs ) { return mp.first - rhs.mp.first; } public: // Access // reference if on the lhs of the eq. reference operator*() { return mp; } // value if on the rhs of the eq. value_type operator*() const { return value_type(*mp.first,*mp.second); } reference operator[]( difference_type n ) { return *( (*this) + n ); } pointer operator->() { return &mp; }; private: // State value_of_reference mp; }; 

Here's the main program, separated from above to see how it is used.

 //////////////////////////////////////////////////////////////// template<class T,class U> bool proxy_comp( piterator_values<T,U> left, piterator_values<T,U> right ) { return left.first < right.first; } /////////////////////////////////////////////////////////////// int main() { std::vector<double> dv1(3); std::vector<double> dv2(3); std::vector<int> iv(3); dv1[0] = -0.5; dv1[1] = -1.5; dv1[2] = -2.5; dv2[0] = 10.5; dv2[1] = 11.5; dv2[2] = 12.5; iv[0] = 10; iv[1] = 20; iv[2] = 3; // // EXAMPLE 1: PAIR OF ITERATORS // typedef piterator< std::vector<int>::iterator , std::vector<double>::iterator > PAIR_ITER; PAIR_ITER pair_begin( iv.begin() , dv1.begin() ); PAIR_ITER pair_end( iv.end() , dv1.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; // // EXAMPLE 2: TRIPLET (PAIR OF PAIR) // typedef piterator< std::vector<double>::iterator , std::vector<double>::iterator > DOUBLET_ITER; typedef piterator< std::vector<int>::iterator , DOUBLET_ITER > TRIPLET_ITER; TRIPLET_ITER triplet_begin( iv.begin(), DOUBLET_ITER( dv1.begin() , dv2.begin() ) ); TRIPLET_ITER triplet_end( iv.end(), DOUBLET_ITER( dv1.end() , dv2.end() ) ); std::cout << "tripleted arrays now:" << std::endl; for ( TRIPLET_ITER p = triplet_begin; p != triplet_end; ++p ) std::cout << *p->first << " " << *p->second->first << " " << *p->second->second << std::endl; std::cout << "iter_swap 1st and second elements..." << std::endl; std::iter_swap( triplet_begin , triplet_begin+1 ); std::cout << "tripleted arrays now:" << std::endl; for ( TRIPLET_ITER p = triplet_begin; p != triplet_end; ++p ) std::cout << *p->first << " " << *p->second->first << " " << *p->second->second << std::endl; std::cout << "calling sort..." << std::endl; std::sort( triplet_begin, triplet_end, &proxy_comp< std::vector<int>::iterator , piterator< std::vector<double>::iterator , std::vector<double>::iterator > > ); std::cout << "tripleted arrays now:" << std::endl; for ( TRIPLET_ITER p = triplet_begin; p != triplet_end; ++p ) std::cout << *p->first << " " << *p->second->first << " " << *p->second->second << std::endl; return 0; } 

Here is the above program

 paired arrays now: 10 -0.5 20 -1.5 3 -2.5 swap 1st and 3rd elements... paired arrays now: 3 -2.5 20 -1.5 10 -0.5 calling sort... paired arrays now: 3 -2.5 10 -0.5 20 -1.5 tripleted arrays now: 3 -2.5 10.5 10 -0.5 11.5 20 -1.5 12.5 iter_swap 1st and second elements... tripleted arrays now: 10 -0.5 11.5 3 -2.5 10.5 20 -1.5 12.5 calling sort... tripleted arrays now: 3 -2.5 10.5 10 -0.5 11.5 20 -1.5 12.5 

Answer 2

First of all, you should understand that std::nth_element already describes the partition you described. It finds the N ^th element as expected, but it also breaks the data into two parts - all elements smaller than the element you found will be in the lower places in the collection and all the larger elements on the right.

Personally, I think I would do something differently: if you still need the original data order, but also want it to be sorted in some other order, create a sorted index and leave the original data alone. Given that your source data (apparently) was in std::vector , I personally just put the indexes on the index (adding new elements to the end of the vector will not invalidate them, as iterators).

 std::vector<int> index(data.size()); template <class T> struct cmp { T const &data; public: cmp(T const &array) : data(array) {} bool operator()(int a, int b) { return data[a] < data[b]; } }; for (int i=0; i<index.size(); i++) index[i] = i; std::sort(index.begin(), index.end(), cmp(your_data)); 

Then, to use the data in its original order, you simply index the original array / vector, for example your_data[i] . To use the data in sorted order, you use something like your_data[index[i]] instead.

You could, of course, put all this into an index class, so just use the operator[] index class to actually index the source data in sorted order. The cmp class above already shows how to do most of this.