# Sequences and Sets in Python

Slicing a sequence

To indicate a subsequence of S , you can use a slicing, with the syntax S[i:j], where i  and j  are integers. S[i:j] is the subsequence of S  from the i th item, included, to the j th item, excluded. In Python, ranges always include the lower bound and exclude the upper bound. A slice is an empty subsequence if j  is less than or equal to i , or if i  is greater than or equal to L , the length of S . You can omit i  if it is equal to 0, so that the slice begins from the start of S. You can omit j  if it is greater than or equal to L, so that the slice extends all the way to the end of S. You can even omit both indices, to mean a copy of the entire sequence: S[:]. Either or both indices may be less than 0. A negative index indicates the same spot inS as L+n , just like in indexing. An index greater than or equal to L  means the end of S, while a negative index less than or equal toL  means the start of S . Here are some examples:

x = [1, 2, 3, 4]
x[1:3]                 # [2, 3]
x[1:]                  # [2, 3, 4]
x[:2]                  # [1, 2]

Slicing can also use the extended syntax S[i:j:k]. k is the stride of the slice, or the distance between successive indices. S[i:j] is equivalent to S[i:j:1], S[::2] is the subsequence of S  that includes all items that have an even index in S , and S[::-1] has the same items as S , but in reverse order.

Strings

String objects are immutable, so attempting to rebind or delete an item or slice of a string raises an exception. The items of a string object (corresponding to each of the characters in the string) are themselves strings, each of length 1. The slices of a string object are also strings. String objects have several methods, which are covered in "Methods of String Objects" on page 186.

Tuples

Tuple objects are immutable, so attempting to rebind or delete an item or slice of a tuple raises an exception. The items of a tuple are arbitrary objects and may be of different types. The slices of a tuple are also tuples. Tuples have no normal (nonspecial) methods, only some of the special methods covered in "Special Methods" on page 104.

Lists

List objects are mutable, so you may rebind or delete items and slices of a list. The items of a list are arbitrary objects and may be of different types. The slices of a list are lists.

Modifying a list

You can modify a list by assigning to an indexing. For instance:

x = [1, 2, 3, 4]
x[1] = 42              # x is now [1, 42, 3, 4]

Another way to modify a list object L  is to use a slice of L  as the target (LHS) of an assignment statement. The RHS of the assignment must then be an iterable. If the LHS slice is in extended form, then the RHS must have just as many items as the number of items in the LHS slice. However, if the LHS slice is in normal
(nonextended) form, then the LHS slice and the RHS may each be of any length; assigning to a (nonextended) slice of a list can add or remove list items. For example:

x = [1, 2, 3, 4]
x[1:3] = [22, 33, 44]    # x is now [1, 22, 33, 44, 4]
x[1:4] = [8, 9]          # x is now [1, 8, 9, 4]

Here are some important special cases of assignment to slices:

• Using the empty list [] as the RHS expression removes the target slice from L . In other words, L[i:j]=[] has the same effect as del L[i:j].
• Using an empty slice of L  as the LHS target inserts the items of the RHS at the appropriate spot in L. In other words, L[i:i]=[‘a’,’b’] inserts the items ‘a’ and ‘b’ before the item that was at index i  in L  before the assignment.
• Using a slice that covers the entire list object,
L[:], as the LHS target totally replaces the contents of L .

You can delete an item or a slice from a list with del. For instance:

x = [1, 2, 3, 4, 5]
del x[1]                 # x is now [1, 3, 4, 5]
del x[::2]               # x is now [3, 5]

In-place operations on a list

List objects define in-place versions of the + and * operators, which you can use via augmented assignment statements. The augmented assignment statement L+=L1  has the effect of adding the items of iterable L1  to the end of L . L*=n  has the effect of adding n-1 copies of L  to the end of L ; if n<=0, L*=n empties the contents of L, like L[:]=[].

{mospagebreak title=List methods}

List objects provide several methods, as shown in Table 4-3. Nonmutating methods return a result without altering the object to which they apply, while mutating methods may alter the object to which they apply. Many of the mutating methods behave like assignments to appropriate slices of the list. In Table 4-3, L  indicates any list object, i any valid index in L , s  any iterable, and x  any object.

Table 4-3. List object methods

 Method Description Nonmutating methods L.count(x) Returns the number of items of Lthat are equal to x. L.index(x) Returns the index of the first occurrence of an item in Lthat is equal to x, or raises an exception if Lhas no such item. Mutating methods L.append(x) Appends item xto the end of L; e.g., L[len(L):]=[x]. L.extend(s) Appends all the items of iterable sto the end of L; e.g., L[len(L):]=s. L.insert(i, x) Inserts item xin Lbefore the item at index i, moving following items of L(if any) "rightward" to make space (increases len(L) by one, does not replace any item, does not raise exceptions: acts just like L[i:i]=[x]). L.remove(x) Removes from L the first occurrence of an item in L that is equal to x, or raises an exception if Lhas no such item. L.pop([i]) Returns the value of the item at index iand removes it from L; if iis omitted, removes and returns the last item; raises an exception if Lis empty or iis an invalid index in L. L.reverse() Reverses, in place, the items of L. L.sort([f])(2.3) Sorts, in place, the items of L, comparing items pairwise via function f; if fis omitted, comparison is via the built-in function cmp. For more details, see "Sorting a list" on page 57. L.sort(cmp=cmp, key=None, reverse=False)(2.4) Sorts, in-place, the items of L, comparing items pairwise via the function passed as cmp (by default, the built-in function cmp). When argument key is not None, what gets compared for each item x is key(x), not x itself. For more details, see "Sorting a list" on page 57.

All mutating methods of list objects, except pop , return None .

Sorting a list

A list’s method sort causes the list to be sorted in-place (its items are reordered to place them in increasing order) in a way that is guaranteed to be stable (elements that compare equal are not exchanged). In practice, sort is extremely fast, often preternaturally fast, as it can exploit any order or reverse order that may be present in any sublist (the advanced algorithm sort uses, known as timsort to honor its developer, Tim Peters, is technically a "non-recursive adaptive stable natural mergesort/binary insertion sort hybrid").

In Python 2.3, a lists sort method takes one optional argument. If present, the argument must be a function that, when called with any two list items as
arguments, returns -1, 0, or 1, depending on whether the first item is to be considered less than, equal to, or greater than the second item for sorting purposes. Passing the argument slows down the sort, although it makes it easy to sort small lists in flexible ways. The decorate-sort-undecorate idiom, covered in "Searching and sorting" on page 485 is faster, at least as flexible, and often less error-prone than passing an argument to sort.

In Python 2.4, the sort method takes three optional arguments, which may be passed with either positional or named-argument syntax. Argument cmp  plays just the same role as the only (unnamed) optional argument in Python 2.3. Argument key , if not None, must be a function that can be called with any list item as its only argument. In this case, to compare any two items x  and y , Python uses cmp(key(x),key(y)) rather than cmp(x,y) (in practice, this is implemented in the same way as the decorate-sort-undecorate idiom presented in "Searching and sorting" on page 485, and can be even faster). Argument reverse , if True, causes the result of each comparison to be reversed; this is not the same thing as reversing L  after sorting because the sort is stable (elements that compare equal are never exchanged) whether argument reverse  is true or false.

Python 2.4 also provides a new built-in function sorted (covered in sorted on page 167) to produce a sorted list from any input iterable. sorted accepts the same input arguments as a lists method sort. Moreover, Python 2.4 adds to module operator (covered in "The operator Module" on page 368) two new higher-order functions, attrgetter and itemgetter, which produce functions particularly suitable for the key= optional argument of lists’ method sort and the new built-in function sorted. In Python 2.5, an identical key=  optional argument has also been added to built-in functions min and max, and to functions nsmallest and nlargest in standard library module heapq, covered in "The heapq Module" on page 177.

{mospagebreak title=Set Operations}

Python provides a variety of operations applicable to sets. Since sets are containers, the built-in len function can take a set as its single argument and return the number of items in the set object. A set is iterable, so you can pass it to any function or method that takes an iterable argument. In this case, the items of the set are iterated upon, in some arbitrary order. For example, for any set S , min(S) returns the smallest item in S .

Set Membership

The k  in S  operator checks whether object k is one of the items of set S . It returns True if it is and False if it isn’t. Similarly, not in S  is just like not (k in S).

Set Methods

Set objects provide several methods, as shown in Table 4-4. Nonmutating methods return a result without altering the object to which they apply and can also be called on instances of type frozenset, while mutating methods may alter the object to which they apply and can be called only on instances of type set. In Table 4-4, S  and S1  indicate any set object, and x any hashable object.

Table 4-4. Set object methods

 Method Description Nonmutating methods S.copy( ) Returns a shallow copy of the set (a copy whose items are the same objects as S’s, not copies thereof) S.difference(S1) Returns the set of all items of Sthat aren’t in S1

Table 4-4. Set object methods (continued)

 Method Description S.intersection(S1) Returns the set of all items of Sthat are also in S1 S.issubset(S1) Returns Trueif all items of S are also in S1; otherwise, returns False S.issuperset(S1) Returns Trueif all items of S1 are also in S; otherwise, returns False (like S1.issubset(S)) S.symmetric_difference(S1) Returns the set of all items that are in either Sor S1, but not in both sets S.union(S1) Returns the set of all items that are in S, S1, or in both sets Mutating methods S.add(x) Adds xas an item to S; no effect if xwas already an item in S S.clear( ) Removes all items from S, leaving Sempty S.discard(x) Removes xas an item of S; no effect if xwas not an item of S S.pop( ) Removes and returns an arbitrary item of S S.remove(x) Removes x as an item of S; raises a KeyErrorexception if x is not an item of S

All mutating methods of set objects, except pop, return None.

The pop method can be used for destructive iteration on a set, consuming little extra memory. The memory savings make pop usable for a loop on a huge set, when what you want is to "consume" the set in the course of the loop.

Sets also have mutating methods named difference_update, intersection_update, symmetric_difference_update, and update (corresponding to nonmutating method union). Each such mutating method performs the same operation as the corresponding nonmutating method, but it performs the operation in place, altering the set on which you call it, and returns None. These four nonmutating methods are also accessible with operator syntax: respectively, SS1, S&S1, S^S1, and S|S1; the corresponding mutating methods are also accessible with augmented assignment syntax: respectively,
S-=S1, S&=S1, S^=S1, and S|=S1. When you use operator or augmented assignment syntax, both operands must be sets or frozensets; however, when you call the named methods, argument S1  can be any iterable with hashable items, and the semantics are just the same as if the argument you passed was
set(S1).

Dictionary Operations

Python provides a variety of operations applicable to dictionaries. Since dictionaries are containers, the built-in len function can take a dictionary as its single argument and return the number of items (key/value pairs) in the dictionary object. A dictionary is iterable, so you can pass it to any function or method that takes an iterable argument. In this case, only the keys of the dictionary are iterated upon, in some arbitrary order. For example, for any dictionary D , min(D) returns the smallest key in D .

Dictionary Membership

The k  in D  operator checks whether object k  is one of the keys of the dictionary D . It returns True if it is and False if it isn’t. k not in D  is just like
not (k in D ).

{mospagebreak title=Indexing a Dictionary}

The value in a dictionary D that is currently associated with key k  is denoted by an indexing: D[k]. Indexing with a key that is not present in the dictionary raises an exception. For example:

d = { ‘x’:42, ‘y’:3.14, ‘z’:7 }
d[‘x’]                           # 42
d[‘z’]                           # 7
d[‘a’]                           # raises KeyError exception

Plain assignment to a dictionary indexed with a key that is not yet in the dictionary (e.g., D[newkey]=value ) is a valid operation and adds the key and value as a new item in the dictionary. For instance:

d = { ‘x’:42, ‘y’:3.14}
d[‘a’] = 16                      # d is now {‘x’:42, ‘y’:3.14,’a’:16}

The del statement, in the form del D[k], removes from the dictionary the item whose key is k . If k  is not a key in dictionary D , del D[k] raises an exception.

Dictionary Methods

Dictionary objects provide several methods, as shown in Table 4-5. Nonmutating methods return a result without altering the object to which they apply, while mutating methods may alter the object to which they apply. In Table 4-5, D  and D1  indicate any dictionary object, k  any hashable object, and x  any object.

Table 4-5. Dictionary object methods

 Method Description Nonmutating methods D.copy( ) Returns a shallow copy of the dictionary (a copy whose items are the same objects as D’s, not copies thereof) D.has_key(k) Returns Trueif kis a key in D; otherwise, returns False, just like k in D D.items( ) Returns a new list with all items (key/value pairs) in D D.keys( ) Returns a new list with all keys in D D.values() Returns a new list with all values in D D.iteritems( ) Returns an iterator on all items (key/value pairs) in D D.iterkeys() Returns an iterator on all keys in D D.itervalues( ) Returns an iterator on all values in D D.get(k[, x]) Returns D[k]if k is a key in D; otherwise, returns x (or None,if x is not given) Mutating methods D.clear( ) Removes all items from D, leaving Dempty D.update(D1) For each kin D1, sets D[k]equal to D1[k] D.setdefault(k[, x]) Returns D[k]if kis a key in D; otherwise, sets D[k]equal to xand returns x

Table 4-5. Dictionary object methods (continued)

 Method Description D.pop(k[, x]) Removes and returns D[k]if kis a key in D; otherwise, returns x(or raises an exception if xis not given) D.popitem() Removes and returns an arbitrary item (key/value pair)

The items, keys, and values methods return their resulting lists in arbitrary order. If you call more than one of these methods without any intervening change to the dictionary, however, the order of the results is the same for all. The iteritems, iterkeys, and itervalues methods return iterators equivalent to these lists (iterators are discussed in "Iterators" on page 65). An iterator consumes less memory than a list, but you must never modify the set of keys in a dictionary (i.e., you must never add nor remove keys) while iterating on any of that dictionary’s iterators. Iterating on the lists returned by items, keys, or values carries no such constraint. Iterating directly on a dictionary D  is exactly like iterating on D.iterkeys().

The popitem method can be used for destructive iteration on a dictionary. Both items and popitem return dictionary items as key/value pairs, but using popitem consumes less memory, as it does not rely on a separate list of items. The memory savings make the idiom usable for a loop on a huge dictionary, when what you want is to "consume" the dictionary in the course of the loop.

The setdefault method returns the same result as get, but if k  is not a key in D , setdefault also has the side effect of binding D[k] to the value x. Similarly, the pop method returns the same result as get, but if k is a key in D, pop also has the side effect of removing D[k] (when x  is not specified, and k  is not a key in D , get returns None, but pop raises an exception).

In Python 2.4, the update method can also accept an iterable of key/value pairs as an alternative argument instead of a mapping, and can accept keyword
arguments instead of or in addition to its only positional argument; the semantics are the same as for passing such arguments when calling the built-in dict type, as covered in "Dictionaries" on page 44.

Please check back next week for the continuation of this series.