Re: indirect / index sorting with the STL
Joshua Lehrer wrote:
I was challenged to come up with a way to use existing STL algorithms
to sort one vector but given sorting precedence in a separate vector.
An additional constraint is that only O(1) constant external storage
may be used.
In other words, a vector<string> containing "A","B","C" sorted
indirectly given the precedence vector<int> of 22,11,33 would yield a
vector<string> of "B","A","C".
I tried to write my own container class that simulated a real
container but contained references to the two vectors, the target
vector and the index vector. I ran into trouble when I had to
implement operator* on my pointer class because I had no real object
to return a reference to.
Obviously the puzzle is easy if I copy the elements into a vector<
pair<k,v> > and supply my own comparison functor which compares the
pair::second. But this adds too much overhead in the copy/copy back
and violates my constraint of O(1) external storage.
I've come to the conclusion that this can't be done with std::sort,
but is there another algorithm that can help? Aside from rewriting
sort on my own, does anyone have another suggestion?
You are a bit unclear about whether both vectors should be sorted in
parallel (this seems to be what you attempted) or whether just the second is
to be modified and the first should stay the same. The following does sort
_both_ vectors based upon the comparison from the first. It is faking the
reference that you need as the return type for operator*.
#include <vector>
#include <string>
#include <iostream>
#include <ostream>
#include <iterator>
#include <algorithm>
using std::swap;
template < typename S, typename T >
class fake_pair {
S s_val;
T t_val;
public:
fake_pair ( S const & s, T const & t )
: s_val ( s )
, t_val ( t )
{}
S & first ( void ) {
return ( s_val );
}
S const & first ( void ) const {
return ( s_val );
}
T & second ( void ) {
return ( t_val );
}
T const & second ( void ) const {
return ( t_val );
}
};
template < typename S, typename T >
class fake_pair_ref {
S* s_ptr;
T* t_ptr;
fake_pair_ref ( void );
public:
fake_pair_ref ( S & s_ref, T & t_ref )
: s_ptr ( &s_ref )
, t_ptr ( &t_ref )
{}
S & first ( void ) {
return ( *s_ptr );
}
S const & first ( void ) const {
return ( *s_ptr );
}
T & second ( void ) {
return ( *t_ptr );
}
T const & second ( void ) const {
return ( *t_ptr );
}
fake_pair_ref operator= ( fake_pair<S,T> const & other ) {
this->first() = other.first();
this->second() = other.second();
}
fake_pair_ref operator= ( fake_pair_ref other ) {
this->first() = other.first();
this->second() = other.second();
}
operator fake_pair<S,T> ( void ) {
return ( fake_pair<S,T>( this->first(), this->second() ) );
}
};
struct compare_first {
template < typename X, typename Y >
bool operator() ( X const & lhs, Y const & rhs ) const {
return ( lhs.first() < rhs.first() );
}
};
template < typename Iter1, typename Iter2 >
class fake_pair_iterator {
Iter1 where1;
Iter2 where2;
public:
typedef
fake_pair< typename std::iterator_traits< Iter1 >::value_type,
typename std::iterator_traits< Iter2 >::value_type > value_type;
typedef
fake_pair_ref< typename std::iterator_traits< Iter1 >::value_type,
typename std::iterator_traits< Iter2 >::value_type > reference;
typedef reference * pointer;
typedef typename
std::iterator_traits< Iter1 >::difference_type difference_type;
typedef typename
std::iterator_traits< Iter1 >::iterator_category iterator_category;
fake_pair_iterator ( Iter1 pos1, Iter2 pos2 )
: where1 ( pos1 )
, where2 ( pos2 )
{}
fake_pair_iterator ( void )
: where1 ()
, where2 ()
{}
reference operator* ( void ) {
return ( reference( *where1, *where2 ) );
}
reference operator[] ( difference_type d ) {
return ( *( *this+d ) );
}
fake_pair_iterator operator++ ( void ) {
++ where1;
++ where2;
return ( *this );
}
fake_pair_iterator operator++ ( int ) {
fake_pair_iterator old = *this;
++ where1;
++ where2;
return ( old );
}
fake_pair_iterator operator-- ( void ) {
-- where1;
-- where2;
return ( *this );
}
fake_pair_iterator operator-- ( int ) {
fake_pair_iterator old = *this;
-- where1;
-- where2;
return ( old );
}
fake_pair_iterator operator+= ( difference_type d ) {
where1 += d;
where2 +=d;
return ( *this );
}
fake_pair_iterator operator+ ( difference_type d ) const {
fake_pair_iterator result = *this;
result += d;
return ( result );
}
friend
fake_pair_iterator operator+ ( difference_type d, fake_pair_iterator rhs ) {
return ( rhs + d );
}
fake_pair_iterator operator-= ( difference_type d ) {
where1 += d;
where2 +=d;
return ( *this );
}
fake_pair_iterator operator- ( difference_type d ) const {
fake_pair_iterator result = *this;
result += d;
return ( result );
}
friend
difference_type operator- ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 - rhs.where1 );
}
friend
bool operator< ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 < rhs.where1 );
}
friend
bool operator<= ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 <= rhs.where1 );
}
friend
bool operator> ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 > rhs.where1 );
}
friend
bool operator>= ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 >= rhs.where1 );
}
friend
bool operator== ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 == rhs.where1 );
}
friend
bool operator!= ( fake_pair_iterator lhs, fake_pair_iterator rhs ) {
return ( lhs.where1 != rhs.where1 );
}
};
template < typename Iter1, typename Iter2 >
void parallel_sort ( Iter1 from1, Iter1 to1, Iter2 from2, Iter2 to2 ) {
typedef typename
std::iterator_traits< Iter1 >::value_type value_type1;
typedef typename
std::iterator_traits< Iter2 >::value_type value_type2;
std::sort( fake_pair_iterator< Iter1, Iter2 >( from1, from2 ),
fake_pair_iterator< Iter1, Iter2 >( to1, to2 ),
compare_first() );
}
int main ( void ) {
std::vector< int > i;
i.push_back( 22 );
i.push_back( 11 );
i.push_back( 33 );
std::string s = "abc";
parallel_sort( i.begin(), i.end(), s.begin(), s.end() );
std::cout << s << "\n";
std::copy( i.begin(), i.end(), std::ostream_iterator< int >( std::cout, " " ) );
std::cout << "\n";
}
Best,
Kai-Uwe Bux
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]