C++ 中的二叉树迭代器适用于 T=int，但不适用于 T=std::string

Question

我用 C++ 实现了一个带有迭代器的二叉树。但是，只有当模板参数 (T) 设置为 int 时，它才能正确运行。当尝试使用 std::string 作为模板参数时，迭代器不起作用，并且出现分段错误错误。我不知道为什么。我希望有人能指出错误和/或提供带有解释的解决方案。

#include <iostream>

#include <memory>
#include <iterator>
#include <iostream>
namespace binary_search_tree {

    template <typename T>
    struct binary_tree {
        std::unique_ptr<T> data_node;
        binary_tree<T>* parent = nullptr;
        std::unique_ptr<binary_tree<T>> left_node;
        std::unique_ptr<binary_tree<T>> right_node;


        std::unique_ptr<binary_tree<T>>& left() {
            if (left_node) {
                std::cout << "left: " << "\t";
                std::cout << left_node.get();
                return left_node;
            }
            return left_node;
            //throw std::logic_error("Left child is NULL");

        }

        std::unique_ptr<binary_tree<T>>& right() {
            std::cout << "\n Using right: " << "\t";
            if (right_node) {
                std::cout << "right: " << "\t";
                return right_node;
            }
            return right_node;

        }

        T data() {
            if (this) {
                if (this->data_node) {
                    return *this->data_node;
                }
            }
            //throw std::logic_error("Data is NULL");
        
        }

        void insert(T data) {
            if (!this->data_node) {
                this->data_node = std::make_unique<T>(data);

            }
            else {
                if (data > *this->data_node) {
                    if (!this->right_node) {
                        this->right_node = std::make_unique<binary_tree<T>>(this);
                    }
                    (*this->right_node).insert(data);

                }
                else {
                    if (!this->left_node) {
                        this->left_node = std::make_unique<binary_tree<T>>(this);
                    }
                    (*this->left_node).insert(data);

                }

            }

        }



        binary_tree<T>(T data) {
            this->insert(data);
            return;
        }

        binary_tree<T>() {
            return;
        }

        binary_tree<T>(binary_tree<T>* parent_ptr) {
            this->parent = parent_ptr;
            return;
        }

        struct iterator {
            binary_tree<T>* current;
            binary_tree<T>* root;
            binary_tree<T>* end;


            bool operator==(iterator other) const {
                return current == other.current;
            }
            bool operator!=(iterator other) const {
                return current != other.current;
            }

            void operator++() {
                //check if current is valid
                if (!current) {
                    return;
                }
                //if current reaches last leafe 
                if (current == root->findEndRightLeaf(this->root)) {
                    current = nullptr;
                    return;
                }

                if (current && current->right_node) {
                    // Move to the leftmost leaf of the right subtree
                    current = current->findStartLeftLeaf(current->right_node.get());
                }
                else if (current && current->parent && current == current->parent->left_node.get()) {
                    // Move up to the parent if it's the left child
                    current = current->parent;
                }
                else {
                    // Move upward until a left child is encountered or reach the end
                    while (current && current->parent && current == current->parent->right_node.get()) {
                        current = current->parent;
                    }
                    if (current && current->parent) {
                        // Move to the parent if it's a left child
                        current = current->parent;
                    }
                }
            }
            const T& operator*() {
                if (current) {
                    return current->data();
                }
                else {
                    // Handle the case when trying to dereference the end iterator
                    throw std::out_of_range("Dereferencing in iterator is not valid");
                }
            }
            iterator() {
                ;
            }
            iterator(binary_tree<T>* tree_pointer) : current(tree_pointer), root(tree_pointer), end(nullptr) {
                if (tree_pointer) {
                    this->root = tree_pointer->findRoot(tree_pointer);
                }
                else {
                    this->root = tree_pointer;
                }
            }
            iterator(const iterator& tree_iterator) : current(tree_iterator.current), root(tree_iterator.current), end(nullptr) {
                if (tree_iterator.current) {
                    this->root = this->current->findRoot(this->current);
                }
                else {
                    this->root = tree_iterator.current;
                }
            
            }
        };

        const iterator begin() {
            if (this) {
                binary_tree<T>* leftmostLeaf = findStartLeftLeaf(this);
                return iterator(leftmostLeaf);
            }

        }
        const iterator end() {
            return iterator(nullptr);
        }

        binary_tree<T>* findStartLeftLeaf(binary_tree<T>* node) {
            while (node && node->left_node) {
                node = node->left_node.get();
            }
            return node;
        }
        binary_tree<T>* findRoot(binary_tree<T>* node) {
        
            while (node && node->parent) {
                node = node->parent;
            }
            return node;
        }
        binary_tree<T>* findEndRightLeaf(binary_tree<T>* node) {
            while (node && node->right_node) {
                node = node->right_node.get();
            }
            return node;
        }
    };


}

using namespace binary_search_tree;



int main()
{
    //works with integers
    binary_tree<int> tree_int(2);
    tree_int.insert(3);
    tree_int.insert(1);
    tree_int.insert(7);
    tree_int.insert(0);
    tree_int.insert(1);
    tree_int.insert(1);

    std::cout << "Tree elements (int)  \n";
    for (const auto& value : tree_int) {
        std::cout << "value:\t" << value << "\n";
    }


    //fails with strings
    binary_tree<std::string> tree_str("hi");

    tree_str.insert("2");
    tree_str.insert("6");


    std::cout << "Tree elements (string) \n ";
    for (const auto& value : tree_str) {
        std::cout << "value:\t" << value << "\n";
    }

    return 0;
}

预先感谢您的协助。

Answer 1

我在这段代码中看到了多个未定义行为：

• this

  永远不可能合法地成为

  nullptr

  （编译器可以根据该假设进行优化），因此never使用

  if (this)

  。此外，在

  nullptr

  对象指针上调用方法无论如何都是 UB。

• 如果

  data()

  是 this->data_node，则您的

  nullptr

  方法具有

  UB

  ，因为在这种情况下它根本不

  return

  任何东西。

• data()

  返回按值，但迭代器的

  operator*

  返回

  data()

  值按引用，所以你返回一个悬挂引用，即UB。