Built-in Collections and Comprehensions

Key points

1. 1

   Lists are dynamic arrays: append and pop at the end are O(1), but insert(0), pop(0) and x in lst are O(n). Use deque for queues and set for membership.

2. 2

   Slices clamp their bounds and never raise; plain slice assignment can resize the list, while extended slices (with a step) need the same number of items.

3. 3

   sorted() returns a new list and list.sort() returns None. Sorts are stable, so multi-key sorts can be done with a tuple key or with successive sorts from the least significant key.

4. 4

   Dicts keep insertion order (guaranteed since 3.7). keys(), values() and items() are live views, and key views support set operations. d1 | d2 (3.9) merges with right-hand values winning.

5. 5

   defaultdict inserts on any d[key] read; Counter returns 0 for missing keys without inserting, and its arithmetic operators drop non-positive counts.

6. 6

   itertools.groupby only groups consecutive equal keys, so sort with the same key first; group iterators are shared and are emptied when groupby advances.

7. 7

   heapq is a min-heap on a plain list: heapify first, and add a counter as a tie-breaker when payloads are not comparable.

Read the source

• Built-in Types (sequences, sets, mappings)
• collections: Container datatypes
• Sorting Techniques