Re: [Boost-users] Iterator concept checking

Subject: Re: [Boost-users] Iterator concept checking
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-05-24 13:11:16

On Thu, May 24, 2012 at 8:39 AM, McNamara, Nate <nate.mcnamara_at_[hidden]>wrote:

> **
>
> I'm trying to learn to use BOOST_CONCEPT_CHECK for custom iterators,
> ranges, and containers.  I've built a simple linked list class with an
> iterator (and const_iterator) that, as far as I can tell, satisfies the
> forward traversal iterator requirements.  However, g++ gives the following
> errors:
>
> concept.cpp:81: error: `*' cannot appear in a constant-expression
> concept.cpp:81: error: a call to a constructor cannot appear in a
> constant-expression
> concept.cpp:81: error: template argument 1 is invalid
> concept.cpp:81: error: template argument 1 is invalid
> concept.cpp:82: error: `*' cannot appear in a constant-expression
> concept.cpp:82: error: a call to a constructor cannot appear in a
> constant-expression
> concept.cpp:82: error: template argument 1 is invalid
> concept.cpp:82: error: template argument 1 is invalid
> concept.cpp:83: error: `*' cannot appear in a constant-expression
> concept.cpp:83: error: a call to a constructor cannot appear in a
> constant-expression
> concept.cpp:83: error: template argument 1 is invalid
> concept.cpp:83: error: template argument 1 is invalid
> concept.cpp:84: error: `*' cannot appear in a constant-expression
> concept.cpp:84: error: a call to a constructor cannot appear in a
> constant-expression
> concept.cpp:84: error: template argument 1 is invalid
> concept.cpp:84: error: template argument 1 is invalid
>
> Compiling with -E, lines 81-84 are as follows:
>
> typedef ::boost::concepts::detail::instantiate<
> &::boost::concepts::requirement_<void(*)(boost::concepts::ForwardTraversalIterator<iterator>)>::failed>
> boost_concept_check81;
>
> typedef ::boost::concepts::detail::instantiate<
> &::boost::concepts::requirement_<void(*)(boost::concepts::WritableIterator<iterator>)>::failed>
> boost_concept_check82;
>
> typedef ::boost::concepts::detail::instantiate<
> &::boost::concepts::requirement_<void(*)(boost::concepts::ForwardTraversalIterator<const_iterator>)>::failed>
> boost_concept_check83;
>
> typedef ::boost::concepts::detail::instantiate<
> &::boost::concepts::requirement_<void(*)(boost::concepts::ReadableIterator<const_iterator>)>::failed>
> boost_concept_check84;
>
> That tells me that, regardless of why g++ is having trouble, my iterator
> fails to satisfy the concept somehow.  So I wrote some code (see
> my_naive_check, below) to try to figure out which requirement is failing,
> but my check code is missing the same thing as the iterator, because the
> check code runs fine.
>
> Any pointers much appreciated.
>

Hmmm...the below code (with a slight modification) compiles for me on
MSVC9, Boost 1.49.0.

> // concept.cpp
>
> // What's wrong with the iterators?
>
> #include <cassert>
> #include <cstdlib>
> #include <iostream>
> #include <string>
>
> #include <boost/concept_check.hpp>
> #include <boost/iterator/iterator_concepts.hpp>
> #include <boost/iterator/iterator_facade.hpp>
> #include <boost/lambda/lambda.hpp>
> #include <boost/range/algorithm.hpp>
>
> template <typename T>
> class List {
>   struct Node {
>     Node(const T& value_, Node *next_): value(value_), next(next_) {}
>     T value;
>     Node *next;
>   } *head;
>
> public:
>   List(): head(0) {}
>
>   ~List() {
>     Node *node = head;
>     while (node) {
>       Node *tmp = node->next;
>       delete node;
>       node = tmp;
>     }
>   }
>
>   void push_front(const T& value) { head = new Node(value, head); }
>
>   class iterator:
>   public boost::iterator_facade<iterator,
>                                 T,
>                                 boost::forward_traversal_tag>
>   {
>   public:
>     iterator(): node(0) {}
>
>   private:
>     iterator(Node * const node_): node(node_) {}
>     friend class List;
>
>     friend class boost::iterator_core_access;
>     T& dereference() const { return node->value; }
>     bool equal(const iterator& rhs) const { return node == rhs.node; }
>     void increment() { node = node->next; }
>
>     Node *node;
>   };
>
>   iterator begin() { return iterator(head); }
>   iterator end() { return iterator(); }
>
>   class const_iterator:
>   public boost::iterator_facade<const_iterator,
>                                 const T,
>                                 boost::forward_traversal_tag>
>   {
>   public:
>     const_iterator(): node(0) {}
>     const_iterator(const iterator& old): node(old.node) {}
>
>   private:
>     friend class boost::iterator_core_access;
>     const T& dereference() const { return node->value; }
>     bool equal(const const_iterator& rhs) const { return node == rhs.node;
> }
>     void increment() { node = node->next; }
>
>     const Node *node;
>   };
>
>   const_iterator begin() const { return const_iterator(head); }
>   const_iterator end() const { return const_iterator(); }
>

I don't know where the following concept checking classes are defined, but
from [1], it appears you should be using
boost_concepts::ForwardTraversalConcept, etc. (badly named, IMHO, but
that's what I'm finding in the documentation).

> BOOST_CONCEPT_ASSERT((boost::concepts::ForwardTraversalIterator<iterator>));
>   BOOST_CONCEPT_ASSERT((boost::concepts::WritableIterator<iterator>));
>
> BOOST_CONCEPT_ASSERT((boost::concepts::ForwardTraversalIterator<const_iterator>));
>
> BOOST_CONCEPT_ASSERT((boost::concepts::ReadableIterator<const_iterator>));
> };
>
> /*
> ForwardTraversalIterator must be
>   SinglePassIterator
>     IncrementableIterator
>       Assignable
>       Copy Constructible
>       &r == &++r
>       r++
>       *r++
>     ==
>     !=
>     difference_type
>   DefaultConstructible
>   iterator_traversal<X>::type => forward_traversal_tag
> */
> void my_naive_check(List<std::string>& words) {
>   typedef List<std::string>::iterator It;
>   It it1 = words.end();
>   it1 = words.begin();
>   &it1 == &++it1;
>   It it2 = it1++;
>   std::string word = *it2++;
>   assert(it1 == it2);
>   assert(words.begin() != words.end());
>   It::difference_type distance = 0;
>   It it3;
>   boost::forward_traversal_tag tag = boost::iterator_traversal<It>::type();
> }
>
> int main() {
>   List<std::string> words;
>   words.push_front("world");
>   words.push_front("Hello");
>   my_naive_check(words);
>   boost::for_each(words, std::cout << boost::lambda::_1 << "\n");
>   return EXIT_SUCCESS;
> }
>

(Also, could you please use plain formatting in your emails? It makes it
easier to reply inline and easier to read across a wide variety of media.
Thanks.)

- Jeff

[1]
http://www.boost.org/doc/libs/1_49_0/libs/iterator/doc/iterator_concepts.html