0

So i have a container for which i define my own iterators. In my example its a Skiplist but the type dowsnt matter.

I implemented begin() and end() and i was wonder how to implement cbegin() and cend().

Is there a way to convert iterator to const_iterator?

Here my simplified implementation:

class Skiplist {
public:
    using key_type = int;
    using mapped_type = int;
    using value_type = std::pair<const key_type, mapped_type>;
    using size_type = std::size_t;

    template<typename IT> class iterator_base;          // template class for iterator and iterator const   

    using iterator = iterator_base<value_type>;
    using const_iterator = iterator_base<value_type const>;

    //....

    // Iterators
    iterator begin() noexcept;
    iterator end() noexcept;
    const_iterator cbegin() const noexcept;     // can this be made by convert iterator to const iterator?
    const_iterator cend() const noexcept;

    //....
private:
    struct Skipnode;                // forward declaration so Basenode can have Skiplist*

    struct Basenode {                                       // Empty node, mainly created to represent head element. 
                                                            // Is there a way to get a empty head with no key / values without using this ?
        Basenode(int in_level);
        Basenode(const std::vector<Skipnode*>& in_next);

        std::vector <Skipnode*> next;
    };

    struct Skipnode : Basenode {                        // derived so with Basenode* we can start the iteration of the node on head
        Skipnode(value_type val, int in_level);
        Skipnode(value_type val, const std::vector<Skipnode*>& in_next);

        value_type value;       // first key / second mapped type = value
    };

    //....
};


template<typename IT>
class Skiplist::iterator_base {
public:
    iterator_base(Skiplist::Skipnode* pos)
        : curr{ pos }
    {
    };

    //...

    IT& operator*() { return curr->value; }
    IT* operator->() { return &curr->value; }

private:


    Skiplist::Skipnode* curr;
};



Skiplist::iterator Skiplist::begin() noexcept
{
    if (head.next.empty()) return Skiplist::iterator{ nullptr };

    return Skiplist::iterator{ head.next[0] };
}

Skiplist::iterator Skiplist::end() noexcept
{
    if (head.next.empty()) return Skiplist::iterator{ nullptr };

    Basenode* current_position = &head;
    while (current_position->next[0] != nullptr)
        current_position = current_position->next[0];

    return Skiplist::iterator{ current_position->next[0] };
}

Skiplist::const_iterator Skiplist::cbegin() const noexcept
{
    if (head.next.empty()) return Skiplist::const_iterator{ nullptr };

    return Skiplist::const_iterator{ head.next[0] };
}

Skiplist::const_iterator Skiplist::cend() const noexcept
{
    if (head.next.empty()) return Skiplist::const_iterator{ nullptr };

    const Basenode* current_position = &head;
    while (current_position->next[0] != nullptr)
        current_position = current_position->next[0];

    return Skiplist::const_iterator{ current_position->next[0] };
}

It is very repetive with cbegin and cbegin.

So the question is, what is missing to convert iterator to const_iterator. I tryed const_cast and static_cast but obiously its not working.

EDIT: from the comment i tryed to make a implicit constructor but it still doesnst seem to word. Here what i tryed.

//the constructor in the iterator class:
        iterator_base(const iterator_base<IT>& it)
            : curr{ it.curr }
        {
        }

    Skiplist::const_iterator Skiplist::cbegin() const noexcept
    {
        if (head.next.empty())
            return Skiplist::const_iterator{ nullptr };

        return Skiplist::const_iterator{ begin() };     // this doesnt work
    }
Sandro4912
  • 313
  • 1
  • 9
  • 29
  • The `const_iterator` type would need a (probably implicit) constructor that takes a single `iterator` or your `iterator` type would need a (probably implicit) cast operator to `const_iterator`. As it is, there doesn't exist a relationship between those two types that would allow for a conversion. – François Andrieux Jul 05 '18 at 18:41
  • So basically i need a copy constructor which is not explicit ? – Sandro4912 Jul 05 '18 at 18:48
  • With an implicit copy (or move) constructor from iterator to const_iterator you could make your cbegin/cend just wrappers around begin/end, returning const_iterator. That's the least repetitive way I can think of, at the cost of that copy/move constructor, which may be optimized away. – Rain Jul 05 '18 at 19:13
  • @Sandro4912 No, `const_iterator`'s copy constructor will allow you to copy from another `const_iterator` but not from an `iterator`. For that, `iterator` would have to already be implicitly convertible to `const_iterator` (which is the goal in the first place). You would need an implicit `const_iterator(iterator)` constructor which is not a copy constructor. – François Andrieux Jul 05 '18 at 19:13
  • 2
    @FrançoisAndrieux is using the correct terminology... It is not a **copy** constructor, just a constructor. The `iterator` is not being copied. a `const_iterator` is being constructed from it. – Rain Jul 05 '18 at 19:24
  • since the `iterator` and `const_iterator` are created from a template the constructor should be in the template but how should be the format? – Sandro4912 Jul 05 '18 at 19:48
  • Make a templated utility function and call it from begin and cbegin. Btw you're missing the `const begin` function, which should also return `const_iterator` – rustyx Jul 05 '18 at 20:54
  • isnt const begin the cbegin function? – Sandro4912 Jul 06 '18 at 04:21
  • @Sandro4912 no, `vector` etc have three functions `iterator begin()`, `const_iterator begin() const` and `const_iterator cbegin() const`. `cbegin` is for when you explicitly want const (although I prefer `std::as_const`ing the container) – Caleth Jul 06 '18 at 10:39

1 Answers1

2

A simple solution is to add a bool is_const template parameter to your base_iterator and adapt the types and disable non-const access depending on this parameter.

Sample code:

template<typename IT, bool is_const> class iterator_base;

using iterator = iterator_base<value_type, /*is_const=*/false>;
using const_iterator = iterator_base<value_type, /*is_const=*/true>;

// ...

template<typename IT, boo is_const>
class Skiplist::iterator_base {
    public:
         using node_type = typename std::conditional<is_const, Skiplist::Skipnode const, Skiplist::Skipnode>::type;
         using value_type = typename std::conditional<is_const, IT const, IT>::type;

    iterator_base(node_type* pos) : curr{ pos }{};

    value_type & operator*() const { return curr->value; }
    value_type * operator->() const { return &curr->value; }

private:
    node_type* curr;
};

Concerning end()and cend(), you can simply define iterator_base(nullptr) to be the end of the string. Your code is useless:

while (current_position->next[0] != nullptr)
    current_position = current_position->next[0];

// ***** current_position->next[0] == nullptr ******
return Skiplist::iterator{ current_position->next[0] };
Michael Doubez
  • 5,937
  • 25
  • 39
  • Note that inheriting `std::iterator::type;>` would be a good idea. – Michael Doubez Jul 06 '18 at 10:36
  • so you mean taking most of the stuff i have in my iterator from inheriting from the standard forward iterator – Sandro4912 Jul 09 '18 at 16:20
  • regarding youre second snippet `return Skiplist::iterator{ current_position->next[0] };` isnt necessary nullptr it can be also the next element. you mean that i just return nullptr to indicate end. Because `nullptr` is `nullptr` ? – Sandro4912 Jul 09 '18 at 17:12
  • The loop condition just before is that it doesn't stop iterating until `current_position->next[0]` is nullptr. That's the usual way to mark the end of a linked list. – Michael Doubez Jul 09 '18 at 19:59
  • the standard forward iterator is only for defining traits of your iterator that are used in STL. – Michael Doubez Jul 09 '18 at 20:00
  • `std::iterator` was deprecated with C++17 (see e.g. [here](https://stackoverflow.com/a/43268283/1969455)) so inheriting from it is likely not such a good idea anymore. Instead one needs to write out the member types oneself. (I would start with that even pre-C++17) – Brandlingo Sep 14 '22 at 11:53
  • Yes. I should have said that it was a good idea to define the traits and that inheriting std::iterator is the shortest way to do it. If you have to write the boilerplate for the sake of clarity - here we are, here we go. Thanks for the clarification. – Michael Doubez Sep 15 '22 at 16:03