Removing element in a list

[kramsuiluj]

I'm trying to create a system(school project) that can add items in a list, view all of those items, then remove any one of them.

For example:
Enter a name: Mark
Enter a name: Mary
Enter a name: Max

Now, I viewed them:
List of Names:
Mark
Mary
Max

So my question is, is it possible to remove an element in the list by accessing them by name?

I want it to look like this:
Remove a name: Mary

List of Names:
Mark
Max

[Repeater]

Yes, it is.

You could make a new list without the name you want removed, or you could remove that name from the existing list.

[kramsuiluj]

Uhm i forgot to ask how? Can you give me an example? Thanks!

[George P]

std::list::remove

https://en.cppreference.com/w/cpp/container/list/remove

#include <iostream>
#include <list>
#include <string>

int main()
{
   std::list<std::string> lst { "Mark", "Mary", "Max" };

   std::cout << "The list contains:\n";
   for (const auto& itr : lst) { std::cout << itr << ' '; }
   std::cout << "\n\n";

   std::cout << "Removing 'Mary'....\n\n";

   lst.remove("Mary");

   std::cout << "The list now contains:\n";
   for (const auto& itr : lst) { std::cout << itr << ' '; }
   std::cout << '\n';
}

The list contains:
Mark Mary Max

Removing 'Mary'....

The list now contains:
Mark Max

[againtry]

The solution depends on what you want 'remove' to mean and what the structure of the list is.

You can simply have an attribute in the list that removes access to it. eg The item stays in the list and is marked so that it doesn't print out.

Another way is if the list is stored as a basic array is to flag the element, shift the tail end element into that position and then reduce the array size variable by one.

If you use the C++ STL containers - <list>, <vectors>, <maps>, <arrays> etc removing and element does all that work for you.

[dhayden]

In C++, the word "list" means a specific type of data structure. Do you mean a C++ list, or do you just mean "a collection of names".

You show the names displayed in the same order that they were entered. Is that required or can they be in a different order?

They are also displayed in alphabetical order. Do they need to be displayed in alphabetical order?

Can you use the standard C++ collection classes or are you supposed to write your own?

I know that these questions sound picky but they are necessary to get at the real requirements of the assignment. The best thing would be for you to post the actual assignment so we can read it.

[kramsuiluj]

@dhayden Uhm, we are required to use a data structure in our program, and i want to use list so i can access any part of it, unlike stack or queues, I also heard that i can also do the same with vectors and deque but we were only given like 4 options which is list, stack, queue (forgot the other one but im sure vector and deque is not included).

I'm trying to create a program where i can store data in a list, be able to view them and be able to remove them but i don't know how to remove an element in the list by using the value of the element.

[againtry]

http://www.cplusplus.com/reference/list/list/remove/

[kramsuiluj]

What if there's no initial value ? can you show me an example of the remove_if function ?

[againtry]

See http://www.cplusplus.com/reference/list/list/remove_if/

Keep in mind this is a conditional if so you can, for aguments sake, remove all values from the <list> greater than 7 and less than 2.

The standard remove function doesn't know which value you want to remove, you have to specify it. If you don't know what the value is you are looking for then you would need to print out the list using other <list> functinality to run through the and cout the list via a loop or whatever.

Feel free to use http://www.cplusplus.com/reference/list/list/ the general reference for <list> containers.

[lastchance]

@kramsuiluj,
You run a real risk of creating an XY problem if you don't tell us what your actual assignment/project is. I find it hard to believe that its most important action is to "remove items". Also, I can't see what would have prompted your question "What if there's no initial value?"

Could you answer @dhayden's questions further up the thread, and say exactly what your assignment is. The usage of "list" in colloquial English is not the same as its very specific use as a computer data structure.

[againtry]

we were only given like 4 options which is list, stack, queue
and ... remove_if function

As a wild guess I think kramsuiluj might be on about <list>'s

[lastchance]

Or a tree, maybe?

Bashful  Doc  Dopey  Grumpy  Happy  Sleepy  Sneezy  

           ___ Happy _________________ 
          |                           |
  _______ Doc _                ______ Sneezy 
 |             |              |
 Bashful       Dopey _        Sleepy 
                      |
                      Grumpy 



Removed Grumpy

Bashful  Doc  Dopey  Happy  Sleepy  Sneezy  

           ___ Happy _________ 
          |                   |
  _______ Doc _        ______ Sneezy 
 |             |      |
 Bashful       Dopey  Sleepy 

#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T> class BST
{
   class Node
   {
   public:
      T data;
      Node* left  = nullptr;
      Node* right = nullptr;
      Node( T x ) : data( x ) {}
   };

   Node *root = nullptr;

   void  insert   ( Node* &current, T x );
   bool  find     ( Node*  current, T x );
   int   count    ( Node*  current, T x );
   int   remove   ( Node*  current, Node * &parentPointer, T x );
   int   getHeight( Node*  current );
   void  clear    ( Node*  current );
   void  write    ( Node*  current, ostream &strm );

public:
   void insert  ( T x ) { insert( root, x ); }
   int remove   ( T x ) { Node * temp = nullptr;   return remove( root, temp, x ); }
   bool find    ( T x ) { return find( root, x ); }
   int count    ( T x ) { return count( root, x ); }
   int getHeight(     ) { return getHeight( root ); }
   void clear   (     ) { clear( root ); }
   void write( ostream &strm = cout ) { write( root, strm ); strm << '\n'; }

   // Drawing
   private:
      void drawNode( vector<string> &output, vector<string> &linkAbove, Node* node, int level, int minPos, char linkChar );

   public:
      void draw();
};

//-----

template<typename T> void BST<T>::insert( Node * &current, T x )
{
   if ( !current )               current = new Node( x );
   else if ( x < current->data ) insert( current->left , x );
   else                          insert( current->right, x );
}

//-----

template <typename T> bool BST<T>::find( Node* current, T x )
{
   if ( !current )                return false;
   else if ( current->data == x ) return true;
   else                           return find( current->left, x ) || find( current->right, x );
}

//-----

template <typename T> int BST<T>::count( Node* current, T x )
{
   if ( !current ) return 0;
   return ( current->data == x ) + count( current->left, x ) + count( current->right, x );
}

//-----

template <typename T> int BST<T>::remove( Node * current, Node * &parentPointer, T x )
{
   int count = 0;
   if ( !current ) return count;

   if ( current->left  ) count += remove( current->left , current->left , x );
   if ( current->right ) count += remove( current->right, current->right, x );

   if ( current->data == x )
   {
      count++;
      bool isRoot = ( current == root );
      Node * child;
      if ( !current->left && !current->right )
      {
         child = nullptr;
      }
      else if ( current->left && !current->right )
      {
         child = current->left;
      }
      else if ( !current->left && current->right )
      {
         child = current->right;
      }
      else
      {
         Node *n = current->right;
         Node *nparent = current;
         while ( n->left )
         {
            nparent = n;
            n = n->left;
         }
         if ( n !=  current->right )
         {
            nparent->left = nullptr;
            n->right = current->right;
         }
         n->left  = current->left;
         child = n;
      }
      delete current;
      if ( isRoot ) root = child;
      else          parentPointer = child;
   }
   return count;
}

//-----

template <typename T> int BST<T>::getHeight( Node* current )
{
   if ( !current ) return 0;
   else            return 1 + max( getHeight( current->left ), getHeight( current->right ) );
}

//-----

template <typename T> void BST<T>::clear( Node* current )
{
   if ( current->left  ) clear( current->left  );
   if ( current->right ) clear( current->right );
   if ( current )
   { 
      cout << "Deleting " << current->data << '\n';
      if ( root == current ) root = nullptr;
      delete current;
   }
}

//-----

template <typename T> void BST<T>::write( Node * current, ostream &strm )
{
   if ( current )
   {
      write(  current->left , strm );
      strm << current->data << "  ";
      write(  current->right, strm );
   }
}

//-----

template <typename T> void BST<T>::drawNode( vector<string> &output, vector<string> &linkAbove, Node* node, int level, int p, char linkChar )
{
   if ( !node ) return;

   int h = output.size();
   string SP = " ";
   
   if ( p < 0 )       // Shunt everything non-blank across
   {
      string extra( -p, ' ' );
      for ( string &s : output    ) if ( !s.empty() ) s = extra + s;
      for ( string &s : linkAbove ) if ( !s.empty() ) s = extra + s;
   }
   if ( level < h - 1 ) p = max( p, (int)output[level+1].size() );
   if ( level > 0     ) p = max( p, (int)output[level-1].size() );
   p = max( p, (int)output[level].size() );
   
   // Fill in to left
   if ( node->left ) 
   {
//    string leftData = SP + to_string( node->left->data ) + SP;
      string leftData = SP + node->left->data + SP;
      drawNode( output, linkAbove, node->left, level + 1, p - leftData.size(), 'L' );
      p = max( p, (int)output[level+1].size() );
   }

   // Enter this data
   int space = p - output[level].size();  if ( space > 0 ) output[level] += string( space, ' ' );
// string nodeData = SP + to_string( node->data ) + SP;
   string nodeData = SP + node->data + SP;
   output[level] += nodeData;

   // Add vertical link above
   space = p + SP.size() - linkAbove[level].size();   if ( space > 0 ) linkAbove[level] += string( space, ' ' );
   linkAbove[level] += linkChar;

   // Fill in to right
   if ( node->right ) drawNode( output, linkAbove, node->right, level + 1, output[level].size(), 'R' );
}

//-----

template <typename T> void BST<T>::draw()
{
   int h = getHeight( root );
   vector<string> output( h ), linkAbove( h );
   drawNode( output, linkAbove, root, 0, 5, ' ' );

   // Create link lines
   for ( int i = 1; i < h; i++ )
   {
      for ( int j = 0; j < linkAbove[i].size(); j++ )
      {
         if ( linkAbove[i][j] != ' ' )
         {
            int size = output[i-1].size();
            if ( size < j + 1 ) output[i-1] += string( j + 1 - size, ' ' );
            int jj = j;
            if ( linkAbove[i][j] == 'L' )
            {
               while ( output[i-1][jj] == ' ' ) jj++;
               for ( int k = j + 1; k < jj - 1; k++ ) output[i-1][k] = '_';
            }
            else if ( linkAbove[i][j] == 'R' )
            {
               while ( output[i-1][jj] == ' ' ) jj--;
               for ( int k = j - 1; k > jj + 1; k-- ) output[i-1][k] = '_';
            }
            linkAbove[i][j] = '|';
         }
      }
   }

   // Output
   for ( int i = 0; i < h; i++ )
   {  
      if ( i ) cout << linkAbove[i] << '\n';
      cout << output[i] << '\n';
   }
}

//=======

int main()
{
   BST<string> tree;
   for ( string s : { "Happy", "Doc", "Dopey", "Bashful", "Grumpy", "Sneezy", "Sleepy" } ) tree.insert( s );
   tree.write();   cout << '\n';
   tree.draw();    cout << '\n';

   string s = "Grumpy";
   tree.remove( s );
   cout << "\n\nRemoved " << s << "\n\n";
   tree.write();   cout << '\n';
   tree.draw();    cout << '\n';
}