index.rst

C++的一个好库。。。现在很流行

   or, if no argument is passed explicitly, to the specified
   default value.

Getting More Realistic
----------------------

Now it's time to put some more realistic defaults in place.  We'll
have to give up our print statements—at least if we want to see the
defaults work—since, the default values of these
parameters generally aren't printable.

Instead, we'll connect local variables to the arguments and use
those in our algorithm:

.. parsed-literal::

  namespace graphs { namespace core
  {
    template <class ArgumentPack>
    void depth_first_search(ArgumentPack const& args)
    {
        *Graph*   g = args[graph];
        *Visitor* v = args[visitor|\ *default-expression*\ :sub:`1`\ ];
        *Vertex*  s = args[root_vertex|\ *default-expression*\ :sub:`2`\ ];
        *Index*   i = args[index_map|\ *default-expression*\ :sub:`3`\ ];
        *Color*   c = args[visitor|\ *default-expression*\ :sub:`4`\ ];

        *…use g, v, s, i, and c to implement the algorithm…*
    }
  }} // graphs::core

We'll insert the `default expressions`_ in a moment, but first we
need to come up with the types *Graph*, *Visitor*, *Vertex*,
*Index*, and *Color*.

The ``binding`` |Metafunction|_
-------------------------------

To compute the type of a parameter we can use a |Metafunction|_
called ``binding``:

.. parsed-literal::

  binding<ArgumentPack, Keyword, Default = void>
  { typedef *see text* type; };

where ``Default`` is the type of the default argument, if any.

For example, to declare and initialize ``g`` above, we could write:

.. parsed-literal::

  typedef typename parameter::binding<
    ArgumentPack,\ **tag::graph**
  >::type Graph;

  Graph g = args[graph];

As shown in the `parameter table`_, ``graph`` has no default, so
the ``binding`` invocation for *Graph* takes only two arguments.
The default ``visitor`` is ``boost::dfs_visitor<>()``, so the
``binding`` invocation for *Visitor* takes three arguments:

.. parsed-literal::

  typedef typename parameter::binding<
    ArgumentPack,\ **tag::visitor,boost::dfs_visitor<>**
  >::type Visitor;

  Visitor v = args[visitor|\ **boost::dfs_visitor<>()**\ ];

Note that the default ``visitor`` is supplied as a *temporary*
instance of ``dfs_visitor``.  Because ``args[…]`` always yields
a reference, making ``v`` a reference would cause it to bind to
that temporary, and immediately dangle.  Therefore, it's crucial
that we passed ``dfs_visitor<>``, and not ``dfs_visitor<>
const&``, as the last argument to ``binding``.

.. Important:: 

   Never pass ``binding`` a reference type as the default unless
   you know that the default value passed to the |ArgumentPack|\ 's
   indexing operator will outlive the reference you'll bind to it.

Sometimes there's no need to use ``binding`` at all.  The
``root_vertex`` argument is required to be of the graph's
``vertex_descriptor`` type, [#vertex_descriptor]_ so we can just
use that knowledge to bypass ``binding`` altogether.

.. parsed-literal::

  typename **boost::graph_traits<Graph>::vertex_descriptor**
    s = args[root_vertex|\ ***vertices(g).first**\ ];

.. _dangling:

.. |Metafunction| replace:: :concept:`Metafunction`

.. _Metafunction: ../../../mpl/doc/refmanual/metafunction.html

Beyond Ordinary Default Arguments
---------------------------------

Here's how you might write the declaration for the ``index_map``
parameter:

.. parsed-literal::

  typedef typename parameter::binding<
      ArgumentPack
    , tag::index_map
    , **typename boost::property_map<Graph, vertex_index_t>::const_type**
  >::type Index;

  Index i = args[index_map|\ **get(boost::vertex_index,g)**\ ];

Notice two capabilities we've gained over what
plain C++ default arguments provide:

1. The default value of the ``index`` parameter depends on the
   value of the ``graph`` parameter.  That's illegal in plain C++:
   
   .. parsed-literal::

     void f(int **graph**, int index = **graph** + 1); // error

2. The ``index`` parameter has a useful default, yet it is
   templated and its type can be deduced when  an ``index``
   argument is explicitly specified by the caller.  In plain C++, you
   can *specify* a default value for a parameter with deduced type,
   but it's not very useful:

   .. parsed-literal::

     template <class Index>
     int f(Index index **= 42**);  // OK
     int y = f();                // **error; can't deduce Index**

Syntactic Refinement
====================

In this section we'll describe how you can allow callers to invoke
``depth_first_search`` with just one pair of parentheses, and to
omit keywords where appropriate.


Describing the Positional Argument Order
----------------------------------------

.. _ParameterSpec:

.. |ParameterSpec| replace:: :concept:`ParameterSpec`

First, we'll need to build a type that describes the allowed
parameters and their ordering when passed positionally.  This type
is known as a |ParameterSpec| (MSVC6.x users see this note__)::

  namespace graphs
  {
    typedef parameter::parameters<
        tag::graph
      , tag::visitor
      , tag::root_vertex
      , tag::index_map
      , tag::color_map
    > dfs_params;
  }

__ `Can't Declare ParameterSpec Via typedef`_

The ``parameters`` template supplies a function-call
operator that groups all its arguments into an |ArgumentPack|.  Any
arguments passed to it without a keyword label will be associated
with a parameter according to its position in the |ParameterSpec|.
So for example, given an object ``p`` of type ``dfs_params``, ::

  p('G', index_map=1)

yields an |ArgumentPack| whose ``graph`` parameter has a value of
``'G'``, and whose ``index_map`` parameter has a value of ``1``.

Forwarding Functions
--------------------
  
Next we need a family of overloaded ``depth_first_search`` function
templates that can be called with anywhere from one to five
arguments.  These *forwarding functions* will invoke an instance of
``dfs_params`` as a function object, passing their parameters
to its ``operator()`` and forwarding the result on to
``core::depth_first_search``:

.. parsed-literal::

  namespace graphs
  {
    template <class A0>
    void depth_first_search(A0 const& a0)
    {
       core::depth_first_search(dfs_params()(a0));
    }

    template <class A0, class A1>
    void depth_first_search(A0 const& a0, A1 const& a1)
    {
       core::depth_first_search(dfs_params()(a0,a1));
    } :vellipsis:`\ 
    .
    .
    .
   `
    template <class A0, class A1, …class A4>
    void depth_first_search(A0 const& a0, A1 const& a1, …A4 const& a4)
    {
       core::depth_first_search(dfs_params()(a0,a1,a2,a3,a4));
    }
  }

That's it!  We can now call ``graphs::depth_first_search`` with
from one to five arguments passed positionally or via keyword.

“Out” Parameters
----------------

Well, that's not *quite* it.  When passing arguments by keyword,
the keyword object's assignment operator yields a temporary
|ArgumentPack| object.  A conforming C++ compiler will refuse to
bind a non-``const`` reference to a temporary, so to support a
keyword interface for all arguments, the overload set above *must*
take its arguments by ``const`` reference.  On the other hand—as
you may recall from the `parameter table`_\ —\ ``color_map`` is an
“out” parameter, so it really should be passed by *non-*\ ``const``
reference.  

A keyword object has a pair of ``operator=`` overloads that ensure
we can pass anything—temporary or not, ``const`` or not—by name,
while preserving the mutability of non-temporaries:

.. parsed-literal::

  template <class A>                  // handles non-const, 
  |ArgumentPack| operator=(A&);       // non-temporary objects

  template <class A>                  // handles const objects
  |ArgumentPack| operator=(A const&); // and temporaries

However, when an “out” parameter is passed positionally, there's no
keyword object involved.  With our ``depth_first_search`` overload
set above, the ``color_map`` will be passed by ``const`` reference,
and compilation will fail when mutating operations are used on it.
The simple solution is to add another overload that takes a
non-``const`` reference in the position of the “out” parameter:

.. parsed-literal::

   template <class A0, class A1, …class A4>
   void depth_first_search(A0 **const&** a0, A1 **const&** a1, …\ A4\ **&** a4)
   {
       core::depth_first_search(dfs_params()(a0,a1,a2,a3,a4));
   }

That approach works nicely because there is only one “out”
parameter and it is in the last position.  If ``color_map`` had
been the first parameter, we would have needed *ten* overloads.  In
the worst case—where the function has five “out” parameters—2\
:sup:`5` or 32 overloads would be required.  This “\ `forwarding
problem`_\ ” is well-known to generic library authors, and the C++
standard committee is working on a proposal__ to address it.  In
the meantime, you might consider using `Boost.Preprocessor`_ to
generate the overloads you need.

.. _`forwarding problem`: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1385.htm

__ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html

.. _`Boost.Preprocessor`: ../../../preprocessor/index.html

If it is impractical for you to generate or write the overloads
that would be required for positional “out” arguments to be passed
directly, you still have the option to ask users to pass them
through |ref|_, which will ensure that the algorithm implementation
sees a non-``const`` reference:

.. parsed-literal::

  depth_first_search(g, v, s, i, **boost::ref(c)**);

.. |ref| replace:: ``boost::ref``

.. _ref: http://www.boost.org/doc/html/reference_wrapper.html

Generating Forwarding Functions with Macros
-------------------------------------------

To remove some of the tedium of writing overloaded forwarding
functions, the library supplies a macro, suitably located in
``boost/parameter/macros.hpp``, that will generate free function
overloads for you::

  BOOST_PARAMETER_FUN(void, depth_first_search, 1, 5, dfs_params);

will generate a family of five ``depth_first_search`` overloads, in
the current scope, that pass their arguments through
``dfs_params``.  Instead of ``core::depth_first_search``, these
overloads will forward the |ArgumentPack| on to a function called
``depth_first_search_with_named_params``, also in the current
scope.  It's up to you to implement that function.  You could
simply transplant the body of ``core::depth_first_search`` into
``depth_first_search_with_named_params`` if you were going to use
this approach.

Note that ``BOOST_PARAMETER_FUN`` only takes arguments by ``const``
reference, so you will have to add any additional overloads
required to handle positional “out” parameters yourself.  We are
looking into providing a more sophisticated set of macros to
address this problem and others, for an upcoming release of Boost.

Controlling Overload Resolution
===============================

The parameters of our templated forwarding functions are completely
general; in fact, they're a perfect match for any argument type
whatsoever.  The problems with exposing such general function
templates have been the subject of much discussion, especially in
the presence of `unqualified calls`__.  Probably the safest thing
to do is to isolate the forwarding functions in a namespace
containing no types [#using]_, but often we'd *like* our functions
to play nicely with argument-dependent lookup and other function
overloads.  In that case, it's neccessary to remove the functions
from the overload set when the passed argument types aren't
appropriate.

__ http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#225

Updating the |ParameterSpec|
----------------------------

This sort of overload control can be accomplished in C++ by taking
advantage of the SFINAE (Substitution Failure Is Not An Error)
rule. [#sfinae]_ You can take advantage of the Parameter library's
built-in SFINAE support by using the following class templates in
your |ParameterSpec|:

.. parsed-literal::

     template< class KeywordTag, class Predicate = *unspecified* >
     struct required;

     template< class KeywordTag, class Predicate = *unspecified* >
     struct optional;

Instead of using keyword tags directly, we can wrap them in
``required`` and ``optional`` to indicate which function parameters
are required, and optionally pass ``Predicate``\ s to describe the
type requirements for each function parameter.  The ``Predicate``
argument must be a unary `MPL lambda expression`_ that, when
applied to the actual type of the argument, indicates whether that
argument type meets the function's requirements for that parameter
position.

.. _`MPL lambda expression`: ../../../mpl/doc/refmanual/lambda-expression.html

For example, let's say we want to restrict ``depth_first_search()`` so that
the ``graph`` parameter is required and the ``root_vertex``
parameter is convertible to ``int``.  We might write:

.. parsed-literal::

  #include <boost/type_traits/is_convertible.hpp>
  #include <boost/mpl/placeholders.hpp>
  namespace graphs
  {
    using namespace boost::mpl::placeholders;

    struct dfs_params
      : parameter::parameters<
            **parameter::required<tag::graph>**
          , parameter::optional<tag::visitor>
          , **parameter::optional<
                tag::root_vertex, boost::is_convertible<_,int>
            >**
          , parameter::optional<tag::index_map>
          , parameter::optional<tag::color_map>
        >
    {};
  }

Applying SFINAE to the Overload Set
-----------------------------------

Now we add a special defaulted argument to each of our
``depth_first_search`` overloads:

.. parsed-literal::

  namespace graphs
  {
    template <class A0>
    void depth_first_search(
        A0 const& a0
      , typename dfs_params::match<A0>::type p = dfs_params())
    {
       core::depth_first_search(**p**\ (a0));
    }

    template <class A0, class A1>
    void depth_first_search(
        A0 const& a0, A1 const& a1
      , typename dfs_params::match<A0,A1>::type p = dfs_params())
    {
       core::depth_first_search(**p**\ (a0,a1));
    } :vellipsis:`\ 
    .
    .
    .
   `
    template <class A0, class A1, …class A4>
    void depth_first_search(
        A0 const& a0, A1 const& a1, …A4 const& A4
      , typename dfs_params::match<A0,A1,A2,A3,A4>::type p = dfs_params())
    {
       core::depth_first_search(**p**\ (a0,a1,a2,a3,a4));
    }
  }


These additional parameters are not intended to be used directly