[QLinkedList] find and delete item

[amreo]

I'm the developer of open source project https://github.com/amreo/gridb
I want to implement the deSelect function in src/listcoordselecter.cpp

How to fast way to find and remove item?

I want to find the iterator and remove the related element like

void ListCoordSelecter::deSelect(const Located& loc)
{
	QLinkedList<Located>::iterator iter = this->list.begin();
 
	while (iter.i->n != NULL) 
	{
		if (iter.reference.x() == loc.x() && iter.reference.y == loc.y()) 
		{
			//remove the element pointed by iterator
			break; //end of loop
		}
	}
}

void ListCoordSelecter::deSelect(const Located& loc)
{
	QLinkedList<Located>::iterator iter = this->list.begin();
	
	while (iter.i->n != NULL) 
	{
		if (iter.reference.x() == loc.x() && iter.reference.y == loc.y()) 
		{
			//remove the element pointed by iterator
			break; //end of loop
		}
	}
}

To copy to clipboard, switch view to plain text mode 

[ars]

Hello,

I'm not clear what is really your question, so here is some guessing.

1. You use a linked list. For removing a value from the list you first have to find that value. This is O(n) operation for a simple linked list. If that is too slow for your application you should consider using different data structure.

2. If you have an iterator pointing to the element to be deleted, use

iterator QLinkedList::erase(iterator pos)

iterator QLinkedList::erase(iterator pos)

To copy to clipboard, switch view to plain text mode 

to remove the element from the list. It returns an iterator pointing to the element that followed the deleted element.

3. Your usage of iterators looks a little bit strange to me. I would rewrite it as

void ListCoordSelecter::deSelect(const Located& loc)
{
	QLinkedList<Located>::iterator iter = list.begin(); // no need for this->
 
	while (iter != list.end()) // Usage of NULL to mark the end is implementation detail
	{
		if (iter->x() == loc.x() && iter->y() == loc.y())  // iter.reference not mentioned in Qt 5.x documentation!
		{
			//remove the element pointed by iterator
                        list.erase(iter);
			break; //end of loop
		}
                // don't forget to move the iterator
                ++iter;
	}
}

void ListCoordSelecter::deSelect(const Located& loc)
{
	QLinkedList<Located>::iterator iter = list.begin(); // no need for this->
	
	while (iter != list.end()) // Usage of NULL to mark the end is implementation detail
	{
		if (iter->x() == loc.x() && iter->y() == loc.y())  // iter.reference not mentioned in Qt 5.x documentation!
		{
			//remove the element pointed by iterator
                        list.erase(iter);
			break; //end of loop
		}
                // don't forget to move the iterator
                ++iter;
	}
}

To copy to clipboard, switch view to plain text mode 

Alternatively using C++11 you could also rewrite it to

for(auto iter = list.begin(); iter != list.end(); ++iter)
{
      if (iter->x() == loc.x() && iter->y() == loc.y())  // iter.reference not mentioned in Qt 5.x documentation!
      {
          //remove the element pointed by iterator
          list.erase(iter);
	  break; //end of loop
      }
}

for(auto iter = list.begin(); iter != list.end(); ++iter)
{
      if (iter->x() == loc.x() && iter->y() == loc.y())  // iter.reference not mentioned in Qt 5.x documentation!
      {
          //remove the element pointed by iterator
          list.erase(iter);
	  break; //end of loop
      }
}

To copy to clipboard, switch view to plain text mode 

Best regards
ars

[amreo]

Thanks. I solved the problem