========|
| "x in s"                   | "True" if an item of *s* is      | (1)        |
|                            | equal to *x*, else "False"       |            |
+----------------------------+----------------------------------+------------+
| "x not in s"               | "False" if an item of *s* is     | (1)        |
|                            | equal to *x*, else "True"        |            |
+----------------------------+----------------------------------+------------+
| "s + t"                    | the concatenation of *s* and *t* | (6)(7)     |
+----------------------------+----------------------------------+------------+
| "s * n" or "n * s"         | equivalent to adding *s* to      | (2)(7)     |
|                            | itself *n* times                 |            |
+----------------------------+----------------------------------+------------+
| "s[i]"                     | *i*th item of *s*, origin 0      | (3)        |
+----------------------------+----------------------------------+------------+
| "s[i:j]"                   | slice of *s* from *i* to *j*     | (3)(4)     |
+----------------------------+----------------------------------+------------+
| "s[i:j:k]"                 | slice of *s* from *i* to *j*     | (3)(5)     |
|                            | with step *k*                    |            |
+----------------------------+----------------------------------+------------+
| "len(s)"                   | length of *s*                    |            |
+----------------------------+----------------------------------+------------+
| "min(s)"                   | smallest item of *s*             |            |
+----------------------------+----------------------------------+------------+
| "max(s)"                   | largest item of *s*              |            |
+----------------------------+----------------------------------+------------+
| "s.index(x[, i[, j]])"     | index of the first occurrence of | (8)        |
|                            | *x* in *s* (at or after index    |            |
|                            | *i* and before index *j*)        |            |
+----------------------------+----------------------------------+------------+
| "s.count(x)"               | total number of occurrences of   |            |
|                            | *x* in *s*                       |            |
+----------------------------+----------------------------------+------------+

Sequences of the same type also support comparisons.  In particular,
tuples and lists are compared lexicographically by comparing
corresponding elements. This means that to compare equal, every
element must compare equal and the two sequences must be of the same
type and have the same length.  (For full details see Comparisons in
the language reference.)

Notes:

1. While the "in" and "not in" operations are used only for simple
   containment testing in the general case, some specialised sequences
   (such as "str", "bytes" and "bytearray") also use them for
   subsequence testing:

      >>> "gg" in "eggs"
      True

2. Values of *n* less than "0" are treated as "0" (which yields an
   empty sequence of the same type as *s*).  Note that items in the
   sequence *s* are not copied; they are referenced multiple times.
   This often haunts new Python programmers; consider:

      >>> lists = [[]] * 3
      >>> lists
      [[], [], []]
      >>> lists[0].append(3)
      >>> lists
      [[3], [3], [3]]

   What has happened is that "[[]]" is a one-element list containing
   an empty list, so all three elements of "[[]] * 3" are references
   to this single empty list.  Modifying any of the elements of
   "lists" modifies this single list. You can create a list of
   different lists this way:

      >>> lists = [[] for i in range(3)]
      >>> lists[0].append(3)
      >>> lists[1].append(5)
      >>> lists[2].append(7)
      >>> lists
      [[3], [5], [7]]

   Further explanation is available in the FAQ entry How do I create a
   multidimensional list?.

3. If *i* or *j* is negative, the index is relative to the end of
   sequence *s*: "len(s) + i" or "len(s) + j" is substituted.  But
   note that "-0" is still "0".

4. The slice of *s* from *i* to *j* is defined as the sequence of
   items with index *k* such that "i <= k < j".  If *i* or *j* is
   greater than "len(s)", use "len(s)".  If *i* is omitted or "None",
   use "0".  If *j* is omitted or "None", use "len(s)".  If *i* is
   greater than or equal to *j*, the slice is empty.

5. The slice of *s* from *i* to *j* with step *k* is defined as the
   sequence of items with index  "x = i + n*k" such that "0 <= n <
   (j-i)/k".  In other words, the indices are "i", "i+k", "i+2*k",
   "i+3*k" and so on, stopping when *j* is reached (but never
   including *j*).  When *k* is positive, *i* and *j* are reduced to
   "len(s)" if they are greater. When *k* is negative, *i* and *j* are
   reduced to "len(s) - 1" if they are greater.  If *i* or *j* are
   omitted or "None", they become “end” values (which end depends on
   the sign of *k*).  Note, *k* cannot be zero. If *k* is "None", it
   is treated like "1".

6. Concatenating immutable sequences always results in a new object.
   This means that building up a sequence by repeated concatenation
   will have a quadratic runtime cost in the total sequence length.
   To get a linear runtime cost, you must switch to one of the
   alternatives below:

   * if concatenating "str" objects, you can build a list and use
     "str.join()" at the end or else write to an "io.StringIO"
     instance and retrieve its value when complete

   * if concatenating "bytes" objects, you can similarly use
     "bytes.join()" or "io.BytesIO", or you can do in-place
     concatenation with a "bytearray" object.  "bytearray" objects are
     mutable and have an efficient overallocation mechanism

   * if concatenating "tuple" objects, extend a "list" instead

   * for other types, investigate the relevant class documentation

7. Some sequence types (such as "range") only support item sequences
   that follow specific patterns, and hence don’t support sequence
   concatenation or repetition.

8. "index" raises "ValueError" when *x* is not found in *s*. Not all
   implementations support passing the additional arguments *i* and
   *j*. These arguments allow efficient searching of subsections of
   the sequence. Passing the extra arguments is roughly equivalent to
   using "s[i:j].index(x)", only without copying any data and with the
   returned index being relative to the start of the sequence rather
   than the start of the slice.


Immutable Sequence Types
========================

The only operation that immutable sequence types generally implement
that is not also implemented by mutable sequence types is support for
the "hash()" built-in.

This support allows immutable sequences, such as "tuple" instances, to
be used as "dict" keys and stored in "set" and "frozenset" instances.

Attempting to hash an immutable sequence that contains unhashable
values will result in "TypeError".


Mutable Sequence Types
======================

The operations in the following table are defined on mutable sequence
types. The "collections.abc.MutableSequence" ABC is provided to make
it easier to correctly implement these operations on custom sequence
types.

In the table *s* is an instance of a mutable sequence type, *t* is any
iterable object and *x* is an arbitrary object that meets any type and
value restrictions imposed by *s* (for example, "bytearray" only
accepts integers that meet the value restriction "0 <= x <= 255").

+--------------------------------+----------------------------------+-----------------------+
| Operation                      | Result                           | Notes                 |
|================================|==================================|=======================|
| "s[i] = x"                     | item *i* of *s* is replaced by   |                       |
|                                | *x*                              |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s[i:j] = t"                   | slice of *s* from *i* to *j* is  |                       |
|                                | replaced by the contents of the  |                       |
|                                | iterable *t*                     |                       |
+--------------------------------+----------------------------------+-----------------------+
| "del s[i:j]"                   | same as "s[i:j] = []"            |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s[i:j:k] = t"                 | the elements of "s[i:j:k]" are   | (1)                   |
|                                | replaced by those of *t*         |                       |
+--------------------------------+----------------------------------+-----------------------+
| "del s[i:j:k]"                 | removes the elements of          |                       |
|                                | "s[i:j:k]" from the list         |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.append(x)"                  | appends *x* to the end of the    |                       |
|                                | sequence (same as                |                       |
|                                | "s[len(s):len(s)] = [x]")        |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.clear()"                    | removes all items from *s* (same | (5)                   |
|                                | as "del s[:]")                   |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.copy()"                     | creates a shallow copy of *s*    | (5)                   |
|                                | (same as "s[:]")                 |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.extend(t)" or "s += t"      | extends *s* with the contents of |                       |
|                                | *t* (for the most part the same  |                       |
|                                | as "s[len(s):len(s)] = t")       |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s *= n"                       | updates *s* with its contents    | (6)                   |
|                                | repeated *n* times               |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.insert(i, x)"               | inserts *x* into *s* at the      |                       |
|                                | index given by *i* (same as      |                       |
|                                | "s[i:i] = [x]")                  |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.pop()" or "s.pop(i)"        | retrieves the item at *i* and    | (2)                   |
|                                | also removes it from *s*         |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.remove(x)"                  | remove the first item from *s*   | (3)                   |
|                                | where "s[i]" is equal to *x*     |                       |
+--------------------------------+----------------------------------+-----------------------+
| "s.reverse()"                  | reverses the items of *s* in     | (4)                   |
|                                | place                            |                       |
+--------------------------------+----------------------------------+-----------------------+

Notes:

1. *t* must have the same length as the slice it is replacing.

2. The optional argument *i* defaults to "-1", so that by default the
   last item is removed and returned.

3. "remove()" raises "ValueError" when *x* is not found in *s*.

4. The "reverse()" method modifies the sequence in place for economy
   of space when reversing a large sequence.  To remind users that it
   operates by side effect, it does not return the reversed sequence.

5. "clear()" and "copy()" are included for consistency with the
   interfaces of mutable containers that don’t support slicing
   operations (such as "dict" and "set"). "copy()" is not part of the
   "collections.abc.MutableSequence" ABC, but most concrete mutable
   sequence classes provide it.

   New in version 3.3: "clear()" and "copy()" methods.

6. The value *n* is an integer, or an object implementing
   "__index__()".  Zero and negative values of *n* clear the sequence.
   Items in the sequence are not copied; they are referenced multiple
   times, as explained for "s * n" under Common Sequence Operations.


Lists
=====

Lists are mutable sequences, typically used to store collections of
homogeneous items (where the precise degree of similarity will vary by
application).

class list([iterable])

   Lists may be constructed in several ways:

   * Using a pair of square brackets to denote the empty list: "[]"

   * Using square brackets, separating items with commas: "[a]", "[a,
     b, c]"

   * Using a list comprehension: "[x for x in iterable]"

   * Using the type constructor: "list()" or "list(iterable)"

   The constructor builds a list whose items are the same and in the
   same order as *iterable*’s items.  *iterable* may be either a
   sequence, a container that supports iteration, or an iterator
   object.  If *iterable* is already a list, a copy is made and
   returned, similar to "iterable[:]". For example, "list('abc')"
   returns "['a', 'b', 'c']" and "list( (1, 2, 3) )" returns "[1, 2,
   3]". If no argument is given, the constructor creates a new empty
   list, "[]".

   Many other operations also produce lists, including the "sorted()"
   built-in.

   Lists implement all of the common and mutable sequence operations.
   Lists also provide the following additional method:

   sort(*, key=None, reverse=False)

      This method sorts the list in place, using only "<" comparisons
      between items. Exceptions are not suppressed - if any comparison
      operations fail, the entire sort operation will fail (and the
      list will likely be left in a partially modified state).

      "sort()" accepts two arguments that can only be passed by
      keyword (keyword-only arguments):

      *key* specifies a function of one argument that is used to
      extract a comparison key from each list element (for example,
      "key=str.lower"). The key corresponding to each item in the list
      is calculated once and then used for the entire sorting process.
      The default value of "None" means that list items are sorted
      directly without calculating a separate key value.

      The "functools.cmp_to_key()" utility is available to convert a
      2.x style *cmp* function to a *key* function.

      *reverse* is a boolean value.  If set to "True", then the list
      elements are sorted as if each comparison were reversed.

      This method modifies the sequence in place for economy of space
      when sorting a large sequence.  To remind users that it operates
      by side effect, it does not return the sorted sequence (use
      "sorted()" to explicitly request a new sorted list instance).

      The "sort()" method is guaranteed to be stable.  A sort is
      stable if it guarantees not to change the relative order of
      elements that compare equal — this is helpful for sorting in
      multiple passes (for example, sort by department, then by salary
      grade).

      For sorting examples and a brief sorting tutorial, see Sorting
      HOW TO.

      **CPython implementation detail:** While a list is being sorted,
      the effect of attempting to mutate, or even inspect, the list is
      undefined.  The C implementation of Python makes the list appear
      empty for the duration, and raises "ValueError" if it can detect
      that the list has been mutated during a sort.


Tuples
======

Tuples are immutable sequences, typically used to store collections of
heterogeneous data (such as the 2-tuples produced by the "enumerate()"
built-in). Tuples are also used for cases where an immutable sequence
of homogeneous data is needed (such as allowing storage in a "set" or
"dict" instance).

class tuple([iterable])

   Tuples may be constructed in a number of ways:

   * Using a pair of parentheses to denote the empty tuple: "()"

   * Using a trailing comma for a singleton tuple: "a," or "(a,)"

   * Separating items with commas: "a, b, c" or "(a, b, c)"

   * Using the "tuple()" built-in: "tuple()" or "tuple(iterable)"

   The constructor builds a tuple whose items are the same and in the
   same order as *iterable*’s items.  *iterable* may be either a
   sequence, a container that supports iteration, or an iterator
   object.  If *iterable* is already a tuple, it is returned
   unchanged. For example, "tuple('abc')" returns "('a', 'b', 'c')"
   and "tuple( [1, 2, 3] )" returns "(1, 2, 3)". If no argument is
   given, the constructor creates a new empty tuple, "()".

   Note that it is actually the comma which makes a tuple, not the
   parentheses. The parentheses are optional, except in the empty
   tuple case, or when they are needed to avoid syntactic ambiguity.
   For example, "f(a, b, c)" is a function call with three arguments,
   while "f((a, b, c))" is a function call with a 3-tuple as the sole
   argument.

   Tuples implement all of the common sequence operations.

For heterogeneous collections of data where access by name is clearer
than access by index, "collections.namedtuple()" may be a more
appropriate choice than a simple tuple object.


Ranges
======

The "range" type represents an immutable sequence of numbers and is
commonly used for looping a specific number of times in "for" loops.

class range(stop)
class range(start, stop[, step])

   The arguments to the range constructor must be integers (either
   built-in "int" or any object that implements the "__index__()"
   special method).  If the *step* argument is omitted, it defaults to
   "1". If the *start* argument is omitted, it defaults to "0". If
   *step* is zero, "ValueError" is raised.

   For a positive *step*, the contents of a range "r" are determined
   by the formula "r[i] = start + step*i" where "i >= 0" and "r[i] <
   stop".

   For a negative *step*, the contents of the range are still
   determined by the formula "r[i] = start + step*i", but the
   constraints are "i >= 0" and "r[i] > stop".

   A range object will be empty if "r[0]" does not meet the value
   constraint. Ranges do support negative indices, but these are
   interpreted as indexing from the end of the sequence determined by
   the positive indices.

   Ranges containing absolute values larger than "sys.maxsize" are
   permitted but some features (such as "len()") may raise
   "OverflowError".

   Range examples:

      >>> list(range(10))
      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
      >>> list(range(1, 11))
      [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
      >>> list(range(0, 30, 5))
      [0, 5, 10, 15, 20, 25]
      >>> list(range(0, 10, 3))
      [0, 3, 6, 9]
      >>> list(range(0, -10, -1))
      [0, -1, -2, -3, -4, -5, -6, -7, -8, -9]
      >>> list(range(0))
      []
      >>> list(range(1, 0))
      []

   Ranges implement all of the common sequence operations except
   concatenation and repetition (due to the fact that range objects
   can only represent sequences that follow a strict pattern and
   repetition and concatenation will usually violate that pattern).

   start

      The value of the *start* parameter (or "0" if the parameter was
      not supplied)

   stop

      The value of the *stop* parameter

   step

      The value of the *step* parameter (or "1" if the parameter was
      not supplied)

The advantage of the "range" type over a regular "list" or "tuple" is
that a "range" object will always take the same (small) amount of
memory, no matter the size of the range it represents (as it only
stores the "start", "stop" and "step" values, calculating individual
items and subranges as needed).

Range objects implement the "collections.abc.Sequence" ABC, and
provide features such as containment tests, element index lookup,
slicing and support for negative indices (see Sequence Types — list,
tuple, range):

>>> r = range(0, 20, 2)
>>> r
range(0, 20, 2)
>>> 11 in r
False
>>> 10 in r
True
>>> r.index(10)
5
>>> r[5]
10
>>> r[:5]
range(0, 10, 2)
>>> r[-1]
18

Testing range objects for equality with "==" and "!=" compares them as
sequences.  That is, two range objects are considered equal if they
represent the same sequence of values.  (Note that two range objects
that compare equal might have different "start", "stop" and "step"
attributes, for example "range(0) == range(2, 1, 3)" or "range(0, 3,
2) == range(0, 4, 2)".)

Changed in version 3.2: Implement the Sequence ABC. Support slicing
and negative indices. Test "int" objects for membership in constant
time instead of iterating through all items.

Changed in version 3.3: Define ‘==’ and ‘!=’ to compare range objects
based on the sequence of values they define (instead of comparing
based on object identity).

New in version 3.3: The "start", "stop" and "step" attributes.

See also:

  * The linspace recipe shows how to implement a lazy version of range
    suitable for floating point applications.
u