0

I'm implementing a bidirectional iterator of my B-Tree implementation. (Full code: https://wandbox.org/permlink/i4UeEvE3OB6mVup3)

In short, I'm stuck in reversing the direction.

Node implementation:

class Node {
        std::size_t n = 0;
        bool leaf = true;
        Node* parent = nullptr;
        std::size_t index = 0;
        std::vector<T> key;
        std::vector<std::unique_ptr<Node>> child;
        // details ...
};

My correct forward iterator implementation:

    class BTreeIterator {
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        // using iterator_category = std::bidirectional_iterator_tag;
        using iterator_category = std::forward_iterator_tag;
        
        Node* node;
        std::vector<T>::iterator it;
        
        void Increment() {
            if (it == node->key.end()) {
                return;
            }
            if (node->leaf) {
                ++it;
                while (node->parent && it == node->key.end()) {
                    it = node->parent->key.begin() + node->index;
                    node = node->parent;
                }
            } else {
                auto i = std::distance(node->key.begin(), it);
                node = node->child[i + 1]->LeftmostLeaf();
                it = node->key.begin();
            }
        }
        
    public:
        BTreeIterator(Node* node, std::size_t i) : node {node} {
            assert(node && i <= node->key.size());
            it = node->key.begin() + i;
        }
        
        reference operator*() const {
            return *it;
        }
        
        pointer operator->() const {
            return it;
        }
        
        BTreeIterator& operator++() {
            Increment();
            return *this;
        }
        
        BTreeIterator operator++(int) {
            BTreeIterator temp = *this;
            Increment();
            return temp;
        }
        
        friend bool operator==(const BTreeIterator& x, const BTreeIterator& y) {
            return x.node == y.node && x.it == y.it;
        }
        
        friend bool operator!=(const BTreeIterator& x, const BTreeIterator& y) {
            return !(x == y);
        }
    };

My failed attempt to implement operator--:

// ...
        void Decrement() {
            if (it == node->key.rend()) {
                return;
            }
            if (node->leaf) {
                --it;
                while (node->parent && it == node->key.rend()) {
                    it = node->parent->key.rbegin() + (node->getN() - node->index);
                    node = node->parent;
                }
            } else {
                auto i = std::distance(node->key.rbegin(), it);
                node = node->child[getN() - i - 1]->RightmostLeaf();
                it = node->key.rbegin();
            }
        }
// ...
        BTreeIterator& operator--() {
            Decrement();
            return *this;
        }
        
        BTreeIterator operator--(int) {
            BTreeIterator temp = *this;
            Decrement();
            return temp;
        }

Because it is std::vector<T>::iterator, it fails to assign .rbegin() or .rend() of std::vector<T>, which is std::vector<T>::reverse_iterator.

Is there any way to get the address of pointer of std::vector<T>::reverse_iterator to make a std::vector<T>::iterator? I really need "before-one-the-begin" address to make ease Decrement() implementation.

frozenca
  • 839
  • 4
  • 14
  • There is no magic behind a reverse iterator. Internally, a reverse iterator holds a normal iterator (see `base()` member function). But that iterator `it` points to the element *after* the current element. That is, when you dereference a reverse iterator, you do `*std::prev(it)`. You can't have an iterator one element before `begin()`. This is not allowed by the standard. – Evg Aug 22 '20 at 07:32
  • check this https://stackoverflow.com/questions/2037867/can-i-convert-a-reverse-iterator-to-a-forward-iterator – Harry Aug 22 '20 at 07:39
  • Fine, I've done the job with using ```begin()``` only. It was just like a mediocre algorithm textbook problem, I was too scared for some reason. – frozenca Aug 22 '20 at 07:52

1 Answers1

0

Self-answer: I cannot get before-one-the-begin in any way.

I have to just implement it differently.

Correct implementation of Decrement():

void Decrement() {
            auto i = std::distance(node->key.begin(), it);
            if (!node->leaf) {
                node = node->child[i]->RightmostLeaf();
                it = node->key.begin() + node->key.size() - 1;
            } else {
                if (i > 0) {
                    --it;
                } else {
                    while (node->parent && node->index == 0) {
                        node = node->parent;
                    }
                    if (node->index > 0) {
                        it = node->parent->key.begin() + node->index - 1;
                        node = node->parent;
                    }
                }
            }
            
        }
frozenca
  • 839
  • 4
  • 14