New subject: Proxy indirect container adaptor: 4 claims

20 Feb 2004

      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@glindra.org)
//------------------------------------------------------------------
#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

Proxy --- an indirect container adaptor

Christian Engström

David Abrahams

Christian Engström

David Abrahams

Christian Engström

David Abrahams

Jeff Flinn

Christian Engström

David Abrahams

Christian Engström

David Abrahams

Christian Engström

David Abrahams

Christian Engström

David Abrahams

Christian Engström

David Abrahams

Thorsten Ottosen

tags

participants (4)