Constant iterator and code duplication

[VoB]

Implementing a binary search tree, I need to write a iterator and a constant_iterator.


My iterator has to be templated on nodeType and pairType, as I did here:

template <typename nodeType, typename pairType >
struct _iterator {

    nodeType* current;
    
    //public:
    using value_type = pairType;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
    using reference = value_type&;
    using pointer = value_type *;
    

    explicit _iterator(nodeType* pn) noexcept: current{pn} {}

    //implementation of all the other functions 

and in the definition of my binary search tree class I have the following typedefs:

    using iterator = _iterator<node_type,pair_type>;
    
    using constant_iterator = _iterator<node_type,const pair_type>;

Actually, nodeType=Node<pair_type>, since the Node is templated on pair_type. So I decided to template my iterator on the pair_type only, but now it doesn't work anymore when I want to use in my code the constant version, which is "typedef"ed in this way:

    using iterator = _iterator<pair_type>;
    
    using constant_iterator = _iterator<const pair_type>; //this creates problem 

because when I use the constant version he can't construct the iterator, for instance in the cbegin function call. Why do I have problems if I give just one template? The problems appear to be in the constructor, but I can't understand how.

[coder777]

You did not provide enough code to reproduce the problem. Please provide a minimal compilable expample.

One possible problem might be that with constant members no copy constructor will be generated by the compiler. In that case you need to provide your own.

[VoB]

Here's the minimal working example. I split everything into three files: Node.h, Iterator.h, bst.h and in the main.cpp I call the function cbegin.

In the bst.h file I wrote a comment with capital letters to indicate where comes from the source of the error, which I think is

using constant_iterator = _iterator<const pair_type>;


and I can't understand why I can't define the template to be const.


The Node.h file:

#include <iostream>
#include <memory>

template <typename T>
struct Node{
    T data;
    std::unique_ptr<Node<T>> left;
    
    std::unique_ptr<Node<T>> right;
    
    Node<T>* parent;
    

    explicit Node(const T& _data): data{_data}, left{nullptr}, right{nullptr},parent{nullptr}{}

    Node(): data{},left{nullptr}, right{nullptr},parent{nullptr}{}
 
};


#endif /* Node_h */ 

--------- Here's the iterator file -------

#ifndef Iterator_h
#define Iterator_h

#include "Node.h"
#include <iterator>
#include <utility>



template <typename pair_type> //pair_type will be std::pair
struct _iterator {
    using nodeType = Node<pair_type>;
    
    nodeType* current;
    
    //public:
    using value_type = pair_type;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
    using reference = value_type&;
    using pointer = value_type *;
    

    explicit _iterator(nodeType* pn) noexcept: current{pn} {}
    
    };
    
#endif /* Iterator_h */ 

--------- Here's the bst file -------

#ifndef bst_h
#define bst_h


#include "Iterator.h"

 

template <typename key_type, typename value_type >
class bst{
    
   
    using pair_type = std::pair< const key_type, value_type>;
   
    using node_type = Node<pair_type>;

    using iterator = _iterator<pair_type>;

    using constant_iterator = _iterator<const pair_type>; //HERE'S THE PROBLEM, I THINK

private:
    std::unique_ptr<Node<pair_type>> head; //unique pointer to the root/head Node
    
    
public:

    bst(): head{nullptr}{}
        
    
    
    iterator begin() noexcept{
        if (!head) {
            return iterator{nullptr};
        }
        auto ptr{head.get()};
        while (ptr->left) {
            ptr=ptr->left.get();
        }
        return iterator{ptr};
    }

    constant_iterator cbegin() const noexcept{
        if (!head) {
            return constant_iterator{nullptr};
        }
        auto ptr{head.get()};
        while (ptr->left) {
            ptr=ptr->left.get();
        }
        return constant_iterator{ptr};
    }
   
};
    
    
#endif /* bst_h*/

and, finally, the main.cpp file

#include "bst.h"

int main() {
        

    bst<int,int> my_tree{};
    auto it{my_tree.cbegin()};

    return 0;
}

and I got the following compiler error:

./bst.h:83:16: error: no matching constructor for initialization of 'bst<int, int>::constant_iterator' (aka '_iterator<const pair<const int, int> >')
return constant_iterator{ptr};
^ ~~~~~

[coder777]

The problem is in bst line 22/45: You have a pointer to Node<pair_type>. The constant_iterator requires Node<const pair_type> which are different types.

Is it necessary to have this different types?

[VoB]

Uhm, the only necessary thing is to have a constant iterator.

Actually, your comment enlightened me (maybe).

Since a constant iterator must point to something constant, and my iterator is pointing to a Node, now I think that I should impose that the Node is constant, rather than the pair itself as I was doing. In practice, what I want to be constant is Node<T>, where T will be a std::pair with key and value

Do you agree with this?

[coder777]

const Node<T> * would make its member data const. Also left, right, parent. That means you cannot directly use it modify the tree.

Maybe something like this:

template <typename pair_type, typename value_type = pair_type> //pair_type will be std::pair
struct _iterator {
    using nodeType = Node<pair_type>;
    
    nodeType* current;
    
    //public:
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
    using reference = value_type&;
    using pointer = value_type *;
    

    explicit _iterator(nodeType* pn) noexcept: current{pn} {}
    
    };

...

    using constant_iterator = _iterator<pair_type, const pair_type>;

This would make the value_type const and keeps the node as it is

[VoB]

So if you think to a constant iterator for your bst, you would like to have constantness only for each std::pair, and not for children?

This sounds strange to me, because if I can still modify something (for instance left, right, parent), I wouldn't say that the iterator is pointing to something constant.

I do not wish to be controversial, my question is just pure curiosity :-)



Anyway, I think I got your workaround. Now I'll try to follow the flow of the code to check it more carefully.

[coder777]

In that case neither the children nor the parent are const. Only the pointer to them.

This sounds strange to me, because if I can still modify something (for instance left, right, parent), I wouldn't say that the iterator is pointing to something constant.

It's not that strange. The node is for internal while the data for external use. So that the user of your class bst never gets in touch with the node.

But it entirely depends on what you want to achieve.

The standard container behave like that. I.e. you can use const_iterator for removing/adding etc. The only restriction is that you get const data for reference (operator->) or dereference (operator*)