High performance container

OrderedDict

It is a dict and it has order. It could be constructed by dict.

from collections import OrderedDict
od = OrderedDict({i: j for i, j in zip(['a', 'b','c'], [1,2,3])})
>>> od
OrderedDict([('a', 1), ('b', 2), ('c', 3)])

Access by index

>>> list(od.items())[0]
(‘a’, 1)

Change value doesn’t influence order

>>> od['a'] = 0
>>> od
OrderedDict([('a', 0), ('b', 2), ('c', 3)])

Inserting a new value will append to the end.

>>> od['d'] = 4
>>> od
OrderedDict([('a', 0), ('b', 2), ('c', 3), ('d', 4)])

queue

PriorityQueue

PriorityQueue is a container for min heap.

from queue import PriorityQueue
q = PriorityQueue()
q.put(3)
q.put(1)
q.put(2)

>>> q.get()
1
>>> q.get()
2

The PriorityQueue get() method returns min value. To get a maxheap, use put((-value, value)).

from queue import PriorityQueue
q = PriorityQueue()

# Your original value is 3, 1, 2.
q.put((-3, 3))
q.put((-1, 1))
q.put((-2, 2))

q.get()
>>> (-3, 3)

Store data with priority number in PriorityQueue

from queue import PriorityQueue
q = PriorityQueue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
    next_item = q.get()
    print(next_item)

# Result:
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

Function based API of heapq

import heapq
q = []

heapq.heappush(q, (2, 'code'))
heapq.heappush(q, (1, 'eat'))
heapq.heappush(q, (3, 'sleep'))

while q:
    next_item = heapq.heappop(q)
    print(next_item)

# Result:
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

Class based API of Queue

from queue import Queue

q = Queue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
    next_item = q.get()
    print(next_item)

# Result:
#   (2, 'code')
#   (1, 'eat')
#   (3, 'sleep')

deque

>>> from collections import deque
>>> d = deque('ghi')                 # make a new deque with three items
>>> for elem in d:                   # iterate over the deque's elements
...     print(elem.upper())
G
H
I

>>> d.append('j')                    # add a new entry to the right side
>>> d.appendleft('f')                # add a new entry to the left side
>>> d                                # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])

>>> d.pop()                          # return and remove the rightmost item
'j'
>>> d.popleft()                      # return and remove the leftmost item
'f'
>>> list(d)                          # list the contents of the deque
['g', 'h', 'i']
>>> d[0]                             # peek at leftmost item
'g'
>>> d[-1]                            # peek at rightmost item
'i'

>>> list(reversed(d))                # list the contents of a deque in reverse
['i', 'h', 'g']
>>> 'h' in d                         # search the deque
True
>>> d.extend('jkl')                  # add multiple elements at once
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1)                      # right rotation
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1)                     # left rotation
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

>>> deque(reversed(d))               # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear()                        # empty the deque
>>> d.pop()                          # cannot pop from an empty deque
Traceback (most recent call last):
    File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
IndexError: pop from an empty deque

>>> d.extendleft('abc')              # extendleft() reverses the input order
>>> d
deque(['c', 'b', 'a'])