|
|
Boost : |
Subject: Re: [boost] Abstract STL Container Adaptors
From: Andy Jost (Andrew.Jost_at_[hidden])
Date: 2013-03-18 13:07:41
From: Boost [mailto:boost-bounces_at_[hidden]] On Behalf Of Steven Watanabe
> On 03/18/2013 08:30 AM, Andy Jost wrote:
>>
>> Maybe looking at some code would help clarify the answers to these questions. I have about 300 lines partially implementing an adaptor for std::set using Boost.TypeErasure, plus a list of questions and problems I encountered. Is that too large to put into an email for this list? If so, where can I drop it?
>>
> That shouldn't be too large.
Ok, code is at the end; questions first. I realize many of these questions may be answered in the documentation.
Linux 2.6.9-89.ELlargesmp x86_64
g++ (GCC) 4.5.2
1) Certain functions require a downcast, of sorts. The overload of std::set<T>::insert taking an iterator as hint is an example. Not just any iterator, but one with exactly the right type is needed. Maybe this is what type_erasure::is_same is for, but I haven't looked into it yet.
2) I start getting errors when the mpl::vector of requirements exceeds 20 elements: "error: wrong number of template arguments (21, should be 20)."
As a blind guess, I tried including boost/mpl/vector/vector30.hpp but it doesn't help. I know there's a good chance the answer is in the MPL docs somewhere, but I haven't had a chance to go deeper.
3) I could not implement swap. If item 1 can be resolved, then this could work in the same way. Still, it seems that two any<> objects of the same type should be swappable (though, it is not obvious how that would be expressed). I couldn't find a way to do it.
4) When members are overloaded based on a constant this, I could only use the const-qualified version. So, I can add a requirement for set<T>::clear, but for set<T>::begin, the return value must be specified as const_iterator.
5) BOOST_TYPE_ERASURE_MEMBER cannot be used in a SEQ_FOR_EACH loop, because it uses SEQ_FOR_EACH internally. It would be handy to have a way to declare several members when the namespace path and prefix (e.g., has_) doesn't change, either by passing the z parameter or using another macro.
6) I could never get the bidirectional_iterator concept from TypeErasure working. I didn't find an example. I ended up writing out the requirements myself. Also, that required the use of relaxed and I didn't understand why.
#define BOOST_TYPE_ERASURE_STL_MEMBER(key,name,arity) \
BOOST_TYPE_ERASURE_MEMBER((boost)(type_erasure)(has_##key),name,arity); \
/**/
/* std::allocator */
BOOST_TYPE_ERASURE_STL_MEMBER(address,address,1)
BOOST_TYPE_ERASURE_STL_MEMBER(allocate1,allocate,1)
BOOST_TYPE_ERASURE_STL_MEMBER(allocate2,allocate,2)
BOOST_TYPE_ERASURE_STL_MEMBER(construct,construct,2)
BOOST_TYPE_ERASURE_STL_MEMBER(deallocate,deallocate,2)
BOOST_TYPE_ERASURE_STL_MEMBER(destroy,destroy,1)
/* Iterators */
BOOST_TYPE_ERASURE_STL_MEMBER(begin,begin,0)
BOOST_TYPE_ERASURE_STL_MEMBER(end,end,0)
BOOST_TYPE_ERASURE_STL_MEMBER(rbegin,rbegin,0)
BOOST_TYPE_ERASURE_STL_MEMBER(rend,rend,0)
/* Capacity */
BOOST_TYPE_ERASURE_STL_MEMBER(empty,empty,0)
BOOST_TYPE_ERASURE_STL_MEMBER(max_size,max_size,0)
BOOST_TYPE_ERASURE_STL_MEMBER(size,size,0)
/* Modifiers */
BOOST_TYPE_ERASURE_STL_MEMBER(clear,clear,0)
BOOST_TYPE_ERASURE_STL_MEMBER(erase1,erase,1)
BOOST_TYPE_ERASURE_STL_MEMBER(erase2,erase,2)
BOOST_TYPE_ERASURE_STL_MEMBER(insert1,insert,1)
BOOST_TYPE_ERASURE_STL_MEMBER(insert2,insert,2)
BOOST_TYPE_ERASURE_STL_MEMBER(swap,swap,1)
/* Observers */
BOOST_TYPE_ERASURE_STL_MEMBER(key_comp,key_comp,0)
BOOST_TYPE_ERASURE_STL_MEMBER(value_comp,value_comp,0)
/* Operations */
BOOST_TYPE_ERASURE_STL_MEMBER(count,count,1)
BOOST_TYPE_ERASURE_STL_MEMBER(equal_range,equal_range,1)
BOOST_TYPE_ERASURE_STL_MEMBER(find,find,1)
BOOST_TYPE_ERASURE_STL_MEMBER(lower_bound,lower_bound,1)
BOOST_TYPE_ERASURE_STL_MEMBER(upper_bound,upper_bound,1)
/* Allocator */
BOOST_TYPE_ERASURE_STL_MEMBER(get_allocator,get_allocator,0)
#define BOOST_TYPE_ERASURE_FWD_TYPEDEFS(z,base,name) typedef base::name name;
#define BOOST_TYPE_ERASURE_STL_TYPEDEFS \
(key_type)(key_compare)(value_compare)(allocator_type) \
(iterator)(const_iterator)(reverse_iterator)(const_reverse_iterator) \
BOOST_TYPE_ERASURE_ALLOCATOR_TYPEDEFS \
/**/
#define BOOST_TYPE_ERASURE_ALLOCATOR_TYPEDEFS \
(value_type)(reference)(const_reference)(pointer)(const_pointer) \
(difference_type)(size_type) \
/**/
namespace boost { namespace type_erasure
{
template<typename T> struct allocator_typedefs
{
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef const T* const_pointer;
typedef const T& const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
};
template<typename T, typename Defs = allocator_typedefs<T> >
struct allocator_requirements
: mpl::vector<
copy_constructible<>
, assignable<>
, has_address<typename Defs::pointer(typename Defs::reference)>
, has_address<
typename Defs::const_pointer(typename Defs::const_reference)
>
, has_allocate1<T*(typename Defs::size_type)>
, has_allocate2<T*(typename Defs::size_type,void const *)>
, has_deallocate<void(typename Defs::pointer,typename Defs::size_type)>
, has_max_size<typename Defs::size_type()>
, has_construct<
void(typename Defs::pointer,typename Defs::const_reference)
>
, has_destroy<void(typename Defs::pointer)>
>
{};
template<typename T> struct any_allocator
: any<allocator_requirements<T> >
{
BOOST_PP_SEQ_FOR_EACH(
BOOST_TYPE_ERASURE_FWD_TYPEDEFS
, typename allocator_typedefs<T>
, BOOST_TYPE_ERASURE_ALLOCATOR_TYPEDEFS
)
template<typename Allocator>
any_allocator(Allocator const & allocator)
: any<allocator_requirements<T>, _self>(allocator)
{}
};
template<typename T>
struct compare_requirements
: mpl::vector<
copy_constructible<>
, assignable<>
, callable<bool(T const &, T const &)>
>
{};
template<typename T>
struct any_compare
{
typedef any<compare_requirements<T> > type;
};
template<typename T, typename Reference>
struct input_iterator_requirements
: mpl::vector<
relaxed
, constructible<_self()>
, copy_constructible<>
, assignable<>
, incrementable<>
, dereferenceable<Reference>
, equality_comparable<>
>
{};
template<typename T, typename Reference = T const &>
struct any_input_iterator
{
typedef any<input_iterator_requirements<T,Reference> > type;
};
template<typename T, typename Reference>
struct bidirectional_iterator_requirements
// : bidirectional_iterator<T, Reference, Difference>
: mpl::vector<
relaxed
, constructible<_self()>
, copy_constructible<>
, assignable<>
, incrementable<>
, decrementable<>
, dereferenceable<Reference>
, equality_comparable<>
>
{};
template<typename T, typename Reference = T&>
struct any_bidirectional_iterator
{
typedef any<bidirectional_iterator_requirements<T,Reference> > type;
};
template<typename T, typename Allocator = any_allocator<T> >
struct any_set_typedefs
{
typedef T value_type;
typedef T key_type;
typedef typename any_compare<T>::type key_compare;
typedef typename any_compare<T>::type value_compare;
typedef Allocator allocator_type;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::difference_type difference_type;
typedef typename allocator_type::size_type size_type;
typedef typename
any_bidirectional_iterator<value_type,reference>::type
iterator;
typedef typename
any_bidirectional_iterator<value_type,const_reference>::type
const_iterator;
typedef iterator reverse_iterator;
typedef const_iterator const_reverse_iterator;
};
template<typename T, typename Allocator
, typename Defs = any_set_typedefs<T,Allocator>
>
struct set_requirements
: mpl::vector<
constructible<_self()>
, copy_constructible<>
, assignable<>
/* Iterators */
, has_begin<typename Defs::const_iterator()>
, has_end<typename Defs::const_iterator()>
, has_rbegin<typename Defs::const_reverse_iterator()>
, has_rend<typename Defs::const_reverse_iterator()>
/* Capacity */
, has_empty<bool()>
, has_max_size<typename Defs::size_type()>
, has_size<typename Defs::size_type()>
/* Modifiers */
, has_clear<void()>
, has_insert1<
std::pair<typename Defs::const_iterator,bool>(
typename Defs::value_type const &
)
>
// The next version of insert does not compile.
// , has_insert2<
// typename Defs::const_iterator(
// typename Defs::const_iterator
// , typename Defs::value_type const &
// )
// >
, has_insert2<
void(
typename any_input_iterator<T>::type
, typename any_input_iterator<T>::type
)
>
/* Observers */
, has_key_comp<typename Defs::key_compare()>
, has_value_comp<typename Defs::value_compare()>
/* Operations */
, has_count<typename Defs::size_type(typename Defs::const_reference)>
, has_equal_range<
std::pair<
typename Defs::const_iterator
, typename Defs::const_iterator
>(typename Defs::value_type const &)
>
, has_find<
typename Defs::const_iterator(typename Defs::value_type const &)
>
, has_lower_bound<
typename Defs::const_iterator(typename Defs::value_type const &)
>
, has_upper_bound<
typename Defs::const_iterator(typename Defs::value_type const &)
>
/* Allocator */
// , has_get_allocator<typename Defs::allocator_type()>
>
{};
template<typename T, typename Allocator = any_allocator<T> >
struct any_set_adaptor
: any<set_requirements<T,Allocator>, _self &>
{
// Declare typedefs.
typedef any_set_typedefs<T,Allocator> _typedefs;
BOOST_PP_SEQ_FOR_EACH(
BOOST_TYPE_ERASURE_FWD_TYPEDEFS
, typename _typedefs
, BOOST_TYPE_ERASURE_STL_TYPEDEFS
)
template<typename Set>
any_set_adaptor(Set & set)
: any<set_requirements<T,Allocator>, _self &>(set)
{}
#if 0
// It appears there is no swap for type_erasure::any, either as a member or
// assocaited function.
void swap(any_set_adaptor & arg)
{
typedef any<set_requirements<T,Allocator>, _self &> base_type;
swap(
static_cast<base_type &>(*this), static_cast<base_type &>(arg)
);
}
#endif
};
}}
#undef BOOST_TYPE_ERASURE_FWD_TYPEDEFS
#undef BOOST_TYPE_ERASURE_STL_TYPEDEFS
#undef BOOST_TYPE_ERASURE_ALLOCATOR_TYPEDEFS
#undef BOOST_TYPE_ERASURE_STL_MEMBER
// main.cpp
typedef boost::type_erasure::any_set_adaptor<int> set_type;
void my_algorithm(set_type const & set)
{
std::set<int> foo(set.begin(), set.end());
set_type::iterator it;
std::cout << "7 in set? " << bool(set.count(7)) << std::endl;
std::cout << "empty? " << set.empty() << std::endl;
std::cout << "is 3<4? " << set.key_comp()(3,4) << std::endl;
std::cout << "nameof(reference) = " << typeid(set_type::reference).name() << std::endl;
std::cout << sizeof(set_type) << std::endl;
}
int main()
{
any_allocator<int> a = std::allocator<int>();
int x;
std::cout << a.address(x) << std::endl;
std::set<int> set0;
set0.insert(4);
my_algorithm(set0);
return 0;
}
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk