Visual Studio 2019 年编辑了我的 C++ 代码并毁了我的迭代器

Question

我最近花了一些时间为 AVL 树设计一个迭代器（不过现在它只有插入机制；还没有实现树平衡）。我想测试迭代器，所以我检查了如何使其在线并决定通过拥有一个包含树节点的堆栈来实现它（例如，在正常的迭代堆栈中将包含 this->top 节点左侧的所有节点）。

迭代应该是这样工作的：

for (auto it = tree.iterator(); it.hasNext(); it.next())
{
    // process
}

但是，VS 更改（禁用）了我的 Iterator(const Iterator& it) 和 Iterator(Iterator&& it) 构造函数，然后迭代失败，因为堆栈始终为空。设置 Iterator() = delete; 后，我运行进入堆栈异常大且参数不可见的问题。

如果需要额外的信息，请随时询问。我认为最好直接粘贴相关代码，因为我不理解这种行为并且不知道我应该说什么细节：

avlTree<Key, Info>::iterator:

class Iterator
    {
    private:
        std::vector<Node*> stack;
        bool reverse;
        Node* ptr;

        std::vector<Node*> makeStack(Node* start, long height)
        {
            std::vector<Node*> newStack;
            newStack.reserve(height);
            while (start != nullptr)
            {
                newStack.push_back(start);
                if (reverse)
                    start = start->right;
                else
                    start = start->left;
            }
            return newStack;
        }

        Iterator(Node* start, long height, bool reverse = false) : reverse(reverse), ptr(nullptr)
        {
            stack = makeStack(start, height);
        }

        friend class avlTree;
    public:
        Iterator(Iterator&& iterator)
        {
            stack = move(iterator.stack);
            ptr = nullptr;
        }
        Iterator(const Iterator& iterator)
        {
            stack = iterator.stack;
            ptr = nullptr;
        }
        //Iterator() = delete;

        bool hasNext()
        {
            return stack.size() > 0;
        }
        void next()
        {
            if (!stack.size()) throw "Empty iterator stack";
            if (ptr == stack[stack.size() - 1])
            {
                stack.pop_back();
                if (reverse)        // fill the stack with the subsequent nodes (reverse or normal direction)
                {
                    Node* start = ptr->left;
                    while (start != nullptr)
                    {
                        stack.push_back(start);
                        start = start->right;
                    }
                }
                else
                {
                    Node* start = ptr->right;
                    while (start != nullptr)
                    {
                        stack.push_back(start);
                        start = start->left;
                    }
                }
            }
            if (stack.size() > 0)
                ptr = stack[stack.size() - 1];
        }
        const Key& getKey()
        {
            if (!ptr) throw "ptr is nullptr";
            else return ptr->key;
        }
        Info& getInfo()
        {
            if (!ptr) throw "ptr is nullptr";
            else return ptr->info;
        }
    };


main:

avlTree<char, int> tester;
for (char i = 'g'; i <= 'z'; ++i)
    tester.insert(i);
for (char i = 'a'; i < 'g'; ++i)
    tester.insert(i);

for (auto it = tester.iterator(); it.hasNext(); it.next())
{
    std::cout << it.getKey() << " ";
}

我在调试时得到的代码和消息的屏幕截图：http://prntscr.com/qi79zd

如何解决问题并使迭代工作？

编辑：

完整代码：

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <fstream>
#include <chrono>
#include <iterator>
#include <functional>
//#include <ctime>

template<typename T>
void swap(T& a, T& b)
{
    T temp = a;
    a = b;
    b = temp;
}

template<typename Key, typename Info>
class avlTree
{
private:
    struct Node
    {
        const Key key;
        Info info;
        Node* left;
        Node* right;
        long leftHeight, rightHeight;

        Node(const Key& key, Info&& info = Info(), Node* left = nullptr, Node* right = nullptr)
            : key(key), info(info), left(left), right(right), leftHeight(1), rightHeight(1) {}
        Node& operator()(Node* nleft, Node* nright)
        {
            left = nleft;
            right = nright;
            return *this;
        }
        Node& operator()(long left, long right)
        {
            leftHeight = left;
            rightHeight = right;
        }
    };

    Node* top;

    long length;

public:

    class Iterator
    {
    private:
        std::vector<Node*> stack;
        bool reverse;
        Node* ptr;

        std::vector<Node*> makeStack(Node* start, long height)
        {
            std::vector<Node*> newStack;
            newStack.reserve(height);
            while (start != nullptr)
            {
                newStack.push_back(start);
                if (reverse)
                    start = start->right;
                else
                    start = start->left;
            }
            return newStack;
        }

        Iterator(Node* start, long height, bool reverse = false) : reverse(reverse), ptr(nullptr)
        {
            stack = makeStack(start, height);
        }

        friend class avlTree;
    public:
        Iterator(Iterator&& iterator)
        {
            stack = move(iterator.stack);
            ptr = nullptr;
        }
        Iterator(const Iterator& iterator)
        {
            stack = iterator.stack;
            ptr = nullptr;
        }

        bool hasNext()
        {
            return stack.size() > 0;
        }
        void next()
        {
            if (!stack.size()) throw "Empty iterator stack";

            //stack.insert(stack.end(), vector.begin(), vector.end());
            if (ptr == stack[stack.size() - 1])
            {
                stack.pop_back();
                if (reverse)
                {
                    Node* start = ptr->left;
                    while (start != nullptr)
                    {
                        stack.push_back(start);
                        start = start->right;
                    }
                }
                else
                {
                    Node* start = ptr->right;
                    while (start != nullptr)
                    {
                        stack.push_back(start);
                        start = start->left;
                    }
                }
            }
            if (stack.size() > 0)
                ptr = stack[stack.size() - 1];
        }
        const Key& getKey()
        {
            if (!ptr) throw "ptr is nullptr";
            else return ptr->key;
        }
        Info& getInfo()
        {
            if (!ptr) throw "ptr is nullptr";
            else return ptr->info;
        }
    };

    avlTree()
    {
        this->top = nullptr;
        this->length = 0;
    }

    ~avlTree()
    {
        recursiveDelete(top);
        length = 0;
    }
    void printAsc()
    {
        for (auto it = iterator(); it.hasNext(); it.next())
        {
            std::cout << it.getKey() << " " << it.getInfo() << "\n";
        }
    }
    void printDesc()
    {
        recDesc(top);
    }

    void printTop()
    {
        if (top)    // != nullptr
        {
            std::cout << ".." << top->key << std::endl;
            if (top->left)
                std::cout << "." << top->left->key << "..";
            else std::cout << ".0..";
            if (top->right)
                std::cout << top->right->key << std::endl;
            else std::cout << "0" << std::endl;
        }
    }

    void insert(const Key& key);
    long height()
    {
        return !top ? 0 : top->leftHeight > top->rightHeight ? top->leftHeight : top->rightHeight;
    }

private:
    void recDesc(Node* parent);
    void recursiveDelete(Node* parent);
    void insertRecursive(Node* parent, const Key& key, int& depth);

//  void rightRotation(Node* top, Node* parent = nullptr);
public:

    Iterator iterator()
    {
        return Iterator(top, height());
    }

};

std::vector<std::string> readFile(bool toDarwin = true);

/****************************************************************************/

int main()
{
    // auto start = std::chrono::system_clock::now();
    avlTree<std::string, int> counter;

    avlTree<char, int> tester;
    for (char i = 'g'; i <= 'z'; ++i)
        tester.insert(i);
    for (char i = 'a'; i < 'g'; ++i)
        tester.insert(i);

    for (auto it = tester.iterator(); it.hasNext(); it.next())
    {
        std::cout << it.getKey() << " ";
    }

    return 0;
}

/****************************************************************************/

template<typename Key, typename Info>
void avlTree<Key, Info>::recDesc(Node* parent)
{
    if (parent->left != nullptr)
        recAsc(parent->left);

    std::cout << parent->key;

    if (parent->right != nullptr)
        recAsc(parent->left);
}

template<typename Key, typename Info>
void avlTree<Key, Info>::recursiveDelete(Node* parent)
{
    if (!parent) return;
    if (parent->left != nullptr)
        recursiveDelete(parent->left);
    if (parent->right != nullptr)
        recursiveDelete(parent->right);
    delete parent;
}

template<typename Key, typename Info>
void avlTree<Key, Info>::insertRecursive(Node* parent, const Key& key, int& depth)
{
    if (parent->key == key)
        ++(parent->info);
    else if (parent->key > key)
    {
        if (parent->left == nullptr)
        {
            parent->left = new Node(key);
            ++(parent->left->info);
            ++length;
            depth = 1;
            // (* parent->left)(depth, depth)
        }
        else
        {
            insertRecursive(parent->left, key, depth);
            ++depth;
            parent->leftHeight = depth;
        }
    }
    else if (parent->key < key)
    {
        if (parent->right == nullptr)
        {
            parent->right = new Node(key);
            ++(parent->right->info);
            ++length;
            depth = 1;
            // (* parent->right)(depth, depth)
        }
        else
        {
            insertRecursive(parent->right, key, depth);
            ++depth;
            parent->rightHeight = depth;
        }
    }
}

template<typename Key, typename Info>
void avlTree<Key, Info>::insert(const Key& key)
{
    int depth = 0;
    if (!top)
    {
        top = new Node(key);
        // (*top)(1, 1)
        ++length;
        ++(top->info);
    }
    else
    {
        insertRecursive(top, key, depth);
        ++depth;
        top->key > key ? ++(top->leftHeight) : top->key < key ? ++(top->rightHeight) : NULL;
    }
}

/* Irrelevant to the problem
std::vector<std::string> readFile(bool toDarwin)
{
    // shrink_to_fit()
    std::ifstream file;
    std::string word;

    std::vector<std::string> words;
    words.reserve(1000000);

    if (toDarwin == 1)
        file.open("OnTheOriginOfSpecies.txt");
    else
        file.open("The_bible.txt");

    while (file >> word)
    {
        words.push_back(word);
    }
    words.shrink_to_fit();
    return words;
}
*/

Answer 1

我认为问题在于您没有意识到 RVO - return 值优化。大多数编译器都这样做，事实上它在 C++17 中是强制性的。什么是 RVO？

class A;

A func()
{
     A a_infunc = {};
     return a_infunc;
}

//use
A a_outsidefunc = func();

在这个简单的示例中，没有调用 A::A(const A&) 或 A::A(A&&)。 a_infunc 与 a_outsidefunc 是完全相同的变量。

因此在 for 循环中：

for (auto it = tree.iterator(); it.hasNext(); it.next())
{
    // process
}

由于 RVO，将不会调用 Iterator(const Iterator& it) 或 Iterator(Iterator&& it)。

Visual Studio 2019 年编辑了我的 C++ 代码并毁了我的迭代器

Visual Studio 2019 Edits My C++ Code And Ruins My Iterator

c++

tree

binary-tree

iterator

visual-studio