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.

Seth Carnegie
  • 73,875
  • 22
  • 181
  • 249
  • 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.) – Jeremy Jul 30 '11 at 17:40
  • http://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it – nielsj Jul 30 '11 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. – André Caron Jul 30 '11 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. – Seth Carnegie Jul 30 '11 at 17:44

6 Answers6

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.

Node
  • 3,443
  • 16
  • 18
  • 2
    But it requires the list too. – Daniel Jul 30 '11 at 17:39
  • 1
    The `std::remove()` function does *not remove items from the container*, because it just can't. Check out the [erase-remove idiom](http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove). – André Caron Jul 30 '11 at 17:49
  • @André - Thats what I said. Use it to move them to the end _and delete them at a later point_ – Node Jul 30 '11 at 17:51
  • 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. – Seth Carnegie Jul 30 '11 at 18:51
  • 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. – sbi Jul 31 '11 at 00:49
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.

sbi
  • 219,715
  • 46
  • 258
  • 445
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.

Mark B
  • 95,107
  • 10
  • 109
  • 188
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.

Catskul
  • 17,916
  • 15
  • 84
  • 113
  • That's a good thought, though it seems like you could make the iterators tell their parent list they're removing themselves or something. – Seth Carnegie Aug 04 '11 at 22:51
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.

André Caron
  • 44,541
  • 12
  • 67
  • 125
  • 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 Carnegie Jul 30 '11 at 17:42
  • @Seth: yes, this is technically possible. For instance, in Java, iterators have a [remove method](http://download.oracle.com/javase/1.4.2/docs/api/java/util/Iterator.html#remove()). However, this is not part of the C++ iterator design. I guess the standard committee preferred uniformity with other containers. – André Caron Jul 30 '11 at 17:45
  • @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. – André Caron Jul 30 '11 at 17:47
-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;
Daniel
  • 30,896
  • 18
  • 85
  • 139
  • 2
    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. – sbi Jul 30 '11 at 17:44
  • 1
    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. – Seth Carnegie Jul 30 '11 at 17:47
  • 4
    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()`). – André Caron Jul 30 '11 at 17:55