Subject: [Boost-bugs] [Boost C++ Libraries] #6250: allow sorting through an adaptor
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-12-10 22:15:54
#6250: allow sorting through an adaptor
-----------------------------------+----------------------------------------
Reporter: giecrilj@… | Owner: dave
Type: Feature Requests | Status: new
Milestone: To Be Determined | Component: iterator
Version: Boost 1.48.0 | Severity: Problem
Keywords: |
-----------------------------------+----------------------------------------
The following code does not compile because the transform adaptor offers a
proxy reference that cannot be modified:
{{{
#!c++
#include <iostream>
#include <boost/array.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/bind.hpp>
#include <boost/range/algorithm/sort.hpp>
struct underlying { int m_; };
int main (int, char *[]) {
enum LocalParam { BASE = 073, VALUE = 030 };
typedef ::boost ::array < underlying, +BASE - 01 > mycont; mycont v;
for
(::boost ::range_iterator < mycont >:: type p ((::boost ::begin (v)));
p < ::boost ::end (v); ++p)
p -> m_ = p == ::boost ::begin (v)? +VALUE: p [-01] .m_ * VALUE %
BASE;
::boost ::copy
(v
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_,
_1)),
::std ::ostream_iterator
< int, ::std ::istream ::char_type >
(::std:: cout, " ")); ::std ::cout << '\n';
::boost ::sort
(v
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_,
_1)));
::boost ::copy
(v
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_,
_1)),
::std ::ostream_iterator
< int, ::std ::istream ::char_type >
(::std:: cout, " "));
return (::std ::cout << '\n') .flush ()? +EXIT_SUCCESS: +EXIT_FAILURE; }
}}}
This is a deficiency because, when you have relational data packaged in a
container, you often wish to create various indices based on various
aspects of the data. This is currently unsupported by Boost, except for
Multi-Index, but Multi-Index does not allow you to create a detached
index; instead, it insists on maintaining all indices dynamically all the
time, which is not always necessary and it brings a performance penalty
compared to sorting static data.
I have implemented the missing adaptor and called it '''shufflebase''';
when applied to an adaptor, it allows the sort algorithm to rearrange the
''original container'' based on ''the ordering of the adaptor''.
Here is the adaptor code; note that it does not carry any algorithm, only
type juggling and general logistics:
{{{
#!c++
#include <boost/range/iterator_range.hpp> /* boost:: iterator_range
*/
#ifndef BOOST_RANGE_ADAPTOR_SHUFFLEBASE_DEFINED
#if 1
namespace boost {
/*
the following declarations are used in namespace adaptors;
they are here to keep the namespace in one piece */
#if 2
namespace traits { template < class P_I > struct shufflebase; }
#endif /* &boost.traits */
template < class P_I > class shufflebase_iterator;
#if 2
namespace adaptors {
/* a forward declaration for operator | */
template < class P_R > struct shufflebase_range;
#if 3
namespace detail
{ struct /* tag enabler for operator | */ shufflebase_forwarder {};
template < class P_R >
inline struct shufflebase_range < P_R const >
/* applies the shufflebase adaptor to a range */
operator | (P_R const &p_r, struct detail:: shufflebase_forwarder );
}
#endif /* &boost.adaptors.detail */
#if 3
namespace /* static */ {
detail :: shufflebase_forwarder const
/* the formal parameter for operator | */
(&shufflebase) ((detail ::shufflebase_forwarder ())); }
#endif /* &boost.adaptors.static */
#if 3
namespace traits { template < class P_T > struct shufflebase_range; }
#endif /* &boost.adaptors.traits & */
#if 3
template < class P_R >
/* applies shufflebase_iterator to the range */
struct shufflebase_range
:public traits ::shufflebase_range < P_R > ::base {
public:
inline shufflebase_range (P_R &p_r);
private: typedef traits ::shufflebase_range < P_R > traits;
private: typedef typename traits ::base base;
public: typedef typename traits ::iterator iterator; };
#endif /* #boost.adaptors.shufflebase_range */
#if 3
namespace traits {
#if 4
template < class P_R >
/* typedefs for shufflebase_range proper */ struct shufflebase_range
{ typedef
::boost :: shufflebase_iterator
< typename ::boost ::range_iterator < P_R > ::type > iterator;
typedef struct ::boost ::iterator_range < iterator > base; };
#endif /* #boost.adaptors.traits.shufflebase_range */
}
#endif /* &boost.adaptors.traits */
}
#endif /* &boost.adaptors */
#if 2
template < class P_I >
/*
Behaves transparently when applied to an adapted iterator
except that assignments are possible and apply to the underlying base */
class shufflebase_iterator
:public /* iterator faciade */ traits:: shufflebase < P_I >::
base_type
{
public:
/* constructs from an adapted iterator */
inline shufflebase_iterator (P_I const &);
public:
/* inherited */ typedef typename shufflebase_iterator ::reference
reference;
public: /* returns a proxy reference */
inline
reference
/* safety net: exclude application of default operator = to temporary */
const
operator* () const;
public:
/* inherited */ typedef typename shufflebase_iterator ::value_type
value_type;
public: /* assigns the value to the base element, bypassing the adaptor
*/
inline void assign (value_type const &p_v) const;
public:
/* bookkeeping */
typedef typename traits:: shufflebase < P_I >:: base_type inherited; };
#endif /* #boost.shufflebase_iterator */
#if 2
namespace detail { template < class P_I > class shufflebase_reference;
#if 3
template < class P_I >
/*
Stores a value of an iterator.
This class plays a double duty:
it stores the base value for assigning to a reference
and it caches the adapted value for comparisons.
This causes some memory overhead
that I believe is unavoidable
without knowing the details of the managed adaptor.
Moreover, caching the adapted value may speed things up a bit.
This class is necessary
because the sorting algorithm puts some values aside for later use. */
class shufflebase_value
{
public: /* bookkeeping */ typedef P_I base_type;
public: /* construct from a reference */
inline
shufflebase_value (class shufflebase_reference < base_type > const
&p_r);
public: /* the adapted value type */
typedef typename ::std ::iterator_traits < base_type > ::value_type
adapted;
public: /* compares as adapted */
inline operator adapted const &() const;
private: /* the adapted value */ adapted m_adapted;
public: /* the base value type */
typedef typename traits ::shufflebase < base_type > ::base_value
base_value;
private: /* the base value */ base_value m_base;
public:
/*
returns the base value for assignment
(the adapter is meant to affect the base container, remember? */
inline base_value const &base () const; };
#endif /* #boost.detail.shufflebase_value */
#if 3
template < class P_I >
/*
A proxy class serving as reference type for shufflebase_iterator.
Implicitly converts to the adapted reference for comparisons.
Assignment affects the base object instead.
*/
class shufflebase_reference
{
public: /* bookkeeping */ typedef P_I base_type;
public: /* the adapted reference type */ typedef
typename ::std ::iterator_traits < base_type > ::reference reference;
public: /* compares as adapted */
inline operator reference const () const;
public:
/* the adapted value type */
typedef class shufflebase_value < base_type > value_type;
public: /* assigned value goes to base */
inline
shufflebase_reference const
&operator= (value_type const &p_v) const;
public: /* constructor */ inline
shufflebase_reference (shufflebase_iterator < base_type > const &);
private:
/* the proxied iterator */
shufflebase_iterator < base_type > const &m_ref;
public: /* extract the base value for assigning to a value object */
inline
typename
::std ::iterator_traits < typename base_type:: base_type > ::value_type
const
&base () const;
private:
/* references are not assignable */
void operator = (shufflebase_reference const &); };
#endif /* #boost.detail.shufflebase_reference */
}
#endif /* &boost.detail */
#if 2
namespace traits {
#if 3
template < class P_I >
/* contains typedefs for shufflebase_iterator */ struct shufflebase
{
/* bookkeeping */ typedef P_I iterator;
/* the base type for shufflebase_iterator */
typedef ::boost ::iterator_adaptor
<
class shufflebase_iterator < iterator >, iterator,
class detail:: shufflebase_value < iterator >,
::boost:: use_default,
class detail:: shufflebase_reference < iterator >
> base_type;
/* the base value */ typedef
typename
::std ::iterator_traits < typename iterator ::base_type >:: value_type
base_value;
/*
The proper place to define base_value would be class shufflebase_value;
however, this type is shared by other auxiliary classes;
they depend on each other, causing the compiler to fail. */ };
#endif /* #boost.traits.shufflebase */
}
#endif /* &boost.traits */
}
#endif /* &boost */
#define BOOST_RANGE_ADAPTOR_SHUFFLEBASE_DEFINED
#endif
#ifndef BOOST_RANGE_ADAPTOR_SHUFFLEBASE_IMPLEMENTED
#if 1
namespace boost {
#if 2
namespace adaptors {
#if 3
namespace detail {
#if 4
template <class P_R >
inline struct shufflebase_range < P_R const >
operator | (P_R const &p_r, shufflebase_forwarder)
{ return shufflebase_range < P_R const > (p_r); }
#endif /* !boost.adaptors.shufflebase_range.operator| */
}
#endif /* &boost.adaptors.detail */
#if 3
template < class P_R >
inline shufflebase_range < P_R > ::shufflebase_range (P_R &p_r)
:base (iterator (::boost ::begin (p_r)), iterator (::boost ::end (p_r)))
{}
#endif /* !boost.adaptors.shufflebase_range.shufflebase_range */
}
#endif /* &boost.adaptors */
#if 2
template < class P_I >
inline typename shufflebase_iterator < P_I > ::reference const
shufflebase_iterator < P_I > ::operator * () const { return *this; }
#endif /* !boost.shufflebase_iterator.operator * */
#if 2
namespace detail {
#if 3
template < class P_I >
inline shufflebase_reference < P_I > ::operator reference const ()
const
{ return *this -> m_ref. base (); }
#endif /* !boost.detail.shufflebase_reference::reference */
#if 3
template < class P_I >
inline shufflebase_reference < P_I > const
&shufflebase_reference < P_I > ::operator = (value_type const &p_v)
const
{ this -> m_ref .assign (p_v); return *this; }
#endif /* !boost.detail.shufflebase_reference::operator = */
#if 3
template < class P_I >
inline shufflebase_reference < P_I > ::shufflebase_reference
(shufflebase_iterator < P_I > const &p_ref) :m_ref (p_ref) {}
#endif /* !boost.detail.shufflebase_reference.shufflebase_reference */
#if 3
template < class P_I >
inline shufflebase_value < P_I > ::shufflebase_value
(class shufflebase_reference < P_I > const &p_r)
:m_adapted (p_r), m_base (p_r. base ()) {}
#endif /* !boost.detail.shufflebase_value.shufflebase_value */
#if 3
template < class P_I >
inline shufflebase_value < P_I >:: operator adapted const & () const
{ return this -> m_adapted; }
#endif /* !boost.detail.shufflebase_value.adapted & */
#if 3
template < class P_I >
inline
typename ::std ::iterator_traits < typename P_I ::base_type > ::value_type
const
&shufflebase_reference < P_I > :: base () const
{ return *this -> m_ref .base () .base (); }
#endif /* !boost.detail.shufflebase_reference.base */
#if 3
template < class P_I >
typename shufflebase_value < P_I > ::base_value const
&shufflebase_value < P_I > ::base () const { return this -> m_base; }
#endif /* !boost.detail.shufflebase_value.base */
}
#endif /* &boost.detail */
#if 2
template < class P_I >
inline shufflebase_iterator < P_I >:: shufflebase_iterator (P_I const
&p_i)
:inherited (p_i) { }
#endif /* !boost.shufflebase_iterator. */
#if 2
template < class P_I >
inline void shufflebase_iterator < P_I > ::assign (value_type const &p_v)
const
{ *this -> base (). base () = p_v. base (); }
#endif /* !boost.shufflebase_iterator.assign */
}
#endif /* &boost */
#define BOOST_RANGE_ADAPTOR_SHUFFLEBASE_IMPLEMENTED
#endif
}}}
Having this, the following code becomes valid:
{{{
#!c++
#include <iostream>
#include <boost/array.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/bind.hpp>
#include <boost/range/algorithm/sort.hpp>
struct underlying { int m_; };
int main (int, char *[]) {
enum LocalParam { BASE = 073, VALUE = 030 };
typedef ::boost ::array < underlying, +BASE - 01 > mycont; mycont v;
for
(::boost ::range_iterator < mycont >:: type p ((::boost ::begin (v)));
p < ::boost ::end (v); ++p)
p -> m_ = p == ::boost ::begin (v)? +VALUE: p [-01] .m_ * VALUE %
BASE;
::boost ::copy
(v
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_,
_1)),
::std ::ostream_iterator
< int, ::std ::istream ::char_type >
(::std:: cout, " ")); ::std ::cout << '\n';
::boost ::sort
(v
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_, _1))
| ::boost ::adaptors ::shufflebase);
::boost ::copy
(v
| ::boost ::adaptors ::transformed (::boost ::bind (&underlying ::m_,
_1)),
::std ::ostream_iterator
< int, ::std ::istream ::char_type >
(::std:: cout, " "));
return (::std ::cout << '\n') .flush ()? +EXIT_SUCCESS: +EXIT_FAILURE; }
}}}
and it produces the following output:
24 45 18 19 43 29 47 7 50 20 8 15 6 26 34 49 55 22 56 46 42 5 2 48 31 36
38 27 58 35 14 41 40 16 30 12 52 9 39 51 44 53 33 25 10 4 37 3 13 17 54 57
11 28 23 21 32 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
54 55 56 57 58
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/6250> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:08 UTC