Boost logo

Boost Users :

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



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net