8

Is it possible to remove an element from an std::list if you have only the iterator that points to the element you want to remove? I have a large amount of functions that take iterators to list elements, and it would be a huge inconvenience to have to pass the owning list to every one of them.

Improve this question
4
  • 1
    Note that using an iterator this way is against its use as a design pattern, but that's not to say it's not the right thing to do in many situations (e.g. looking through the elements of a set.) Commented Jul 30, 2011 at 17:40
  • stackoverflow.com/questions/596162/… Commented Jul 30, 2011 at 17:41
  • @Jeremy: actually, it's not agains the use of the iterator as a design pattern. However, it has poor semantics with respect to iterator invalidation. In many containers, removing an item invalidates all iterators, including the one you're currently using to iterate over the elements. Commented Jul 30, 2011 at 17:42
  • @Andre yeah, but I'm always going to use a list which doesn't invalidate other iterators if you remove an item from it. Also @nj, I don't think that's relevant to this question. Commented Jul 30, 2011 at 17:44

6 Answers 6

Reset to default
3

Edit:

You cant with a single iterator.

If you have the begin/end iterators, you could use the std::remove algorithm to move all the elements you want to erase to the end, and delete them at a later point.

If you don't, or the above isn't feasible with your current design, i'd recommend altering your functions to take a std::pair<std::list<T>, std::list<T>::iterator> or something like that.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

But it requires the list too.
The std::remove() function does not remove items from the container, because it just can't. Check out the erase-remove idiom.
@André - Thats what I said. Use it to move them to the end and delete them at a later point
I decided to do something similar, which is just store a reference to the owning list in the item it holds. That solution involved minimal changes to existing code (two lines I think). But if I couldn't do that, I would do what is suggested in this answer (the std::pair one), so I'll mark this as the answer.
While this is right in principle (I upvoted already), note that std::remove() does not necessarily move the objects to be removed to the end. It makes no claims as to what happens to them. For std::vector, I'm sure all implementations will just overwrite them. For std::list I'm not sure.
3

No, you can't. Iterators are light-weight objects modeled after pointers and do not carry a reference to the container they refer to. (Although some implementations do so internally in Debug mode.)

Just as you cannot "remove" an object from an array when all you have is a pointer into the array, you cannot remove an object from a container without also having access to the container.

Improve this answer

Comments

3

You can't do that with the standard library, but you can use Boost's intrusive list http://www.boost.org/doc/libs/1_37_0/doc/html/boost/intrusive/list.html which has such an interface.

Improve this answer

Comments

1

While others have mentioned that you can't do it, I think I can offer as to why.

I believe the specific technical reason (rather than design reason) is that lists do some upkeep, like keeping track of size for example, which require that certain actions have to be passed through them to allow that upkeep.

It's for this reason that any hack that might be offered would likely fail.

Improve this answer

1 Comment

That's a good thought, though it seems like you could make the iterators tell their parent list they're removing themselves or something.
0

No, this is not possible. As its name suggests, an iterator's job is to iterate over the elements of a sequence. Check out the SGI page on iterators for a summary of iterator design in the C++ standard library.

Improve this answer

3 Comments

Because list is a doubly-linked list, could you not write a function to manipulate the next and previous pointers so that it removes the element? Or would that be really bad? Or is it just that the members are private?
@Seth: yes, this is technically possible. For instance, in Java, iterators have a remove method. However, this is not part of the C++ iterator design. I guess the standard committee preferred uniformity with other containers.
@Seth: this might be done for a specific version of a specific vendor's library. However, it means lots of non-standard (and definitely non-portable) code. Moreover, the members are probably private.
-1

You can do this manually. iterator exposes _M_node as the current node. you can do something like:

itr._M_node->_M_prev->_M_next = itr._M_node._M_next;
Improve this answer

3 Comments

This is only the case for a specific iterator into a specific container in a specific versions of a specific implementation, it's an implementation detail, and can even be turned off by using the right preprocessor token. Also, it might mess up the container's internals, which you would need to know in order to do that.
Not to mention you didn't update the _M_prev pointer of _M_next (because it's a dlinked list). That's something I was thinking of, but this code needs to work with different versions/compilers as well.
Note that even if this were possible, this would cause a memory leak. You would also need to access the container's allocator to release the memory and you would need to reduce the list's item count if it is cached (the standard allows implementations to choose between O(1) size() and O(1) splice()).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.