[boost] Any Interest in an Adapter for Sequences of Pointers?

From: Alex Chovanec (achovane_at_[hidden])
Date: 2003-06-11 22:28:57

Sequences of pointers are relatively common, but the semantics for handling
them can be unwieldy.

For instance, suppose you have an std::vector<const Widget *> that you need
to perform some STL algorithm on (possibly a mutating algorithm). You may be
using this instead of an std::vector<Widget> for any number of reasons:

1. You may need to manipulate objects across multiple containers.

2. Widget may be an abstract base class, and the objects you are
manipulating may be instances of different derived classes.

3. Widget objects may be non-copyable.

4. Widget objects may be so large that it is inefficient to copy them, and
it may be cheaper to copy pointers instead.

5. You may not be allowed to rearrange the Widget objects because they are
declared const, or possibly for some other reason.

Whatever your reason for using pointers, handling ranges of them can be
painful. In order to use an STL algorithm that compares Widget objects, you
have to define a custom function object. For example, suppose you wanted to
sort your Widget pointers based on the less-than operator for Widgets, which
you have already defined as follows:

    friend bool operator<(const Widget & lhs, const Widget & rhs);

Now you have to define a special predicate for comparing Widget pointers:

    struct WidgetComp
    {
        bool operator()(const Widget * lhs, const Widget * rhs)
        {
            return (*lhs < *rhs);
        }
    };

Now you can (finally) sort a range of Widget pointers using the following
statement:

    std::vector<Widget *> widget_ptrs_;
    std::sort(widget_ptrs_.begin(), widget_ptrs_().end(), WidgetComp());

But this just gets you a strict weak ordering. In practice, you might also
need an equality comparison. Simply comparing the pointers may be
insufficient, since two pointers can refer to distinct but equal Widget
objects.

Alternatively, you could use something like
boost::iterator_adaptor<std::vector<int *>::iterator,
indirect_iterator_policies>. However,
passing an indirect iterator to std::sort() would cause the underlying
Widget objects to be sorted rather than the pointers. This may not be what
you want. Ideally, you would be able to choose to sort either the pointers
or the objects they refer to.

Using predicates like these on sorted ranges of pointers has another
disadvantage. There is no safeguard to ensure that NULL pointers are not
inserted into the vector.

Also, ranges of Widget pointers are not interoperable with ranges of
Widgets. Thus, you cannot use the following to generate a range of Widget
pointers from a range of Widgets and then sort them:

    std::vector<Widget> widgets_;
    std::vector<Widget *> widget_ptrs_;
    . . .
    // widgets_ and widget_ptrs_ get populated with some values
    . . .
    std::copy(widgets_.begin(), widgets_.end(),
              std::back_inserter(widget_ptrs_));
    std::sort(widget_ptrs_.begin(), widget_ptrs_().end(), WidgetComp());

Instead, you have to use a hand-coded loop:

    std::vector<Widget> widgets_;
    std::vector<Widget *> widget_ptrs_;
    . . .
    // widgets_ and widget_ptrs_ get populated with some values
    . . .
    for (unsigned int i = 0; i < widgets_.size(); ++i)
    {
        widget_ptrs_.push_back(&widgets_[i]);
    }

    std::sort(widget_ptrs_.begin(), widget_ptrs_().end(), WidgetComp());

While this is not horrible, it would be nice if we could have something like
the first syntax.

The class I am proposing is an adapter for a sequence of pointers. Users
would be able to specify the type of object that the pointers refer to,
along with a sequence type (e.g. vector, deque, list).

I would probably want to name the class "permutation," because it would
provide an abstraction that represents a permutation of existing, but not
necessarily contiguously stored objects, and it would have a sequence-like
interface, with all the usual member functions (push_back(), pop_back(),
insert(), erase(), etc.).

This class would not be responsible for allocating or deallocating objects.
It would be up to the user to make sure that a permutation never contains a
dangling pointer.

The underlying sequence would not actually hold pointers. Rather, it would
hold objects that behave much like pointers (I would call them "proxies.")

Here is a snippet of what the source code for the preceding example might
look like:

    std::vector<Widget> widgets_;
    boost::permutation<Widget> widget_perm_;
    . . .
    // widgets_ and widget_perm_ get populated with some values
    . . .
    // place pointers to all the objects in widgets_ into widget_perm_
    std::copy(widgets_.begin(), widgets_.end(),
                 std::back_inserter(widget_perm_));

    // sort the widget pointers based on the less-than operator for
    // class Widget
    std::sort(widgets_.proxy_begin(), widgets_.proxy_end(),
                 std::less<Widget>);

    // alternatively, we could have sorted the underlying objects instead of
    // the pointers with the following function call
    //std::sort(widgets_.begin(), widgets_.end());

The usual iterator and const_iterator allow us to step through the
referenced Widget objects, while the more specialized proxy_iterator allows
us to step through the pointers (proxies) that refer to them. (Note that the
specialized function object
from above is no longer required.)

We can add (remove) a Widget pointer (proxy) to (from) a permutation as
follows:

    Widget my_widget_;
    widget_perm_.insert(perm.proxy_begin(), my_widget_);
    widget_perm_.pop_front();

There are other interesting points. For instance, suppose our permutation
references Widgets_ stored across multiple containers. Then we can perform
something like an STL replace algorithm over this range of objects.
Alternatively, we can perform the same algorithm over the corresponding
range of pointers (proxies). Choosing which way to go is as simple as
choosing the right type of iterator.

    // for each Widget w_ such that (w_ == old_widget_),
    // set w_ = new_widget_
    std::replace(widget_perm_.begin(), widget_perm_.end(), old_widget_,
                 new_widget_);

    // for each pointer p_ such that (p_ == &old_widget_),
    // set p_ = &new_widget_
    std::replace(widget_perm_.proxy_begin(), widget_perm_.proxy_end(),
                 old_widget_, new_widget_);

There are many more possibilities beyond those described here. Does this
sound interesting to anyone????

Please let me know.

Thank you,

Alex