C++ Template meta-magic, template call-site qualification deduction mechanism

Question

I apologise for the verbosity of this example, I contrived it out of a project. The commented, Item 1 and item two, are important in the following code.

#include <boost/intrusive/set.hpp>

struct x : public boost::intrusive::set_base_hook<>
{
    int y;
};

struct finder
{
    bool operator()(const int & i, const x & _x) const
    { return i < _x.y;}
    bool operator()(const x & _x, const int & i) const
        { return _x.y < i;}
};

class trampoline
{
public:
    void bounce() const /* item 1 */
    {
        /*item 2*/
        boost::intrusive::set<x>::iterator it = _set.find(1,finder()); 
    }

    boost::intrusive::set<x> _set;
};

int main()
{
    trampoline t;
    t.bounce();
}

I cannot take a non-const itereator to my member container (item 2) where the function in scope is const, if I switch the iterator to a const_iterator everything works fine, or if I make the enclosing function non-const it works as well. Makes perfect sense, now, after an hour of reverse engineering the problem from the following error message:

test.cc: In member function ‘void trampoline::bounce() const’:test.cc:21: error: conversion from ‘boost::intrusive::tree_iterator<boost::intrusive::rbtree_impl<boost::intrusive::setopt<boost::intrusive::detail::base_hook_traits<x, boost::intrusive::rbtree_node_traits<void*, false>, (boost::intrusive::link_mode_type)1u, boost::intrusive::default_tag, 3>, std::less<x>, long unsigned int, true> >, true>’ to non-scalar type ‘boost::intrusive::tree_iterator<boost::intrusive::rbtree_impl<boost::intrusive::setopt<boost::intrusive::detail::base_hook_traits<x, boost::intrusive::rbtree_node_traits<void*, false>, (boost::intrusive::link_mode_type)1u, boost::intrusive::default_tag, 3>, std::less<x>, long unsigned int, true> >, false>’ requested

Which eventually led me to the following template definition (/include/boost/intrusive/detail/tree_node.hpp +72):

/////////////////////////////////////////////////////////////////////////////
//                                                                         //
//                   Implementation of the tree iterator                   //
//                                                                         //
/////////////////////////////////////////////////////////////////////////////

// tree_iterator provides some basic functions for a 
// node oriented bidirectional iterator:
template<class Container, bool IsConst>

Sufficed it so say I solved the problem shortly after....

How the hell does that template get passed IsConst from the callsite of the enclosing function ? My brain is ready to explode (for all I know its something simple, but I am mystified). A detailed explanation with a step by step implementation to explain the mechanics would be helpful.

I have a similar question here similar with regards to the type-deduction/aliasing of the template mechanism of C++. references are appreciated, but they need to be mulled over into knowledge :D. If you have the patience to answer this question, you might want to try to form a discourse on the other question.

Answer 1

Wouldn't the find() member function of boost::intrusive::set simply have a const and non-const overload? I mean, that's how I would do it:

template <typename T /*...*/ >
class set {
  //... 
  public:
    template <bool isConst>
    class iterator {
      //....
    };
    iterator<true> find(/*..*/) const; //notice the const
    iterator<false> find(/*..*/);      //notice no const
};

This really isn't meta-programming magic, just good old fashion const-correctness.