C ++ Как удалить узлы в векторе - PullRequest
Новая
       63

C ++ Как удалить узлы в векторе

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

Итак, я создал двоичное дерево поиска, которое хранится в массиве. Это двоичное дерево поиска (BST) хранит введенный пользователем идентификатор, возраст и имя, а затем помещает его в массив, отсортированный по возрастанию по идентификатору.

Я пытаюсь написать функцию удаления, которая принимает идентификатор пользовательского ввода, проходит по вектору и, если находит соответствующий идентификатор, удаляет его.

Однако я не могу заставить BinaryTree.erase () работать из-за ошибки. 

Severity    Code    Description Project File    Line    Suppression State
Error (active)  E0304   no instance of overloaded function "std::vector<_Ty, _Alloc>::erase [with _Ty=Node, _Alloc=std::allocator<Node>]" matches the argument list Project_4CS210

После удаления я планирую организовать вектор так, чтобы не было открытых пятен, однако я хочу убедиться, что сначала смогу удалить узел. Какие-либо предложения? Я новичок, поэтому для меня большая часть этого нова. 

Here's my delete function. 


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

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;
void BST::Delete()
{
    int input_id;
    cout << "What is the ID of the person to be deleted" << endl;
    cin >> input_id;

    for (unsigned int i = 0; i < binaryTree.size(); i++)
    {
if (input_id == binaryTree.at(i).ID)
        binaryTree.erase(i);



    }
}

Ответы [ 3 ]

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

Вы не должны удалять элементы из вектора во время итерации, вы можете пропустить некоторые индексы во время итерации, используйте std::remove_if, чтобы отправить элементы, необходимые для удаления в конце вектора, а затем стереть их из вектора с помощью метода erase() : 

auto It = std::remove_if(binaryTree.begin(), binaryTree.end(), [input](const Node& node)
         {
             if( node.ID == input )
             {
                 return true;
             }
             return false;

         });
binaryTree.erase(It,binaryTree.end());

Метод erase() принимает итераторы для удаления диапазона или один итератор для удаления одного элемента. std::remove_if вернет итератор для первых элементов, помещенных в конце для удаления.

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

Учитывая, что вы хотите удалить все элементы в векторе или определенный элемент. Вы можете фактически удалить элементы из вектора, используя erase во время итерации. Имейте в виду, что erase фактически предоставляет вам итератор для следующего элемента. Поэтому вам может не понадобиться увеличивать итератор, если он не удовлетворяет условию.

Вот пример кода: 

for (std::vector<Node>::iterator it =  binaryTree.begin(); it != binaryTree.end();)
{
    if(it == yourItem) //Conditional check if it matches with your object.
    {
       it =  binaryTree.erase(it);
    }
    else
    {
       ++it;
    }
}

Вы можете видеть, что я фактически получаю итератор для следующего элемента в списке, не увеличивая его. Вы можете обработать его любым удобным для вас способом.

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

std::vector::erase принимает итератор , а не индекс.

Вы можете использовать binaryTree.begin() + i, чтобы получить итератор для i-го элемента вектора (обратите внимание, что некоторые контейнеры имеют типы итераторов без +, поэтому вам нужно будет использовать std::advance там).

В целом, binaryTree.erase(binaryTree.begin() + i) должен выполнять ту работу, которую вы хотите, но то, что вы пытаетесь сделать, вы также можете посмотреть на std::remove_if.

Чтобы подробно остановиться на этом последнем пункте (потому что кто-то в комментариях упомянул идиому удаления / удаления): 

vector.erase(std::remove_if(vector.begin(), 
                            vector.end(),
                            [](const auto& element) { return condition(element); }),
             vector.end());

Это удалит все элементы из вектора, где condition(element) возвращает true, и, как правило, лучше, чем итерация по вектору вручную:

  • Если вы хотите удалить более одного элемента с помощью вашего метода, вы можете пропустить некоторые. Возьмите вектор, где элементы, которые вы хотите удалить, имеют индексы i и i + 1. Затем вы обычно удаляете элемент с индексом i, а элемент с i + 1 перемещается в индекс i - однако на следующей итерации вы уже проверяете индекс i + 1, поэтому пропускаете элемент, который вы хотели удалить

  • Каждый раз, когда вы удаляете элемент из вектора, все элементы позади него перемещаются в памяти. Если ваши вещи довольно большие, это может быть дорого. Использование remove_if должно гарантировать, что каждый элемент не перемещается больше, чем необходимо, что может быть более эффективным, особенно если вы удалите много элементов.

...