Boost logo

Boost :

From: Christian Engström (christian.engstrom_at_[hidden])
Date: 2004-02-20 07:30:38


Is the following design valid, and if so, would it make a useful
addition to the Boost library? I enclose a draft implementation, and
look forward to any comments.

/Christian
- - -

It can quite often be of interest to convert a program that uses a
direct container into using an indirect container of smart pointers to
the objects instead, either just temporarily to see what happens to
performance, or permanently if it turns out to be beneficial.
Unfortunately, this normally means that the program has to be modified
in many different places, even for programs that are not affected as
such by the slightly different semantics that indirect containers have.

The proxy indirect container header file makes it possible to switch
between direct and indirect containers by changing a single typedef in
any such program.

For example, the following test program was modified to use an indirect
vector instead of a direct one by just changing the type declaration
from std::vector<person> to proxy_vector<person>::self.

//===================================================================

#include <boost/operators.hpp>
#include "proxy.hpp"

int calls_to_copy_constructor = 0;

//===================================================================
class person : boost::totally_ordered<person>
//-------------------------------------------------------------------
{
public:
   string name;
   int age;

   person() {}
   person(const string& in_name, int in_age);
   person(const person& other) : name(other.name), age(other.age) {
     ++calls_to_copy_constructor;
   }

   // Compares first name, then age
   friend bool operator== (const person& a, const person& b);
   friend bool operator< (const person& a, const person& b);

   bool read(istream& in_file);
};

ostream& operator<< (ostream& out_file, const person& x);

//===================================================================
int main (int argc, char* argv[])
//-------------------------------------------------------------------
{
   person a_person;
   person someone_special("Alice", 27);
   ifstream in_file("test_proxy.in");

// typedef std::vector<person> buf_type; // <----
   typedef proxy_vector<person>::self buf_type; // <----

   buf_type buf(5, person("Undefined", -1));
   buf.front() = person("First", 1);
   *(buf.begin() + 1) = person("Second", 2);
   buf[2] = person("Third", 3);
   (buf.begin() + 3)->name = "Incomplete";

   while (a_person.read(in_file)) {
     buf.push_back(a_person);
   }

   std::sort(buf.begin(), buf.end());

   for (buf_type::iterator it = buf.begin(); it != buf.end(); ++it) {
     cout << *it;
     if (it->age < 0) cout << " Not a proper age";
     if (*it == someone_special) cout << " Someone special";
     if (it != buf.begin() && (*it == *(it – 1)))
       cout << " Duplicate record";
     cout << endl;
   }

   buf_type::iterator end_it = std::unique(buf.begin(), buf.end());
   cout << "\nNumber of unique records: " << (end_it - buf.begin());

   cout << "\n\nCalls to 'person's copy constructor: "
        << calls_to_copy_constructor << endl;
   return 0;
}

//===================================================================

So how does this work?

First of all, the declaration proxy_vector<T>::self is short for

proxy_container< std::vector< proxy<T> > >

There are convenience templates like this for the basic container types
in STL, but by using the general form the proxy container adaptor can be
used on any container that has an STL compliant interface.

Class proxy

At the very center of the design is the proxy template class.

A proxy<T> object is a smart pointer that has a boost::shared_ptr<T> as
its only data member. It constructs, assigns, and takes responsibility
for deleting the object in the same way as a shared_ptr.

It does not support any pointer arithmetic, however, so the ++ and --
operators are undefined.

Without pointer arithmetic, there is very little use for the comparison
operators as they are defined for shared_ptr, so these are instead given
the semantics of element_compare, which means that they compare the two
objects as such rather than the pointers. (There is a conversion
function to shared_ptr that can be used to test the pointers as such if
necessary.)

With these definitions, we can use the STL algorithms directly on any
Container< proxy<T> >, and they will produce the same results as they
would for a Container<T>. This applies both to algorithms like
std::sort, which depends on the < operator for comparisons, and
algorithms like unique, which relies on the == operator.

The proxy class also contains an implicit conversion operator from
proxy<T> to T&. This means that we can use a proxy<T> as the actual
parameter to any function that expects a T for input or output, or, to
put it another way, that the proxy is automatically “cashed in” for a T
object as soon as this is required.

In particular, this means that we can copy T objects from a Container<
proxy<T> > into T variables, in exactly the same way as if it had been a
Container<T>, since the proxy<T> object that the iterator delivers will
be automatically converted to a T if it is assigned to a T variable. If
we assign it to a proxy<T> variable, it will of course remain a proxy.

To handle assignments to proxy variables, the default assignment
operator is supplemented by operator=(const T&). This operator will
create a proxy that points at a new copy of the T object, and assign it
to the left hand variable.

This means that we now have a Container< proxy<T> > that behaves like a
Container<T> for comparisons, and when we retrieve whole objects from
the container.

Class proxy_iterator

To get operator-> working in the same way as for a Container<T>, we
define the classes proxy_iterator and const_proxy_iterator.

A proxy_iterator is publicly derived from the iterator of the underlying
Container< proxy<T> >. It works just like standard iterator in all
respects except one, which is that operator-> does a double
dereferencing, so that it will deliver a pointer to the T object itself.
This lets us use the -> operator in the same way that we would with a
direct container. operator* is not changed, however, and retains its
single dereferencing semantics.

Are we really allowed to define these operators like this? --Yes, we are.

While it is true that this means that the semantics will be different
for (*x).y and x->y, this does not affect the STL algorithms in any way,
since they don’t make any use of the -> operator. (How could they, when
they’re supposed to work on the built-in types as well?)

The proxy iterators can be mixed freely with the underlying standard
iterators, since the derived-to-base-class conversion will convert in
one direction, and the proxy iterators have have a conversion
constructor that converts in the other direction. Since the compiler
will prefer a derived-to-base conversion over a user-defined conversion,
the ambiguity problems that are normally associated with having two
types that can be implicitly converted in both directions are eliminated.

Class proxy_container

The class proxy_container, finally, inherits from the underlying
Container< proxy<T> > and overrides the definitions for iterator and
const_iterator so that the proxy iterators are used instead. It also
redefines the standard container member functions that return an
iterator so that they return the appropriate proxy iterator.

In order to be able to insert T objects directly into the proxy
container, the class proxy_container also redefines all members that
insert an object into the container so that there are two versions of
each function: one that takes a proxy<T> as input and inserts a new
proxy that points at the same object, and one that takes a T object and
inserts a proxy that points at a newly created copy of the object.

Taken together, these classes let us emulate the interface of a
Container<T> with something that is actually an indirect container.
Since it is only a single type declaration that has to be changed to
switch between direct and indirect containers, it becomes practical to
do this for testing purposes. The indirect containers still retain the
full interface of a traditional container of smart pointers, so the
additional capabilities of an indirect container are available in the
usual way.

- - -

I have uploaded the full source code for the draft implementation, as
well as and the test program shown here, to the files section at Yahoo,
and I have tested it with MSVC6 and gcc 3.3 on Windows XP.

For MSVC6 there is the problem that the implementation of
std::vector::iterator is just a plain pointer and not a standards
compliant iterator, so proxy_vector uses a deque rather than a vector as
a workaround.

File proxy.hpp:
(slightly abridged)

//==================================================================
// 20-feb-2004 Christian Engström (christian.engstrom_at_[hidden])
//------------------------------------------------------------------
#include <vector>
#include <deque>
#include <list>
#include <boost/smart_ptr.hpp>

//==================================================================
// 'proxy'
//------------------------------------------------------------------
template <class T>
class proxy
{
private:
   typedef proxy<T> self;
   boost::shared_ptr<T> m_sp;

public:
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Types
   typedef T element_type; // "Inherited" from 'boost::shared_ptr'
   typedef T value_type;

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Constructors
   proxy() {}
   template<class Y> proxy(const proxy<Y>& other) :
m_sp(other.as_shared_ptr()) {}
   template<class Y> explicit proxy(const boost::shared_ptr<Y>& other) :
m_sp(other) {}
   template<class Y> explicit proxy(const boost::weak_ptr<Y>& other) :
m_sp(other) {}
   template<class Y> explicit proxy(std::auto_ptr<Y>& other) :
m_sp(other) {}
   template<class Y> explicit proxy(Y* other) :
m_sp(other) {}

   // Assignment
   self& operator=(const self& other) {m_sp = other.m_sp; return *this;}
   self& operator=(const T& other) {*this = proxy<T>(new T(other));
return *this;}

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Conversions
   operator T&() const {return **this;} // Implicit
conversion to T
   bool is_null() const {return !m_sp;}

   boost::shared_ptr<T>& as_shared_ptr() {return m_sp;}
   const boost::shared_ptr<T>& as_shared_ptr() const {return m_sp;}

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Comparisons are made on the value, never the pointer.
   bool operator== (const self& other) const {return **this == *other;}
   bool operator!= (const self& other) const {return **this != *other;}
   bool operator< (const self& other) const {return **this < *other;}
   bool operator> (const self& other) const {return **this > *other;}
   bool operator<= (const self& other) const {return **this <= *other;}
   bool operator>= (const self& other) const {return **this >= *other;}

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Dereferencing
   T& operator*() const {return *m_sp;}
   T* operator->() const {return m_sp.get();}
   T* get() const {return m_sp.get();}
   T* as_ptr() const {return m_sp.get();}
};

//==================================================================
// 'proxy_iterator'
//------------------------------------------------------------------
template <class MutableBaseIterator>
class proxy_iterator : public MutableBaseIterator
{
private:
   typedef proxy_iterator<MutableBaseIterator> self;
   typedef MutableBaseIterator base;
   typedef typename base::value_type::element_type T;

public:
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Types
   typedef typename base::difference_type difference_type;

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Constructors
   proxy_iterator() {}
   proxy_iterator(const MutableBaseIterator& it) : base(it) {}

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Standard operators for iterators
   T* operator-> () {return (**this).get();} // Indirect

   self& operator++ () {base::operator++ (); return *this;}
   self& operator-- () {base::operator-- (); return *this;}
   self operator++ (int) {return base::operator++ (0);}
   self operator-- (int) {return base::operator-- (0);}

   self& operator+= (difference_type n) {base::operator+= (n); return
*this;}
   self& operator-= (difference_type n) {base::operator-= (n); return
*this;}
   self operator+ (difference_type n) const {return base::operator+ (n);}
   self operator- (difference_type n) const {return base::operator- (n);}

   friend self operator+ (difference_type n, self x) {return x + n;}
   friend difference_type operator- (self x, self y) {return base(x) -
base(y);}
};

//==================================================================
// 'const_proxy_iterator'
//------------------------------------------------------------------
{
   // Analagous to proxy_iterator, and with a conversion constructor
from proxy_iterator.
   ...
};

//==================================================================
// 'proxy_container'
//------------------------------------------------------------------
template <class BaseProxyContainer>
class proxy_container : public BaseProxyContainer
{
private:
   typedef proxy_container self;
   typedef BaseProxyContainer base;
   typedef typename BaseProxyContainer::value_type value_type;
   typedef typename BaseProxyContainer::value_type::element_type T;

public:
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Constructors
   proxy_container() {}
   proxy_container(const base& c) : base(c) {}

   template <class InputIterator>
   proxy_container(InputIterator first, InputIterator last) :
base(first, last) {}

   explicit proxy_container(typename base::size_type n, const
value_type& x = value_type())
     : base(n, x) {}

   proxy_container(typename base::size_type n, const T& x) {
     for (typename base::size_type i = 0; i < n; ++i) {
       push_back(proxy<T>(new T(x)));
     }
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Iterators redefined
   typedef proxy_iterator<typename base::iterator> iterator;
   typedef const_proxy_iterator<typename base::iterator, typename
base::const_iterator> const_iterator;

   typedef std::reverse_iterator<iterator> reverse_iterator;
   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Container members that either return an iterator or take a
value_type parameter (or both)
   iterator begin() {return base::begin();}
   const_iterator begin() const {return base::begin();}
   iterator end() {return base::end();}
   const_iterator end() const {return base::end();}

   reverse_iterator rbegin() {return base::rbegin();}
   const_reverse_iterator rbegin() const {return base::rbegin();}
   reverse_iterator rend() {return base::rend();}
   const_reverse_iterator rend() const {return base::rend();}

   void push_front(const value_type& x) {base::push_front(x);}
   void push_front(const T& x) {base::push_front(proxy<T>(new T(x)));}

   void push_back(const value_type& x) {base::push_back(x);}
   void push_back(const T& x) {base::push_back(proxy<T>(new T(x)));}

   iterator insert(iterator position, const value_type& x)
     {return base::insert(x);}
   iterator insert(iterator position, const T& x)
     {return base::insert(position, proxy<T>(new T(x)));}
   void insert(iterator position, typename base::size_type n, const
value_type& x)
      {base::insert(position, n, x);}
   void insert(iterator position, typename base::size_type n, const T& x)
     ; // Not yet implemented
   template<typename InputIterator>
   void insert(iterator position, InputIterator first, InputIterator last)
     {base::insert(position, first, last);}

   iterator erase(iterator position) {return base::erase(position);}
   iterator erase(iterator first, iterator last) {return
base::erase(first, last);}

   void resize(typename base::size_type new_size, const value_type& x)
      {base::resize(new_size, x);}
   void resize(typename base::size_type new_size, const T& x)
     ; // Not yet implemented

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Special list operations
   void remove(const value_type& value) {base::remove(value);}
   void remove(const T& value); // Not yet implemented
};

//==================================================================
// The standard contaiers
//------------------------------------------------------------------

template <class T> struct proxy_vector
#if !defined(BOOST_MSVC_STD_ITERATOR)
   {typedef proxy_container< std::vector< proxy<T> > > self;};
#else
   {typedef proxy_container< std::deque< proxy<T> > > self;}; // MSVC
workaround
#endif

template <class T> struct proxy_deque
   {typedef proxy_container< std::deque< proxy<T> > > self;};

template <class T> struct proxy_list
   {typedef proxy_container< std::list< proxy<T> > > self;};

// Associative containers are not yet implemented


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk