recursive template pointer to member parameters problem

[trantran]

This is likely a stupid question, but I can't figured out by myself how to pass a pointer to a member function of a templatised class in its own template parameters.
More clearly:
I would like to have this to work out:

template <typename T, T test::* PtrToMember>
class test{
    T a;
    T b;
    GetValue(){ 
           return this::*PtrToMember;
    }
}

which the compiler won't accept.

The problem is that the pointer to member type should be a sort of infinite recursion with the first line be something like:
template<typename T, T test<T,... recursion...
because test has a parameter that use itself its parameters.

Any brilliant idea of how to make this work?

[mattjbond]

This is likely a stupid question, but I can't figured out by myself how to pass a pointer to a member function of a templatised class in its own template parameters.
More clearly:
I would like to have this to work out:

template <typename T, T test::* PtrToMember>
class test{
    T a;
    T b;
    GetValue(){ 
           return this::*PtrToMember;
    }
}

which the compiler won't accept.

The problem is that the pointer to member type should be a sort of infinite recursion with the first line be something like:

template<typename T, T test<T,... recursion...

because test has a parameter that use itself its parameters.

Any brilliant idea of how to make this work?

One has to wonder what exactly you are trying to achieve here? Can you enlighten us?

[trantran]

One has to wonder what exactly you are trying to achieve here? Can you enlighten us?

The particular piece of code is just to isolate what I want to do.

In reality, I want to write a template function to iterate a list that would be versatile in that it could select which member data to use to go to the "next" data. For example, the same structure could have a Next_A and a Next_B data member (each being a pointer to a next instance) and you would use the same template function to go through the list by something like: goto_next<structure, data_member_pointer>()
for example: goto_next<mylist, Next_B>()
So this would prevent me from rewriting the code.
Of course I can achieve this easily if I pass the data_member_pointer as an argument to the function such as: goto_next<mylist>(&structure::Next_B) but I am curious to know if it is possible to do it as a template parameter.

At first sight, because the pointer to member type requires the actual structure (including the template parameters) to identify it, it appears I cannot do it because I end up in a recursive declaration or definition.

And this is where I need your brains!

(Also note that the little face in the original example are created automatically by the blog software when I type colon colon asterisk (to indicate data pointer such as : ::*)

[nezachem]

(Also note that the little face in the original example are created automatically by the blog software when I type colon colon asterisk (to indicate data pointer such as : ::*)

You may consider using code tags, such as ::* . In fact, it is a requirement for this forum.

[vijayan121]

Are you looking for something like this?

template< typename T > struct list
{
    T* current ;
};

template< typename T, T* T::*PTRMEMBER >
T* get_next( list<T>& lst ) 
{ 
    lst.current = lst.current->*PTRMEMBER ; 
    return lst.current ;
}

struct A
{
    A* member_one ;
    A* member_two ;
};

int main()
{
    A one = A() ;
    A two = A() ;
    A three = { &two, &one } ;
    A four = { &three, &two } ;

    list<A> lst = { &four };

    std::cout << get_next< A, &A::member_one >( lst ) 
              << '\t' << &three << '\n' ;

    std::cout << get_next< A, &A::member_two >( lst ) 
              << '\t' << &one << '\n' ;
}

[trantran]

Are you looking for something like this?

template< typename T > struct list
{
    T* current ;
};

template< typename T, T* T::*PTRMEMBER >
T* get_next( list<T>& lst ) 
{ 
    lst.current = lst.current->*PTRMEMBER ; 
    return lst.current ;
}

struct A
{
    A* member_one ;
    A* member_two ;
};

int main()
{
    A one = A() ;
    A two = A() ;
    A three = { &two, &one } ;
    A four = { &three, &two } ;

    list<A> lst = { &four };

    std::cout << get_next< A, &A::member_one >( lst ) 
              << '\t' << &three << '\n' ;

    std::cout << get_next< A, &A::member_two >( lst ) 
              << '\t' << &one << '\n' ;
}

Not quite.
You adroitely showed a workaround. But with that code you have a single instantiated class and two different function to address each situation (member_one or member_two function instantiation). I want two different instances of the list (one with member_one and the other with member_two) and a single instance of the function. I want it done inside the list class itself (using nested class if necessary) and I want the pointer_to_member to be used as the template argument to create the two different template instances of the class) so that you could instantiate the list class twice like this:

template list<T,member_one> list1;
template list<T,member_two> list2;

and then use get_next like this: list1.get_next() or list2.get_next()

In other words I would like to be able to compile this simple code :

// A: Code I want to compile but it won't because list::*member requires (recursive) template parameters for list
struct list<typename T, T * list::*member >{
	T * member_one;
	T * member_two;
	T * get_next(){
		return this->*member;
	}
};

(Of course there is a workaround such as this:

// B: Workaround 
struct list<typename T, int selector> {
	T * member_one;
	T * member_two;
	T * get_next(){
		if (selector==1) return member_one;
		else return member_two;
	}
};

but could C++ accept directly the other more direct solution (A) through some syntax unknown to me?

(Thanks to Nezachem for pointing me the existence of code tags formating)

[trantran]

I have found (almost) the solution (based on an underlying insight of vijayan12 which is to separate the classes)

template <typename T> 
struct raw_list{
	T * member_a;
	T * member_b
};

template <typename T, T * raw_list<T>::*member>
struct list{
	raw_list<T> rl
	T * get_next(){
		return rl.*member;
	}
};
// usage:
//  list<T, &raw_list::first> rl_1;
//  list<T, &raw_list::second> rl_2;
//   rl_1.get() ...

I said "almost" because I would have like to nest raw_list inside of list.
But I don't think that is possible because you wouldn't be able in that case to pass the pointer_to_member template argument (again same recursive problem).

[mattjbond]

Just thinking aloud but I am wondering if you can produce a solution based on crtp where each of you list members were derived from a base class templated on the derived class type. Then maybe you could define your list to pass in the list type rather than the pointer to member and get the behaviour you want through the static polymorhpism provided by the crtp. I'll have a play around and see if I can come up with anything.

[vijayan121]

[I want two different instances of the list (one with member_one and the other with member_two) and a single instance of the function. I want it done inside the list class itself (using nested class if necessary) and I want the pointer_to_member to be used as the template argument to create the two different template instances of the class) so that you could instantiate the list class twice like this:

If that is all you want, you do not need the pointer_to_member as a template parameter at all - just pass it to the constructor of the list. Then you could have either a member function or a free function do what you want.

#include <iostream>

template < typename T > struct list
{
    explicit list( T* list::*pm, T* a = 0, T* b = 0 )
        : member_a(a), member_b(b), pointer_to_member(pm) {}

    T* get() { return this->*pointer_to_member ; }

    T* member_a ;
    T* member_b ;
    T* list::*pointer_to_member ;
    // ...
};

template < typename T > T* get_it( list<T>& lst )
{ return lst.*lst.pointer_to_member ; }

int main()
{
    int a = 11111, b = 22222 ;

    list<int> lst1( &list<int>::member_a, &a, &b ) ;
    list<int> lst2( &list<int>::member_b, &a, &b ) ;

    std::cout << *lst1.get() << '\t' << *get_it(lst1) << '\n'
              << *lst2.get() << '\t' << *get_it(lst2) << '\n' ;
}

[trantran]

TO vijayan121

Good point, but this is at the expense of another 4 bytes.
In my application, the "next" are really part of a list_item and there are lots of them and I am somewhat memory constrained. The 4 bytes increase per item solves the problem but theoretically I don't see what we would need to pay a memory price for this since C++ and the compiler should theoretically be able to do the same thing without using more memory since a pointer to a member is just really an index to a structure already known at compile-time.

Is it just a syntax problem to be amended in a future revision of C++ or is there some underlying theoretically reason that I haven't think about?

[vijayan121]

> Is it just a syntax problem to be amended in a future revision of C++
> or is there some underlying theoretically reason that I haven't think about?

There is an underlying theoretical reason, and you have already thought about it.

A pointer to member of a class cannot be introduced before the class is at least declared.

// error: `undeclared_class' has not been declared
int undeclared_class::*pointer_to_member ; 

struct declared_class ;
// fine: `declared_class' has been declared
int declared_class::*pointer_to_member ;

In this case, just to declare the class we need a pointer to member of that class which is not yet declared (which we are trying to declare).

You also have a discovered the solution; split this into two classes.

#include <iostream>

template < typename T > struct list_base
{
    explicit inline list_base( T* a = 0, T* b = 0 ) 
        : member_a(a), member_b(b) {}

    T* member_a ;
    T* member_b ;
    // ...
};

template < typename T, T* list_base<T>::*PTR_MEMBER > 
struct list : list_base<T>
{
    explicit inline list( T* a = 0, T* b = 0 ) 
       : list_base<T>(a,b) {}

    inline T* get() { return this->*PTR_MEMBER ; }

    // ...
};

template < typename T, T* list_base<T>::*PTR_MEMBER >
inline T* get_it( list<T,PTR_MEMBER>& lst ) 
{ return lst.*PTR_MEMBER ; }

int main()
{
    int a = 11111, b = 22222 ;

    list<int,&list_base<int>::member_a> lst1( &a, &b ) ;
    list<int,&list_base<int>::member_b> lst2( &a, &b ) ;

    std::cout << *lst1.get() << '\t' << *get_it(lst1) << '\n'
              << *lst2.get() << '\t' << *get_it(lst2) << '\n' ;
}

[trantran]

Just thinking aloud but I am wondering if you can produce a solution based on crtp where each of you list members were derived from a base class templated on the derived class type. Then maybe you could define your list to pass in the list type rather than the pointer to member and get the behaviour you want through the static polymorhpism provided by the crtp. I'll have a play around and see if I can come up with anything.

Yes, I tried it and it works quite well for what I wanted to do and with no memory cost.
It is an effective workaround.
Still I would have much preferred that C++ permit the other behavior.
Many thanks for your idea. Much appreciated.

[trantran]

Error

[trantran]

> Is it just a syntax problem to be amended in a future revision of C++
> or is there some underlying theoretically reason that I haven't think about?

There is an underlying theoretical reason, and you have already thought about it.

A pointer to member of a class cannot be introduced before the class is at least declared.

// error: `undeclared_class' has not been declared
int undeclared_class::*pointer_to_member ; 

struct declared_class ;
// fine: `declared_class' has been declared
int declared_class::*pointer_to_member ;

In this case, just to declare the class we need a pointer to member of that class which is not yet declared (which we are trying to declare).

You also have a discovered the solution; split this into two classes.

#include <iostream>

template < typename T > struct list_base
{
    explicit inline list_base( T* a = 0, T* b = 0 ) 
        : member_a(a), member_b(b) {}

    T* member_a ;
    T* member_b ;
    // ...
};

template < typename T, T* list_base<T>::*PTR_MEMBER > 
struct list : list_base<T>
{
    explicit inline list( T* a = 0, T* b = 0 ) 
       : list_base<T>(a,b) {}

    inline T* get() { return this->*PTR_MEMBER ; }

    // ...
};

template < typename T, T* list_base<T>::*PTR_MEMBER >
inline T* get_it( list<T,PTR_MEMBER>& lst ) 
{ return lst.*PTR_MEMBER ; }

int main()
{
    int a = 11111, b = 22222 ;

    list<int,&list_base<int>::member_a> lst1( &a, &b ) ;
    list<int,&list_base<int>::member_b> lst2( &a, &b ) ;

    std::cout << *lst1.get() << '\t' << *get_it(lst1) << '\n'
              << *lst2.get() << '\t' << *get_it(lst2) << '\n' ;
}

But, what do you do when T is "list"
For example: list_base<list>

You get the annoying recursion problem again!
Anyother great idea on this?

[vijayan121]

> But, what do you do when T is "list"
> For example: list_base<list>

> You get the annoying recursion problem again!
> Anyother great idea on this?

Perhaps you should first describe the real problem that you are trying to solve. It might, just might, have a much easier solution.

[trantran]

Perhaps you should first describe the real problem that you are trying to solve. It might, just might, have a much easier solution.

"Perhaps you should first describe the real problem that you are trying to solve. It might, just might, have a much easier solution."

Very good suggestion.
Here is the full problem.

I have a very large group of items which are linked to each other by different double link lists and trees using members inside each item.
Thus each item looks like this:

// Solution 1
struct item{
	 // some (irrelevant) data here
	struct Whatever data;		
	
	// members for list 1
	private:
	item * prev1;
	item * next1;
	public:
		// typical list functions here such as:
	item * gotonext1(){...}
	item * gotoprev1(){...}
	insert_after(item * new_item){...}
	delete(){...}
	etc...

	// members for list 2
	private:
	item * prev2;
	item * next2;
	public:
	... typical list functions...	

	// members for tree3
	private:
	item * prev3;
	item * next3;
	item * parent;
	item * first_child3;
	item * last_child3;
	public:
	... typical tree functions...

	... etc..
};

This is a very effective structure, both for memory (no unecessary data is needed to be kept) and speedy (no unecessary supplementary indirection).
It is also a very practical structure: once you have a pointer to an item (let's call it current) you can move at any other item following whatever list you want, and do it repeatedly with minimal typing, like this:
next_item=current.gotonext1().gotofirstchild3().gotoprev2();

But it is very dumb semantically because you have to repeat all the structures/function in the code.

Tentative solution 2:

Of course, when one sees this, one could think:
"oh! we can simply view this as a case of items stored in different containers! Let's just use different containers, each containing pointer to those items. And voila!"
But that would be very ineffective:
memory-wise: lots of expensive supplementary (and unecessary) pointers to items.
speed-wise: once you move to the next item you have to "find" the location of that item in all the different containers (or at least in the container you will use next for the following "next" or other functions)... and that complicates everything considerably.

Tentative solution 3:

Fine, then what we really want to have is a sort of "super-iterator" to iterate through the items in different ways (different lists, trees, etc).
So let's just write that using a diamond shape structure:

struct super_iterator_base{
item * current;
};
struct list1_iterator:virtual super_iterator_base{
... list1 functions here...
};
struct list2_iterator:virtual super_iterator_base{
... list1 functions here...
};
struct tree3_iterator:virtual super_iterator_base{
... tree3 functions here...
};
struct super_iterator: list1_iterator, list2_iterator,tree3_iterator{
};

Efficient in memory: no supplementary pointers for each items as in solution 2;
Not always efficient in speed: there is an additional (invisible) indirection created by the virtual dispatch when you move using the super_iterator.
Complex: virtual diamond-shape structure (including additional space required for iterators (1 pointer for each list, tree, etc in the iterator) that wasn't necessary in solution 1)
So not ideal, but probably the best of all unless you find something even better (or find faults in this one!)

Tentative solution 4 (which does not appear to work at all)
(This was the solution that I was trying to make work with your help but I unfortunately was not very clear at all in what I wanted to achieve.)

Ok, then just create separate templatised list1, list2, tree3, etc, structures, something like this:

template< typename T, T * T::*ptr_to_member>
struct list{
	private:
T * prev;
T * next;
public:
delete(){
prev->*ptr_to_member.next=next;
next->*ptr_to_member.prev=prev;
}
etc...
};
struct tree{
... similar code ...
};

struct item{
struct Whatever data;
list<item,  &item::lst1> lst1;
list<item,  &item::lst2> lst2;
tree<item,  &item::tr3> tr3;
...etc...
};

The reason for passing the ptr_to_member is that by passing the pointer to member to lst1 (for example), lst1 can easily "convert" the item pointers (returned by its function) to pointers to lst1 that are internally necesary in certain processing/function calls such as, for example, delete() (as shown above)

This would have been the most effective, elegant, intuitive and overall desirable solution was it not for what I believe... (but I am a C++ newbie so could be completely wrong on this !) an inadequacy in C++.
After all, even though it appears that C++ does not permit to use &item::lst1 INSIDE the definition of item, there is, as far as I can see, no theoretically justification (just a possible C++ committee decision which could be changed...). Let me explain more:

There IS an (obvious) theoretical impossibility for having a member of a class being the class itself such as this: struct item { item it;}
There is NO theoretical impossibility for having a member of a call being a pointer to the same class (because the size of a pointer to a class does not depend on the class itself and is therefore known before the class is even defined), such as: struct item; struct item{item * p_item;} and this is in fact explicitly permitted in c++
Similarly there is NO theoretical impossibility for having the address of a pointer to a member of a class inside the class itself, as it appears that a compiler could easily figure this because that address is really an offset to a structure AND that structure does *not* depend on the value of that offset for its definition. Therefore in a first step the compiler can define the structure (and put dummy values for the yet unknown offsets) and in a second step it can calculate the offset and replace the dummy values with that offset.

Solution 4 ???? 
(... your brains exerciced right here ...  it's proven good for you for Alzheimer prevention! ... Try it! ) 
wish list:
-no additional memory cost for each item than memory-efficient solution 1.
-keeps double-link list structures (no vectors, etc...)
-no supplementary indirection cost allowed (as speedy as solution 1)
-no more "typing" when using it  than there is in solution 1 (therefore no additional parameters, etc)
-a solution that is simple, logical and semantically elegant (in other words the exact opposite of solution 1!)
OR
- try to make solution 4 work, using an astute clever c++ trick  that will deligh me if it exist!

IMPORTANT NOTE: I am a C++ newbie. So there could be glaring/obvious mistake in all of my exposé, or (hopefully) obvious way to do it nice and easily, perhaps even using that you have previously said and perhaps didn't fully understood.
I'd loved to be illuminated.

[trantran]

Explaining something is often the first step to solving it!
I think I have another solution, not perfect but pretty good.
It is equivalent (and based) on the diamond solution idea.
It is also based on Vijayan121 bright idea to separate things out.
The additional memory cost is in the pointer and not in the struct item, so that cost is practically meaningless (but solution1 was theoretically) better in that there were no unecessary additional memory needed at all - this is one reason why the solution is not perfect - the other reason is that it is not simple or intuitive at all, I'd say unecessary complex because of c++ prohibition on using address to pointer_to_member of a class inside that class itself as previously discussed)
I'll have to test it to see if it really works or if problems pop up somewhere somehow.
Comments on it most welcome!

struct item {
      struct  Whatever data;
      list_data<item> lst1;
      list_data<item> lst2;
      tree_data<item>tr3;
     ... etc...
}

struct youpie_pointer{
     item * ptr;
    list_fct<item, &item::lst1> lf1;
    list_fct<item, &item::lst2 > lf2;
     tree_fct<item, &item::tr3 > tf3;
    youpie_pointer():lf1(ptr),lf2(ptr),tf3(ptr){}
};

where list_data is something like:

template <typename T>
struct list_data{
   T* prev;
   T* next;
  ... etc...
};

and list_fct something like:

template <typename T, T * T::*ptr>
struct list_fct{
      item * & ptr_ref; // important note: pointer reference! not just pointer!
      list_fct(item * ptr):ptr_ref(ptr){}
     T * goto_next(){...}
};

[vijayan121]

> wish list:
> -no additional memory cost for each item
> -keeps double-link list structures (no vectors, etc...)
> -no supplementary indirection cost allowed
> -no more "typing" when using it
> -a solution that is simple, logical and semantically elegant

I have a very large group of items which are linked to each other by different double link lists and trees using members inside each item.

what we really want to have is a sort of "super-iterator" to iterate through the items in different ways

Yes, what we want are ways to access these items as different sequences. A set of polymorphic iterators which can iterate through the same items as different sequences.

there is an additional (invisible) indirection created by the virtual dispatch when you move using the super_iterator.

So we will make them polymorphic at compile-time using the earlier pointer to member idea. The example below is just for the doubly linked list like sequences.

#include <iostream>
#include <iterator>
#include <algorithm>

// iterator over a sequence using pointers to members 
// for next element and prev element
template< typename T, T* T::*NEXT, T* T::*PREV >
struct list_iterator : std::iterator<std::bidirectional_iterator_tag,T*>
{

    list_iterator( T* curr, T* last ) : current(curr), last_element(last) {}

    T*& operator* () { return current ; }

    list_iterator& operator++ ()
    { current = current->*NEXT ; return *this ; }

    list_iterator& operator-- ()
    { current = current ? current->*PREV : last_element ;  return *this ; }

    list_iterator operator++ (int)
    { list_iterator before(*this) ; ++*this ; return before ; }

    list_iterator operator-- (int)
    { list_iterator before(*this) ; --*this ; return before ; }

    bool operator== ( const list_iterator& that ) const
    { return this->current == that.current ; }

    bool operator!= ( const list_iterator& that ) const
    { return this->current != that.current ; }

    private:
       T* current ;
       T* last_element ;
};

Next we write sequence operations like insert, erase, print etc. in terms of polymorphic iterators.

template< typename T, T* T::*NEXT, T* T::*PREV > inline
void insert_into_list( T* new_element, list_iterator<T,NEXT,PREV> iter )
{
    list_iterator<T,NEXT,PREV> temp = iter ;
    T* prev = *--temp ;
    if(prev) prev->*NEXT = new_element ;
    new_element->*NEXT = *iter ;
}

template< typename T, T* T::*NEXT, T* T::*PREV > inline
void remove_from_list( list_iterator<T,NEXT,PREV> iter )
{
    list_iterator<T,NEXT,PREV> ptemp = iter ;
    list_iterator<T,NEXT,PREV> ntemp = iter ;
    T* prev = *--ptemp ;
    T* next = *++ntemp ;
    if(next) next->*PREV = prev ;
    if(prev) prev->*NEXT = next ;
}

template< typename ITERATOR > inline
void print_list( const char* label, ITERATOR begin, ITERATOR end )
{
    std::cout << label << ":\n" ;
    typedef typename ITERATOR::value_type T ;
    std::copy( begin, end,
               std::ostream_iterator<T>( std::cout, " -> " ) ) ;
    std::cout << "0\n\n" ;
}

This is our item structure (with everything other than the doubly linked list pointers elided for clarity):

struct item
{
    // members for list 1
    item * next1;
    item * prev1;

    // members for list 2
    item * next2;
    item * prev2;

    // members for tree 1 etc.
    // ....

    item() : next1(0), prev1(0), next2(0), prev2(0) {}
};

And finally a main, to see if it really works:

int main()
{
    item a, b, c, d, e ;
    std::cout << "a:" << &a << "  b:" << &b << "  c:" << &c
              << "  d:" << &d << "  e:" << &e << "\n\n" ;

    // list1 == a->b->c->d->e
    a.next1 = &b ; b.next1 = &c ; c.next1 = &d ; d.next1 = &e ;
    e.prev1 = &d ; d.prev1 = &c ; c.prev1 = &b ; b.prev1 = &a ;

    // list2 == c->a->d->e->b ;
    c.next2 = &a ; a.next2 = &d ; d.next2 = &e ; e.next2 = &b ;
    b.prev2 = &e ; e.prev2 = &d ; d.prev2 = &a ; a.prev2 = &c ;

    typedef list_iterator< item, &item::next1,
                            &item::prev1 > list1_iterator ;
    list1_iterator begin1( &a, &e ), end1( 0, &e ) ;
    print_list( "list1", begin1, end1 ) ;

    typedef list_iterator< item, &item::next2,
                            &item::prev2 > list2_iterator ;
    list2_iterator begin2( &c, &b ), end2( 0, &b ) ;
    print_list( "list2", begin2, end2 ) ;

    typedef std::reverse_iterator< list2_iterator >
                                     reverse_list2_iterator ;
    reverse_list2_iterator rbegin(end2), rend(begin2) ;
    print_list( "list2 in reverse", rbegin, rend ) ;

    item f ;
    std::cout << "f:" << &f << "\n\n" ;

    // insert f into list1 at the place d is
    // to get a->b->c->f->d->e
    insert_into_list( &f, std::find( begin1, end1, &d ) ) ;
    print_list( "list1 after insert", begin1, end1 ) ;

    // remove a from list2 to get c->d->e->b ;
    remove_from_list( std::find( begin2, end2, &a ) ) ;
    print_list( "list2 after remove", begin2, end2 ) ;
}

Output:

a:0x22ff50 b:0x22ff40 c:0x22ff30 d:0x22ff20 e:0x22ff10

list1:
0x22ff50 -> 0x22ff40 -> 0x22ff30 -> 0x22ff20 -> 0x22ff10 -> 0

list2:
0x22ff30 -> 0x22ff50 -> 0x22ff20 -> 0x22ff10 -> 0x22ff40 -> 0

list2 in reverse:
0x22ff40 -> 0x22ff10 -> 0x22ff20 -> 0x22ff50 -> 0x22ff30 -> 0

f:0x22fdc0

list1 after insert:
0x22ff50 -> 0x22ff40 -> 0x22ff30 -> 0x22fdc0 -> 0x22ff20 -> 0x22ff10 -> 0

list2 after remove:
0x22ff30 -> 0x22ff20 -> 0x22ff10 -> 0x22ff40 -> 0

Note:
1. The insert/remove functions do not take care of all special cases.
2. Using polymorphic call wrappers instead of pointers to members would perhaps be more flexible.

Before we go into all that:
Does this iterator approach meet your requirements?

[trantran]

Thank you Vijayan for your answer. I want to make a few points

1) The iterator
I was not looking for the actual code of an iterator (only for comments on my suggestion or possible other suggestions, which you also provided), but since you did provide that code there are a few things I don't understand in your iterator code:
a) why do you have a last_element member? Why don't you just return NULL for the before first element or after last element? I suspect you might have done that because of reverse iterations but even then I don't see why the much simpler NULL wouldn't work just as well.
b) why didn't you just put the insert_into_list and remove_into_list function INSIDE the iterator? (this would have saved an annoying unecessary supplementary argument when you use the function, wouldn't it?)
(minor point c) you forgot to set both prev member in insert_into-list - likely purposefully to just give an idea of the code and to be faster)

2) I would have like you to have your opinion on a possible future revision of C++ to permit the pointer_to_member inside its own class (as I believe it is theoretically possible to do it - as explained above in the previous post #16), or perhaps you truly believe it is impossible? Then why? especially since this address is only an offset into a structure, not an offset of an actual instance as in a regular C-like function ptr)

3) You seem to confirm that the last suggestion I proposed is the best approach, and you also mentionned "polymorphic call wrappers": I would be delighted to hear more about what that is! Do you mean to replace the pointer_to_members by a function object? (In any case the function object option seem to be a very nice idea to explore and it might (?) even simplifies things and end up being an effective workaround for the C++ pointer_to_member limitation? I'll have to think more about it and would like to hear your ideas on those matters.

4) I think that we do have a solution that satisfy the requirement. (Even though I would still have preferred the much simpler (impossible with current C++ rules) "tentative solution 4" and hoping we might simplify it further with function objects or your "polymorphic call wrappers").

[trantran]

ADDENDUM: After thinking a bit about it, using a function object to encapsulate the pointer members (prev, next) makes it more elegant and nicely packaged but unfortunately it does not permit to make the "tentative solution 4" (of post#16 ) to work out (very unfortunately).

[vijayan121]

1) The iterator
a) why do you have a last_element member? Why don't you just return NULL for the before first element or after last element? I suspect you might have done that because of reverse iterations but even then I don't see why the much simpler NULL wouldn't work just as well.

The iterator corresponding to end is one which 'point to' a fictitious one past the last element of the sequence. This iterator must be well defined; --end should move the iterator to the last element of the sequence

b) why didn't you just put the insert_into_list and remove_into_list function INSIDE the iterator?

Insert and erase are logically operations on sequences; not operations on an iterator which just identifies one element of a sequence. Of course it is possible to create a pseudo sequence container and put insert and erase and other container operations into it.

2) I would have like you to have your opinion on a possible future revision of C++ to permit the pointer_to_member inside its own class

A pointer to member inside its own class is already allowed. eg.

template< typename T, int T::*PM > struct A {} ;
struct B
{
    int i ;
    A< B, &B::i > a ;
};

3) You seem to confirm that the last suggestion I proposed is the best approach, and you also mentionned "polymorphic call wrappers": I would be delighted to hear more about what that is! Do you mean to replace the pointer_to_members by a function object?

A function object is a callable object, as is a pointer to a free function or a bound member function.
A call wrapper can hold any target callable object that can be called with the argument types and returns a type that can be converted to the object's return type. The underlying callable object (pointer to free function, function object, bound member function etc.) isn't specified when the call wrapper is instantiated; it precisely known only at the place where the call is made.

std::tr1::function< item*(item*) > can hold any callable object
that can be called with an arguments of type item* and returns a result that is or can be converted to an item*.

struct item { item* next1() const ; /* ... */  } ;
item* free_fun_get_nxt( const item* ) ;
struct do_get_next : std::unary_function<item*,item*>
{
    item* operator() ( item* ) const ;
};

std::tr1::function< item*(item*) > get_next_t ;

get_next_t get_next = &item::next1 ;
get_next = free_fun_get_nxt ;
get_next = do_get_next() ;

Call wrappers are useful in a lot of non-trivial ways - among other things, it allows us to specify the type of a callable object based on nothing more than a knowledge of its argument and return types.

[trantran]

The iterator corresponding to end is one which 'point to' a fictitious one past the last element of the sequence. This iterator must be well defined; --end should move the iterator to the last element of the sequence

But why can't NULL be the last element of the sequence?
C++ standard 24.1.5 explicitly says concerning iterators that: "The library never assumes that past-the-end values are dereferenceable"
So the iterator value that represents past-the-end can be NULL.

A pointer to member inside its own class is already allowed. eg.

template< typename T, int T::*PM > struct A {} ;
struct B
{
    int i ;
    A< B, &B::i > a ;
};

Problem! That code WON'T compile in microsoft visual C++ 2008 issuing specifically the C2327 compiler error:

"'symbol' : is not a type name, static, or enumerator
Code within a nested class attempts to access a member of the enclosing class that is not a type name, a static member, or an enumerator

So either:
1) C++ does not really allow it (when templates are involved), or
2) Visual C++ 2008 is not C++ compliant.
If 2) is correct than could you provide me the name of the compiler you are using that will accept that code?

[trantran]

1)

But why can't NULL be the last element of the sequence?
C++ standard 24.1.5 explicitly says concerning iterators that: "The library never assumes that past-the-end values are dereferenceable"
So the iterator value that represents past-the-end can be NULL.

Forget this part! My mistake.
Now, I understand what you meant in your previous answer about --end() !

2)
But don't forget to comment on the other part about c++ template and pointer_to_members in the previous post! This is a VERY important point of this thread for me!

[vijayan121]

> Problem! That code WON'T compile in microsoft visual C++ 2008
> issuing specifically the C2327 compiler error:
> "'symbol' : is not a type name, static, or enumerator
> Code within a nested class attempts to access a member of the
> enclosing class that is not a type name, a static member, or an enumerator

Clearly, that is a spurious error message. In that code, there is no nested class is at all, and therefore there is no enclosing class either.

The IS clearly states that:

After the point of declaration of a class member, the member name can be looked up in the scope of its class. [Note: this is true even if the class is an incomplete class.]

It also gives an example (elided for clarity):

class Y;
char Y::* pmc;

declares pmc to be a pointer to a member of Y of type char. The declaration of pmc is well-formed even though Y is an incomplete type.

The code compiles cleanly under various versions of the GNU compiler, the Comeau compiler and other compilers with an EDG front end. AFAIK, the Microsoft C++ compiler which does not compile it is non-conforming for this case.

[trantran]

The example given in the standard is different and will compile easily in Microsoft VC2008, for example this compiles without problem:

struct B{
  int i;
  int B::*ptr;
};

The reason being that the ptr in that code is not yet assigned to any actual member of that class value!

In your initial post the problem lies with the implicit assignment int T::*PM to &B::i when the template is instantiated at compile-time. At that point B is not well formed and therefore the compiler don't know what B::i is and therefore complains:
"error C2327: 'B::i' : is not a type name, static, or enumerator".
Yes, the standard permit to declare a pointer to a member of the class inside itself, but I don't think it permits to assign it to one of its member until the class is fully formed.

Clearly, that is a spurious error message. In that code, there is no nested class is at all, and therefore there is no enclosing class either.

The nested class is: A< B, &B::i > which is being instantiated INSIDE B. The enclosing class here is B.

The code compiles cleanly under various versions of the GNU compiler, the Comeau compiler and other compilers with an EDG front end. AFAIK, the Microsoft C++ compiler which does not compile it is non-conforming for this case.

Did you test the non-template code (similar to the C++ standard example - that is without the assignment) or the actual (template) code you initially posted?

[vijayan121]

> the problem lies with the implicit assignment int T::*PM to &B::i
> when the template is instantiated at compile-time.

Well, no assignment to an l-value is possible at compile time. At compile time, the constant expression &B::i is specified as the second template parameter.

A pointer to member constant expression shall be created using the unary & operator applied to a qualified-id operand, optionally preceded by a pointer to member cast

> At that point B is not well formed
B is just an incomplete type at that point. There is nothing in B so far to make it ill-formed.

> therefore the compiler don't know what B::i is and therefore complains:
The compiler knows (or ought to know) at that point that B::i is a non-static public member of B of type int.

The potential scope of a name declared in a class consists not only of the declarative region following the name's declarator, but also ...{elided}.

A name N used in a class S shall refer to the same declaration in its context and when re-evaluated in the completed scope of S.

> The nested class is: A< B, &B::i > which is being instantiated INSIDE B.
> The enclosing class here is B.

No.

A class defined within another is called a nested class. The name of a nested class is local to its enclosing class. The nested class is in the scope of its enclosing class. Except by using explicit pointers, references, and object names, declarations in a nested class can use only type names, static members, and enumerators from the enclosing class.

and

For a class template specialization, or {elided}, if the specialization is implicitly instantiated because it is referenced from within another template specialization, and if {elided}, and if {elided} the point of instantiation is immediately before the point of instantiation of the enclosing template.

Otherwise, the point of instantiation for such a specialization immediately precedes the namespace scope declaration or definition that refers to the specialization.

If you are in doubt about what that bit of legalese means, compile and run this:

#include <iostream>

enum { VALUE = 100 } ;

struct A
{
    enum { VALUE = 99999 } ;

    template< typename T > struct S_nested_in_A
    {
        int check_value() const { return VALUE ; }
    };

    S_nested_in_A<int> ss ;
};


template< typename T > struct S
{
    int check_value() const { return VALUE ; }
};

struct B
{
    enum { VALUE = 99999 } ;

    S<int> ss ;
};

int main()
{
    A aa ;
    B bb ;

    if( aa.ss.check_value() == A::VALUE )
         std::cout << "S_nested_in_A<int> was instantiated as a nested class within A\n" ;
    else if( aa.ss.check_value() == ::VALUE )
         std::cout << "S_nested_in_A<int> was instantiated at global scope\n" ;


    if( bb.ss.check_value() == B::VALUE )
         std::cout << "S<int> was instantiated as a nested class within B\n" ;
    else if( bb.ss.check_value() == ::VALUE )
         std::cout << "S<int> was instantiated at global scope\n" ;
}

In summary, my understanding is that for

template< typename T, int T::*PM > struct A {} ;

struct B
{
    int i ;
    A< B, &B::i > a ;
};

the GNU compiler, the Comeau compiler, and compilers which use an EDG front end are conforming. The Microsoft C++ compiler is non-conforming.

[trantran]

Impressive demonstration!

And also very depressing for me...
C++ must be given a gold medal for the most UNintuitive language ever created in the recorded history of the world.
After spending more than a year learning C++ , I now realise that I still don't know it enough to program safely with that language.
Even more depressing is that EVEN a company like Microsoft with billions of dollars of spending in research, easy access to any computer scientist in the world, can't figure correctly how C++ works.

I am also *very* impressed by your mastering of the language.

So the next obvious question is this: where/how/in what books did you learn C++ and how many years (or decades!) did it take you?

My best hope is to copy the learning method of THE expert of the language.

[vijayan121]

> After spending more than a year learning C++ , I now realise that
> I still don't know it enough to program safely with that language.

That is almost certainly incorrect. To be able to program well (safely, elegantly, efficiently) in a language does not imply that you have to know 'everything' about the language.

To quote Stroustrup:

What design and programming techniques do we want to emphasize? What subsets of the language do we want to learn first? What subsets of the language do we want to emphasize in real code?

...

Even for the professional programmer, it is impossible to first learn a whole programming language and then try to use it. A programming language is learned in part by trying out its facilities for small examples. Consequently, we always learn a language by mastering a series of subsets. The real question is not ‘‘Should I learn a subset first?’’ but ‘‘Which subset should I learn first?’’

...

The emphasis for both novices and experienced programmers should be concepts and techniques. The syntactic and semantic details of C++ are secondary to an understanding of design and programming techniques that C++ supports.

- from http://www.research.att.com/~bs/new_learning.pdf

> Even more depressing is that EVEN a company like Microsoft with
> billions of dollars of spending in research, easy access to any
> computer scientist in the world, can't figure correctly how C++ works.

Not really. The Microsoft C++ team has known about this (and several other cases of non-conformance) for more than five years now. Fixing this is seen by them (justifiable IMHO - it is not a 'stop everything till we fix this' kind of issue; there are easy work-arounds; it is a feature that is very rarely used in real life code) as of having a lesser priority than other things that they are spending their time on.

> where/how/in what books did you learn C++

Here are some of the books (in no particular order) that I've found useful:

1. Ruminations on C++: A Decade of Programming Insight and Experience by Andrew Koenig, Barbara E. Moo

2. C++ Templates: The Complete Guide by David Vandevoorde, Nicolai M. Josuttis

3. The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis

4. Standard C++ IOStreams and Locales: Advanced Programmer's Guide and Reference by Angelika Langer, Klaus Kreft

5. C++ Coding Standards: 101 Rules, Guidelines, and Best Practices by Herb Sutter, Andrei Alexandrescu

6. Modern C++ Design: Generic Programming and Design Patterns Applied by Andrei Alexandrescu

7. Inside the C++ Object Model by Stanley B. Lippman

8. Beyond the C++ Standard Library: An Introduction to Boost by Björn Karlsson

9. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond by David Abrahams, Aleksey Gurtovoy

10. The C++ Standard Library Extensions: A Tutorial and Reference by Pete Becker

11. Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson,
and John Vlissides

12. Advanced C++ Programming Styles and Idioms by James O. Coplien

13. Refactoring: Improving the Design of Existing Code by Martin Fowler, Kent Beck, John Brant, William Opdyke, Don Roberts

14. Large-Scale C++ Software Design by John Lakos

I've found these web resources to be instructive and useful:

1. comp.lang.c++.moderated - http://groups.google.co.in/group/comp.lang.c++.moderated

2. comp.std.c++ - http://groups.google.co.in/group/comp.std.c++

[trantran]

Problem solved.

Many thanks for your very precious help !
I feel very fortunate that are people like you in this world!