[Boost-users] Iterator concept checking

Subject: [Boost-users] Iterator concept checking
From: McNamara, Nate (nate.mcnamara_at_[hidden])
Date: 2012-05-24 11:39:41

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::ForwardTravers
alIterator<iterator>)>::failed> boost_concept_check81;
typedef ::boost::concepts::detail::instantiate<
&::boost::concepts::requirement_<void(*)(boost::concepts::WritableIterat
or<iterator>)>::failed> boost_concept_check82;
typedef ::boost::concepts::detail::instantiate<
&::boost::concepts::requirement_<void(*)(boost::concepts::ForwardTravers
alIterator<const_iterator>)>::failed> boost_concept_check83;
typedef ::boost::concepts::detail::instantiate<
&::boost::concepts::requirement_<void(*)(boost::concepts::ReadableIterat
or<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.

// 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(); }

 
BOOST_CONCEPT_ASSERT((boost::concepts::ForwardTraversalIterator<iterator
>));
  BOOST_CONCEPT_ASSERT((boost::concepts::WritableIterator<iterator>));
 
BOOST_CONCEPT_ASSERT((boost::concepts::ForwardTraversalIterator<const_it
erator>));
 
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;
}

________________________________________

This E-Mail (including any attachments) may contain privileged or confidential information.  It is intended only for the addressee(s) indicated above.

The sender does not waive any of its rights, privileges or other protections respecting this information.  

Any distribution, copying or other use of this E-Mail or the information it contains, by other than an intended recipient, is not sanctioned and is prohibited.

If you received this E-Mail in error, please delete it and advise the sender (by return E-Mail or otherwise) immediately. 

This E-Mail (including any attachments) has been scanned for viruses. 

It is believed to be free of any virus or other defect that might affect any computer system into which it is received and opened. 

However, it is the responsibility of the recipient to ensure that it is virus free. 

The sender accepts no responsibility for any loss or damage arising in any way from its use.

E-Mail received by or sent from RBC Capital Markets is subject to review by Supervisory personnel. 

Such communications are retained and may be produced to regulatory authorities or others with legal rights to the information.

IRS CIRCULAR 230 NOTICE:  TO COMPLY WITH U.S. TREASURY REGULATIONS, WE ADVISE YOU THAT ANY U.S. FEDERAL TAX ADVICE INCLUDED IN THIS COMMUNICATION IS NOT INTENDED OR WRITTEN TO BE USED, AND CANNOT BE USED, TO AVOID ANY U.S. FEDERAL TAX PENALTIES OR TO PROMOTE, MARKET, OR RECOMMEND TO ANOTHER PARTY ANY TRANSACTION OR MATTER.