Expert: Ralph McArdell - 6/5/2006

Question
I have wrote my own Multiset Container and Iterator class.
My Iterator class have a pointer point to a Multiset element.

And then , I make my iterator be a STL iterator. So I can use the STL algorithms.

My Iterator class is shown here :

template<class Key, class Comp = less<Key>, class A = allocator<Key> >
class Multiset ;

template<class C,typename T, class D = ptrdiff_t >
class Iterator  
{
    typedef T      value_type;
    typedef D      difference_type;
   typedef C   iterator_category;
   typedef T*      pointer;
   typedef T&      reference;

   friend Multiset<T>;

public:
  Iterator(){}
  Iterator(CNode<T>* m_Node);
  pointer operator->() const;
  reference operator*() const;
  Iterator<C,T>& operator++();
  Iterator<C,T> operator++(int);
  Iterator<C,T>& operator--();
  Iterator<C,T> operator--(int);

  bool operator ==(const Iterator& rhs) const;
  bool operator !=(const Iterator& rhs) const;
protected:

  CNode<T>* mIt; // an element of Multiset
  unsigned long GetKey();
  void increment();
  void decrement();
  CNode<T>* GetNode()
};


But , when I use the upper_bound function in algorithm library of C, there is a error :

...\include\algorithm(847) : error C2784: '_D *__cdecl std::_Dist_type(const struct std::iterator<_C,_Ty,_D> &)' : could not deduce template argument for 'const struct std::iterator<_C,_Ty,_D> &' from 'class Iterator<struct std::bidirectional_iterator_tag,double,int>'

How can I solve this. My iterator class is correct ? What are the requirement for an standard iterator of C (for multiset)

Answer
It would have saved me a good few minutes (half hour maybe) if you had said straight out what compiler, version and C++ standard library implementation and version you are using. Please do this in all future questions that are compiler/library specific and also what operating system etc. if relevant (for example if you ask me about mouse clicks expecting Linux/Gnome and do not mention Linux/Gnome then I will probably assume Windows). Not all compilers and library implementations are equal. Most fall short of the C++ standard. And they do it in different areas.

Anyhow, as far as I can tell you are using a version of MSVC++ 6 or maybe 5, with the C++/STL implementation that shipped with these products. Note that this is a _very_ old and somewhat broken/limited STL implementation. It originally shipped with VC5.

Note that I had to trawl through the header files for various VC++ versions STL implementations to find this out. Not fun. Waste of my time. Maybe I have wasted so much time I cannot answer your problem. I am certainly not very well disposed towards you.

You also have not shown enough code for me to recreate the problem without even more effort and so I cannot give an answer that I know is totally correct. And no I do _not_ want you to post large quantities of code either. I expect you to par the posted example code down to the absolute minimum that is complete and shows the problem. I can then copy and paste into a test code source file and see if I can recreate the problem, and also spot any further problems. In fact in doing this you may find you fix some problems on your own <g>.

Remember that AllExperts experts answer on a volunteer basis. We have our own lives to get on with as well. The easier you make it for us to help you the more likely it is you will get help and good help.

In my VC6 installation I see that the C++ STL implementation internal inline function template _Dist_type is defined as follows in header file iterator:

template<class _C, class _Ty, class _D> inline
  _D *_Dist_type(const iterator<_C, _Ty, _D>&)
  {return ((_D *)0); }

Which matches your error message information.

You will notice that the type passed to specialisations of this function template is a reference to a class template specialisation of std::iterator (in header utility).

I suspect then the ALL iterator types for this implementation would require deriving from a std::iterator specialisation. It seems that you may have started out from this or similar code. However try something like:

template<typename T, class D = ptrdiff_t >
class Iterator  
: public std::iterator<std::bidirectional_iterator_tag, T, D>
{
// ...
};

There is no point parameterising your iterator on its category, as just saying it is a random access iterator will not make it one and a bidirectional iterator is a forward iterator which is an input iterator.

For reference compare with the latest VC++ 2005 STL version of _Dist_type:

template<class _Iter> inline
  typename iterator_traits<_Iter>::difference_type
     * __CLRCALL_OR_CDECL _Dist_type(_Iter)
  {   // return distance type from arbitrary argument
  return (0);
  }

I suspect this would have worked better with your iterator class template definition.

I have only concerned myself with the immediate problem of the error you received due to all the initial time wasted finding out what was what, so you may find your iterator implementation needs a bit more work.

For more information on writing your own iterators, and the C++ standard library in general see "The C++ Standard Library A Tutorial and Reference" by Nicolai M. Josuttis. Also get a better C++ standard library implementation (see http://www.stlport.org/ http://www.dinkumware.com/) and maybe a compiler that understands more of standard C++ than VC6 does (see for example http://msdn.microsoft.com/vstudio/express/visualC/default.aspx).