C ++ вне диапазона при использовании вектора - PullRequest
Новая
       35

C ++ вне диапазона при использовании вектора

0 голосов
/ 03 мая 2018

Итак, я создал дерево двоичного поиска (BST), поместив узлы в вектор. Эти узлы хранят 3 значения: пользовательский ввод int ID, пользовательский ввод int age и пользовательское string имя ввода.

При вставке этих узлов в вектор они сохраняются в порядке возрастания.

В настоящее время я работаю с двумя узлами.

104 10 Боб

102 11 Стив

При отталкивании первого узла проблем нет; однако, при попытке отодвинуть второй узел, я получаю ошибку 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();

Буду признателен за помощь! Спасибо!

Ответы [ 2 ]

0 голосов
/ 03 мая 2018

std::vector имеет методы, отличные от push_back для вставки элементов. В частности, insert занимает позицию, где новый элемент должен быть вставлен. 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
}

Кроме того, ваш insert метод, зная о start, является утечкой предположений, которые вы позже захотите изменить. Было бы намного лучше содержать все это в 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;
        }
    }
}
0 голосов
/ 03 мая 2018

Ваш вектор не изменяется, когда вы делаете это: 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 без сбоев, тогда ваша вставка () должна выглядеть так: 

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 отсортировано по возрастанию: enter image description here

...