我最近花了一些时间为 AVL 树设计一个迭代器（现在它只有插入机制；还没有实现树平衡）。我想测试迭代器，所以我检查了如何使其在线并决定通过拥有一个包含树节点的堆栈来实现它（例如，在正常迭代堆栈中将包含节点左侧的所有this->top节点）。
这就是迭代应该如何工作：
for (auto it = tree.iterator(); it.hasNext(); it.next())
{
// process
}
但是，VS 更改（禁用） myIterator(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;
}
*/
我相信问题在于您不知道 RVO - 返回值优化。大多数编译器都这样做，实际上它在 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)由于 RVO。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句