时间戳

首页 > 解决方案 > C++：实现B树的双向迭代器

c++ - C++：实现B树的双向迭代器

问题描述

我正在实现我的 B-Tree 实现的双向迭代器。（完整代码：https ://wandbox.org/permlink/i4UeEvE3OB6mVup3 ）

简而言之，我被困在逆转方向。

节点实现：

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 ...
};

我正确的前向迭代器实现：

    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);
        }
    };

我实施失败的尝试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;
        }

因为itis std::vector<T>::iterator，它未能分配.rbegin()or .rend()of std::vector<T>，即 is std::vector<T>::reverse_iterator。

有什么方法可以获取指针的地址std::vector<T>::reverse_iterator来制作 astd::vector<T>::iterator吗？我真的需要“在一个开始之前”的地址来简化Decrement()实施。

标签： c++treeiterator

解决方案

自我回答：我无法以任何方式提前开始。

我必须以不同的方式实现它。

正确执行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;
                    }
                }
            }
            
        }

推荐阅读