C++

Forum

 
STL list, need help using remove

Jeffrey Clark (2)
I am creating a "Graph" ADT using a multi-list for one of my c++ classes. I am not very familiar with the STL list object, and am having trouble deleting a Vertice from the list.

A Vertice is it's own class--it's data members are a list of edges connected to it, a bool, and data(m_data), of which type is passed in via the "V" in the template.

This is the code for my Graph class function "DeleteVertice". My Graph class contains the data member "m_graph", which is the list of Vertices.

Conceptually what I am trying to do is create an iterator for the list, and in a while loop, test to see if it is the appropriate node in the list, and if so delete it. However, it is not liking the line of code with the remove_if data member. It is giving me an error of "error C2064: term does not evaluate to a function taking 1 arguments". I am not sure what I am doing wrong.

1
2
3
4
5
6
7
8
9
10
 
template<typename V, typename E>
void Graph<V, E>::DeleteVertice( V data )
{
	list<Vertices<V, E> >::iterator vIter = m_graph.begin();

	while( vIter != m_graph.end() )
	{
		m_graph.remove_if( (*vIter).GetData() == data );
		++vIter;
	}
moorecm (1932)
Last edited on
keskiverto (10402)
Look at the example in http://www.cplusplus.com/reference/list/list/remove_if/
No iterators or loop is needed in list::remove_if.

list::erase does use iterator, but the iterator becomes invalid in the operation:
http://www.cplusplus.com/reference/list/list/erase/
Jeffrey Clark (2)
Ok, I will check those out. Thank you!

Edit:
I guess I am being short-sighted. I cannot think how this is done with a complex data type.

I can see that with an int data type, simply having the integer or a variable containing the integer would suffice. My thought is that something like this would work:

1
2
3
4
 
void Function( int data )
{
       m_datamember.remove_if( data );
}


But if the object in the list is a complex data type, how would I get "remove_if" to see if a data member of complex data type matches the data being passed in?

Do I need to change what is being passed in?
Last edited on
keskiverto (10402)
No, that would not work. The parameter for remove_if is a predicate. int is not a predicate.

Approximately:
1
2
3
4
5
6
7
8
9
10
 
template <class Predicate>
void list::remove_if( Predicate pred )
{
  auto it = this->begin();
  while ( it != this->end() )
    {
      if ( pred( *it ) ) it = this->erase( it );
      else ++it;
     }
}

Predicate is something that can be called like a function, takes one parameter, and that returns a bool. One has to write a predicate, but then it does not matter how complex data type you have as list::value_type.


Now, you had (*vIter).GetData() == data. In a predicate:
1
2
3
4
 
bool equalsData( const Vertices<V, E> & value )
{
  return data == value.getData():
}

But that naturally fails in lack of data. Lets try functor (function object):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
class equalsData
{
  const V & data_;
public:
  equalsData( const V & value ) : data_( value ) {}

  bool operator() ( const Vertices<V, E> & value ) const
  {
    return data_ == value.getData():
  }
};

void Graph<V, E>::DeleteVertice( V data )
{
  m_graph.remove_if( equalsData( data ) );
}

Now we create a nameless temporary class equalsData object, initialize its data_ member, and then pass a copy to the list::remove_if. remove_if calls the operator() of equalData with each item in the list. If an item matches the data, it will be removed.

You have to fill in the template stuff syntax yourself.

If your compiler supports enough C++11, then you can replace the separate predicate with a lambda expression. I probably should have used it in the example, but haven't been sufficiently fortunate yet.
Topic archived. No new replies allowed.