使用 Vector 时 C++ 超出范围

Question

所以我通过将节点放入向量中创建了二叉搜索树 (BST)。这些节点存储 3 个值，用户输入 int ID，用户输入 int 年龄，用户 string 输入姓名。

将这些节点插入向量时，它们按升序存储。

目前我正在使用两个节点。

104 10 鲍勃

102 11 史蒂夫

推回第一个节点时，没有问题；然而，当我试图推回第二个节点时，我收到了向量 class 抛出的 out_of_bounds 错误。

我认为我的插入函数在尝试切换这两个节点的位置时出现了问题，但我无法准确判断问题出在哪里。

#include "BinaryTree.h"
#include <string>
#include <iostream>
#include <vector>

using namespace std;
int index;

struct Node
{
    int ID;
    int age;
    string name;

    Node()
    {

    }

    Node(int id, int Age, string nm)
    {
        this->ID = id;
        this->age = Age;
        this->name = nm;
    }
};

vector<Node> binaryTree;


BST::BST()
{

}



void BST::start()
{
    int choice;


    cout << "What would you like to do?" << endl;
    cout << "1. Add a node to the tree" << endl;
    cout << "2. Delete a node from the tree" << endl;
    cout << "3. Find a node in the tree" << endl;
    cout << "4. Report the contents of the tree" << endl;
    cout << "5. Exit program" << endl;

    cin >> choice;

    if (choice == 1)
    {
        insert();
    }

    if (choice == 3)
    {
        find();
    }

    if (choice == 4)
    {
        report();
    }


}


void BST::insert()
{

    int ID;
    int AGE;

    string NAME;

    cout << "Please enter the ID number, age and name" << endl;
    cin >> ID >> AGE >> NAME;

    Node *tree = new Node(ID, AGE, NAME);

    if (index == 0)
    {
        binaryTree.push_back(*tree);
        index++;
    }

    if (index > 0)
    {
        if ((binaryTree.at(index - 1).ID) < ID)
        {
            binaryTree.push_back(*tree);
            index++;
        }
    }


    if (index > 0)
    {
        if ((binaryTree.at(index - 1).ID) > ID)
        {
            Node *temp = new Node();
            *temp = binaryTree.at(index - 1);
            binaryTree.at(index - 1) = *tree;

            binaryTree.at(index) = *temp;
            index++;
        }
    }

    cout << "Added! Size: " << binaryTree.size() << endl;
    cout << " " << endl;
    start();

非常感谢您的帮助！谢谢！

Answer 1

执行此操作时矢量不会调整大小：binaryTree.at(index) = *tree;

执行push_back()然后尝试排序

binaryTree.push_back(*tree;)
std::sort(binaryTree.begin(),binaryTree.end(),[](const Node& n1, const Node& n2){//do your comparations});

或者直接使用std::set

如果你想在不崩溃的情况下使用 std::vector，那么你的 insert() 必须如下所示：

void BST::insert()
{
    int ID;
    int AGE;

    string NAME;

    cout << "Please enter the ID number, age and name" << endl;
    cin >> ID >> AGE >> NAME;

    //Node *tree = new Node(ID, AGE, NAME); // Don't use new here, there is no need in this
    Node tree(ID, AGE, NAME);

    binaryTree.push_back(tree);
    std::sort(binaryTree.begin(), binaryTree.end(), [](const Node& n1, const Node& n2)
          {
              //compare your nodes here
              return (n1.ID > n2.ID);
          });

    cout << "Added! Size: " << binaryTree.size() << endl;
    cout << " " << endl;
    start();
}

但这不会是二叉树。您需要其他数据结构来创建二叉树，std::vector 不能是二叉树。有一个现成的解决方案，请查看 std::set，它会根据需要插入元素，您需要将自定义比较函数添加到 std::set，一切都会好起来的。这是给你的 std::set 示例：

class Node
{
public:
    Node(int id):ID(id){}
    int ID;
};

class NodeComparator
{
public:
    bool operator()(const Node& n1,const Node& n2)
    {
        return n1.ID < n2.ID;
    }
};

int main()
{
    std::set<Node, NodeComparator> set1;
    set1.insert(10);
    set1.insert(8);
    set1.insert(14);
    set1.insert(2);

    return 0;
}

这是您需要的，std::set 升序排列：

Answer 2

std::vector 有不同于 push_back 的插入元素的方法。具体来说，insert takes a position, where the new element is to be inserted. emplace 更好，因为您甚至不必创建要复制到向量中的元素，只需传递构造函数参数即可。

您可以在 std::lower_bound 找到合适的插入位置。

#include <algorithm>

void BST::insert()
{
    int ID;
    int AGE;
    std::string NAME;

    std::cout << "Please enter the ID number, age and name" << std::endl;
    std::cin >> ID >> AGE >> NAME;

    auto pos = std::lower_bound(binaryTree.begin(), binaryTree.end(), 
        [](const Node& n1, const Node& n2) { return (n1.ID > n2.ID); });

    binaryTree.emplace(pos, ID, AGE, NAME);

    std::cout << "Added! Size: " << binaryTree.size() << endl;
    std::cout << " " << std::endl;
    // start(); // dubious, see below
}

顺便说一句，您了解 start 的 insert 方法泄露了您以后可能想要更改的假设。最好将所有内容包含在 start 内，例如：

void BST::start()
{
    std::cout << "What would you like to do?" << std::endl;
    std::cout << "1. Add a node to the tree" << std::endl;
    std::cout << "2. Delete a node from the tree" << std::endl;
    std::cout << "3. Find a node in the tree" << std::endl;
    std::cout << "4. Report the contents of the tree" << std::endl;
    std::cout << "5. Exit program" << std::endl;

    for(int choice; (std::cin >> choice) && (choice != 5);)
    {   
        switch (choice)
        {
        case 1: insert(); break;
        case 3: find(); break;
        case 4: report(); break;
        }
    }
}

使用 Vector 时 C++ 超出范围

C++ Out Of Range When using Vector

c++

vector

push-back

nodes

indexoutofboundsexception