<p>When I am writing code in Python, I often need to remove items from a list or other sequence type based on some criteria. I haven't found a solution that is elegant and efficient, as removing items from a list you are currently iterating through is bad.  For example, you can't do this:</p>

<pre><code>for name in names:
    if name[-5:] == 'Smith':
        names.remove(name)
</code></pre>

<p>I usually end up doing something like this:</p>

<pre><code>toremove = []
for name in names:
    if name[-5:] == 'Smith':
        toremove.append(name)
for name in toremove:
    names.remove(name)
del toremove
</code></pre>

<p>This is innefficient, fairly ugly and possibly buggy (how does it handle multiple 'John Smith' entries?). Does anyone have a more elegant solution, or at least a more efficient one? </p>

<p>How about one that works with dictionaries?</p>

[{'answer_id': 18424, 'author': 'nlucaroni', 'author_id': 157, 'author_profile': 'https://Stackoverflow.com/users/157', 'pm_score': -1, 'selected': False, 'text': "<p>Well, this is clearly an issue with the data structure you are using. Use a hashtable for example. Some implementations support multiple entries per key, so one can either pop the newest element off, or remove all of them.</p>\n\n<p>But this is, and what you're going to find the solution is, elegance through a different data structure, not algorithm. Maybe you can do better if it's sorted, or something, but iteration on a list is your only method here.</p>\n\n<p><em>edit:</em> one does realize he asked for 'efficiency'... all these suggested methods just iterate over the list, which is the same as what he suggested. </p>\n"}, {'answer_id': 18430, 'author': 'pottedmeat', 'author_id': 2120, 'author_profile': 'https://Stackoverflow.com/users/2120', 'pm_score': 2, 'selected': False, 'text': '<pre><code>names = filter(lambda x: x[-5:] != "Smith", names);\n</code></pre>\n'}, {'answer_id': 18431, 'author': 'mk.', 'author_id': 1797, 'author_profile': 'https://Stackoverflow.com/users/1797', 'pm_score': 2, 'selected': False, 'text': "<p>filter would be awesome for this. Simple example:</p>\n\n<pre><code>names = ['mike', 'dave', 'jim']\nfilter(lambda x: x != 'mike', names)\n['dave', 'jim']\n</code></pre>\n\n<p><strong>Edit:</strong> Corey's list comprehension is awesome too.</p>\n"}, {'answer_id': 18433, 'author': 'Corey', 'author_id': 1595, 'author_profile': 'https://Stackoverflow.com/users/1595', 'pm_score': 3, 'selected': False, 'text': '<p>Using <a href="http://docs.python.org/tut/node7.html#SECTION007140000000000000000" rel="noreferrer">a list comprehension</a></p>\n\n<pre><code>list = [x for x in list if x[-5:] != "smith"]\n</code></pre>\n'}, {'answer_id': 18435, 'author': 'John', 'author_id': 2168, 'author_profile': 'https://Stackoverflow.com/users/2168', 'pm_score': 7, 'selected': True, 'text': '<p>Two easy ways to accomplish just the filtering are:</p>\n\n<ol>\n<li><p>Using <code>filter</code>:</p>\n\n<p><code>names = filter(lambda name: name[-5:] != "Smith", names)</code></p></li>\n<li><p>Using list comprehensions:</p>\n\n<p><code>names = [name for name in names if name[-5:] != "Smith"]</code></p></li>\n</ol>\n\n<p>Note that both cases keep the values for which the predicate function evaluates to <code>True</code>, so you have to reverse the logic (i.e. you say "keep the people who do not have the last name Smith" instead of "remove the people who have the last name Smith").</p>\n\n<p><strong>Edit</strong> Funny... two people individually posted both of the answers I suggested as I was posting mine.</p>\n'}, {'answer_id': 18497, 'author': 'PabloG', 'author_id': 394, 'author_profile': 'https://Stackoverflow.com/users/394', 'pm_score': 2, 'selected': False, 'text': "<p>Both solutions, <em>filter</em> and <em>comprehension</em> requires building a new list. I don't know enough of the Python internals to be sure, but I <em>think</em> that a more traditional (but less elegant) approach could be more efficient:</p>\n\n<pre><code>names = ['Jones', 'Vai', 'Smith', 'Perez']\n\nitem = 0\nwhile item &lt;&gt; len(names):\n    name = names [item]\n    if name=='Smith':\n        names.remove(name)\n    else:\n        item += 1\n\nprint names\n</code></pre>\n\n<p>Anyway, for short lists, I stick with either of the two solutions proposed earlier.</p>\n"}, {'answer_id': 163925, 'author': 'Ricardo Reyes', 'author_id': 3399, 'author_profile': 'https://Stackoverflow.com/users/3399', 'pm_score': 1, 'selected': False, 'text': "<p>The filter and list comprehensions are ok for your example, but they have a couple of problems:</p>\n\n<ul>\n<li>They make a copy of your list and return the new one, and that will be inefficient when the original list is really big</li>\n<li>They can be really cumbersome when the criteria to pick items (in your case, if name[-5:] == 'Smith') is more complicated, or has several conditions.</li>\n</ul>\n\n<p>Your original solution is actually more efficient for very big lists, even if we can agree it's uglier. But if you worry that you can have multiple 'John Smith', it can be fixed by deleting based on position and not on value:</p>\n\n<pre><code>names = ['Jones', 'Vai', 'Smith', 'Perez', 'Smith']\n\ntoremove = []\nfor pos, name in enumerate(names):\n    if name[-5:] == 'Smith':\n        toremove.append(pos)\nfor pos in sorted(toremove, reverse=True):\n    del(names[pos])\n\nprint names\n</code></pre>\n\n<p>We can't pick a solution without considering the size of the list, but for big lists I would prefer your 2-pass solution instead of the filter or lists comprehensions </p>\n"}, {'answer_id': 171848, 'author': 'elifiner', 'author_id': 15109, 'author_profile': 'https://Stackoverflow.com/users/15109', 'pm_score': 2, 'selected': False, 'text': "<p>There are times when filtering (either using filter or a list comprehension) doesn't work. This happens when some other object is holding a reference to the list you're modifying and you need to modify the list in place.</p>\n\n<pre><code>for name in names[:]:\n    if name[-5:] == 'Smith':\n        names.remove(name)\n</code></pre>\n\n<p>The only difference from the original code is the use of <code>names[:]</code> instead of <code>names</code> in the for loop. That way the code iterates over a (shallow) copy of the list and the removals work as expected. Since the list copying is shallow, it's fairly quick.</p>\n"}, {'answer_id': 178735, 'author': 'Jason Baker', 'author_id': 2147, 'author_profile': 'https://Stackoverflow.com/users/2147', 'pm_score': 2, 'selected': False, 'text': '<p>To answer your question about working with dictionaries, you should note that Python 3.0 will include <a href="http://www.python.org/dev/peps/pep-0274/" rel="nofollow noreferrer">dict comprehensions</a>:</p>\n\n<pre><code>&gt;&gt;&gt; {i : chr(65+i) for i in range(4)}\n</code></pre>\n\n<p>In the mean time, you can do a quasi-dict comprehension this way:</p>\n\n<pre><code>&gt;&gt;&gt; dict([(i, chr(65+i)) for i in range(4)])\n</code></pre>\n\n<p>Or as a more direct answer:</p>\n\n<pre><code>dict([(key, name) for key, name in some_dictionary.iteritems if name[-5:] != \'Smith\'])\n</code></pre>\n'}, {'answer_id': 181062, 'author': 'Xavier Martinez-Hidalgo', 'author_id': 25996, 'author_profile': 'https://Stackoverflow.com/users/25996', 'pm_score': 5, 'selected': False, 'text': "<p>You can also iterate backwards over the list:</p>\n\n<pre><code>for name in reversed(names):\n    if name[-5:] == 'Smith':\n        names.remove(name)\n</code></pre>\n\n<p>This has the advantage that it does not create a new list (like <code>filter</code> or a list comprehension) and uses an iterator instead of a list copy (like <code>[:]</code>).</p>\n\n<p>Note that although removing elements while iterating backwards is safe, inserting them is somewhat trickier.</p>\n"}, {'answer_id': 1857734, 'author': 'CashMonkey', 'author_id': 226094, 'author_profile': 'https://Stackoverflow.com/users/226094', 'pm_score': 1, 'selected': False, 'text': '<p>In the case of a set.  </p>\n\n<pre><code>toRemove = set([])  \nfor item in mySet:  \n    if item is unwelcome:  \n        toRemove.add(item)  \nmySets = mySet - toRemove \n</code></pre>\n'}, {'answer_id': 4639748, 'author': 'Edward Loper', 'author_id': 222329, 'author_profile': 'https://Stackoverflow.com/users/222329', 'pm_score': 5, 'selected': False, 'text': '<p>The obvious answer is the one that John and a couple other people gave, namely:</p>\n\n<pre><code>&gt;&gt;&gt; names = [name for name in names if name[-5:] != "Smith"]       # &lt;-- slower\n</code></pre>\n\n<p>But that has the disadvantage that it creates a new list object, rather than reusing the original object.  I did some profiling and experimentation, and the most efficient method I came up with is:</p>\n\n<pre><code>&gt;&gt;&gt; names[:] = (name for name in names if name[-5:] != "Smith")    # &lt;-- faster\n</code></pre>\n\n<p>Assigning to "names[:]" basically means "replace the contents of the names list with the following value".  It\'s different from just assigning to names, in that it doesn\'t create a new list object.  The right hand side of the assignment is a generator expression (note the use of parentheses rather than square brackets).  This will cause Python to iterate across the list.</p>\n\n<p>Some quick profiling suggests that this is about 30% faster than the list comprehension approach, and about 40% faster than the filter approach.</p>\n\n<p><strong>Caveat</strong>: while this solution is faster than the obvious solution, it is more obscure, and relies on more advanced Python techniques.  If you do use it, I recommend accompanying it with a comment.  It\'s probably only worth using in cases where you really care about the performance of this particular operation (which is pretty fast no matter what).  (In the case where I used this, I was doing A* beam search, and used this to remove search points from the search beam.)</p>\n'}, {'answer_id': 9979995, 'author': 'valyala', 'author_id': 274937, 'author_profile': 'https://Stackoverflow.com/users/274937', 'pm_score': 2, 'selected': False, 'text': '<p>If the list should be filtered in-place and the list size is quite big, then algorithms mentioned in the previous answers, which are based on list.remove(), may be unsuitable, because their computational complexity is O(n^2). In this case you can use the following no-so pythonic function:</p>\n\n<pre><code>def filter_inplace(func, original_list):\n  """ Filters the original_list in-place.\n\n  Removes elements from the original_list for which func() returns False.\n\n  Algrithm\'s computational complexity is O(N), where N is the size\n  of the original_list.\n  """\n\n  # Compact the list in-place.\n  new_list_size = 0\n  for item in original_list:\n    if func(item):\n      original_list[new_list_size] = item\n      new_list_size += 1\n\n  # Remove trailing items from the list.\n  tail_size = len(original_list) - new_list_size\n  while tail_size:\n    original_list.pop()\n    tail_size -= 1\n\n\na = [1, 2, 3, 4, 5, 6, 7]\n\n# Remove even numbers from a in-place.\nfilter_inplace(lambda x: x &amp; 1, a)\n\n# Prints [1, 3, 5, 7]\nprint a\n</code></pre>\n\n<p>Edit:\nActually, the solution at <a href="https://stackoverflow.com/a/4639748/274937">https://stackoverflow.com/a/4639748/274937</a> is superior to mine solution. It is more pythonic and works faster. So, here is a new filter_inplace() implementation:</p>\n\n<pre><code>def filter_inplace(func, original_list):\n  """ Filters the original_list inplace.\n\n  Removes elements from the original_list for which function returns False.\n\n  Algrithm\'s computational complexity is O(N), where N is the size\n  of the original_list.\n  """\n  original_list[:] = [item for item in original_list if func(item)]\n</code></pre>\n'}, {'answer_id': 15434620, 'author': 'Cory Gross', 'author_id': 1359785, 'author_profile': 'https://Stackoverflow.com/users/1359785', 'pm_score': 1, 'selected': False, 'text': '<p>Here is my <code>filter_inplace</code> implementation that can be used to filter items from a list in-place, I came up with this on my own independently before finding this page. It is the same algorithm as what PabloG posted, just made more generic so you can use it to filter lists in place, it is also able to remove from the list based on the <code>comparisonFunc</code> if reversed is set <code>True</code>; a sort-of of reversed filter if you will.</p>\n\n<pre><code>def filter_inplace(conditionFunc, list, reversed=False):\n    index = 0\n    while index &lt; len(list):\n        item = list[index]\n\n        shouldRemove = not conditionFunc(item)\n        if reversed: shouldRemove = not shouldRemove\n\n        if shouldRemove:\n            list.remove(item)\n        else:\n            index += 1\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/18418', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1892/']