CODEWITHSUNDEEP
c++vectornodeserase
Nom OnTheCookie
Nom OnTheCookie

Reputation: 87

C++ How to delete nodes in a vector

So I have created a binary search tree that is stored within an array. This binary search tree (BST) stores a user input ID, Age, and Name, then places it within the array sorted in ascending order by the ID.

I'm attempting to write a delete function that takes a user input ID, loops through the vector, and if it finds a matching ID, it deletes it.

However, I can't seem to get BinaryTree.erase() to work due to an error.

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]" matches the argument list Project_4CS210

After erasing, I plan on organizing the vector so that there aren't any open spots, however, I want to make sure that I can delete the node first. Any suggestions? I am a beginner, so most of this is rather new to me.

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);



    }
}

Upvotes: 2

Views: 2368

Answers (3)

MarKS
MarKS

Reputation: 504

Considering you wish to remove all the items in the vector or a specific item. You can actually erase items from a vector using erase while iterating. Keep in mind the erase actually provides you with the iterator to the next item. So you may not need to increment the iterator unless it fulfills the condition.

Here is a sample code:

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;
    }
}

You can see that i am actually getting the iterator to the next item in the list without incrementing it. You can process it in whatever way you may like.

Upvotes: 0

hlt
hlt

Reputation: 6317

std::vector::erase takes an iterator, not an index.

You can use binaryTree.begin() + i to get the iterator for the i-th element of a vector (note that some containers have iterator types without +, so you'd need to use std::advance there).

Overall, binaryTree.erase(binaryTree.begin() + i) should do the job you want, but for what you are trying to do you could also look into std::remove_if.

To expand on this last point (because someone in the comments mentioned the remove/erase idiom):

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

This will remove all elements from the vector where condition(element) returns true, and is generally better than iterating over the vector by hand:

  • If you want to remove more than one element with your method, you might miss some. Take a vector where the elements you want to remove are at indices i and i + 1. Then, you remove the element at index i normally, and the element at i + 1 moves to index i - however, in the next iteration you already check index i + 1, so you miss the item that you wanted to remove

  • Each time you remove an element from the vector, all the elements behind that are moved around in memory. If your items are fairly big, that can be expensive. Using remove_if should ensure that each element isn't moved more than necessary, which can be more efficient especially if you remove many elements.

Upvotes: 4

Alexey Usachov
Alexey Usachov

Reputation: 1374

You shouldn't remove elements from vector while iterating over it, you can miss some indexes while iterating, use std::remove_if to send elements needed to remove at the end of vector and then erase them from vector with erase() method:

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());

Method erase() accepts iterators to remove range or one iterator to remove one element. std::remove_if will return iterator for the first elements pushed at the end to remove.

Upvotes: 3

Related Questions