本文将详细讲解collections模块中的所有类，和每个类中的方法，从源码和性能的角度剖析。

一个模块主要用来干嘛，有哪些类可以使用，看__init__.py就知道

'''This module implements specialized container datatypes providing
alternatives to Python's general purpose built-in containers, dict,
list, set, and tuple.

* namedtuple   factory function for creating tuple subclasses with named fields
* deque        list-like container with fast appends and pops on either end
* ChainMap     dict-like class for creating a single view of multiple mappings
* Counter      dict subclass for counting hashable objects
* OrderedDict  dict subclass that remembers the order entries were added
* defaultdict  dict subclass that calls a factory function to supply missing values
* UserDict     wrapper around dictionary objects for easier dict subclassing
* UserList     wrapper around list objects for easier list subclassing
* UserString   wrapper around string objects for easier string subclassing

'''

__all__ = ['deque', 'defaultdict', 'namedtuple', 'UserDict', 'UserList',
            'UserString', 'Counter', 'OrderedDict', 'ChainMap']

collections模块实现一些特定的数据类型，可以替代Python中常用的内置数据类型如dict, list, set, tuple，简单说就是对基本数据类型做了更上一层的处理。

一、deque

用途：双端队列，头部和尾部都能以O(1)时间复杂度插入和删除元素。类似于列表的容器

所谓双端队列，就是两端都能操作，与Python内置的list区别在于：头部插入与删除的时间复杂度为O(1)，来个栗子感受一下：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# __author__ = 'liao gao xiang'

"""
保留最后n个元素
"""
from collections import deque


def search(file, pattern, history=5):
    previous_lines = deque(maxlen=history)
    for l in file:
        if pattern in l:
            yield l, previous_lines  # 使用yield表达式的生成器函数，将搜索过程的代码和搜索结果的代码解耦
        previous_lines.append(l)


with open(b'file.txt', mode='r', encoding='utf-8') as f:
    for line, prevlines in search(f, 'Python', 5):
        for pline in prevlines:
            print(pline, end='')
        print(line, end='')

d = deque()
d.append(1)
d.append("2")
print(len(d))
print(d[0], d[1])
d.extendleft([0])
print(d)
d.extend([6, 7, 8])
print(d)

d2 = deque('12345')
print(len(d2))
d2.popleft()
print(d2)
d2.pop()
print(d2)

# 在队列两端插入或删除元素时间复杂度都是 O(1) ，区别于列表，在列表的开头插入或删除元素的时间复杂度为 O(N)
d3 = deque(maxlen=2)
d3.append(1)
d3.append(2)
print(d3)
d3.append(3)
print(d3)

输出结果如下

人生苦短
我用Python
2
1 2
deque([0, 1, '2'])
deque([0, 1, '2', 6, 7, 8])
5
deque(['2', '3', '4', '5'])
deque(['2', '3', '4'])
deque([1, 2], maxlen=2)
deque([2, 3], maxlen=2)

因此，如果你遇到经常操作列表头的场景，使用deque最好。deque类的所有方法，自行操作一遍就知道了。

class deque(object):
    """
    deque([iterable[, maxlen]]) --> deque object

    A list-like sequence optimized for data accesses near its endpoints.
    """
    def append(self, *args, **kwargs): # real signature unknown
        """ Add an element to the right side of the deque. """
        pass

    def appendleft(self, *args, **kwargs): # real signature unknown
        """ Add an element to the left side of the deque. """
        pass

    def clear(self, *args, **kwargs): # real signature unknown
        """ Remove all elements from the deque. """
        pass

    def copy(self, *args, **kwargs): # real signature unknown
        """ Return a shallow copy of a deque. """
        pass

    def count(self, value): # real signature unknown; restored from __doc__
        """ D.count(value) -> integer -- return number of occurrences of value """
        return 0

    def extend(self, *args, **kwargs): # real signature unknown
        """ Extend the right side of the deque with elements from the iterable """
        pass

    def extendleft(self, *args, **kwargs): # real signature unknown
        """ Extend the left side of the deque with elements from the iterable """
        pass

    def index(self, value, start=None, stop=None): # real signature unknown; restored from __doc__
        """
        D.index(value, [start, [stop]]) -> integer -- return first index of value.
        Raises ValueError if the value is not present.
        """
        return 0

    def insert(self, index, p_object): # real signature unknown; restored from __doc__
        """ D.insert(index, object) -- insert object before index """
        pass

    def pop(self, *args, **kwargs): # real signature unknown
        """ Remove and return the rightmost element. """
        pass

    def popleft(self, *args, **kwargs): # real signature unknown
        """ Remove and return the leftmost element. """
        pass

    def remove(self, value): # real signature unknown; restored from __doc__
        """ D.remove(value) -- remove first occurrence of value. """
        pass

    def reverse(self): # real signature unknown; restored from __doc__
        """ D.reverse() -- reverse *IN PLACE* """
        pass

    def rotate(self, *args, **kwargs): # real signature unknown
        """ Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left. """
        pass

这里提示一下，有些函数对队列进行操作，但返回值是None，比如reverse()反转队列，rotate(1)将队列中元素向右移1位，尾部的元素移到头部。

二、defaultdict

用途：带有默认值的字典。父类为Python内置的dict

字典带默认值有啥好处？举个栗子，一般来讲，创建一个多值映射字典是很简单的。但是，如果你选择自己实现的话， 那么对于值的初始化可能会有点麻烦，你可能会像下面这样来实现：

d = {}
for key, value in pairs:
    if key not in d:
        d[key] = []
    d[key].append(value)

如果使用 defaultdict 的话代码就更加简洁了：

d = defaultdict(list)
for key, value in pairs:
    d[key].append(value)

defaultdict 的一个特征是它会自动初始化每个 key 刚开始对应的值，所以你只需要 关注添加元素操作了。比如：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# __author__ = 'liao gao xiang'

# 字典中的键映射多个值
from collections import defaultdict

d = defaultdict(list)
print(d)
d['a'].append([1, 2, 3])
d['b'].append(2)
d['c'].append(3)

print(d)

d = defaultdict(set)
print(d)
d['a'].add(1)
d['a'].add(2)
d['b'].add(4)

print(d)

输出结果如下：

defaultdict(<class 'list'>, {})
defaultdict(<class 'list'>, {'a': [[1, 2, 3]], 'b': [2], 'c': [3]})
defaultdict(<class 'set'>, {})
defaultdict(<class 'set'>, {'a': {1, 2}, 'b': {4}})

三、namedtuple()

用途：创建命名字段的元组。工厂函数

namedtuple主要用来产生可以使用名称来访问元素的数据对象，通常用来增强代码的可读性， 在访问一些tuple类型的数据时尤其好用。

比如我们用户拥有一个这样的数据结构，每一个对象是拥有三个元素的tuple。使用namedtuple方法就可以方便的通过tuple来生成可读性更高也更好用的数据结构。

from collections import namedtuple

websites = [
    ('Sohu', 'http://www.sohu.com/', u'张朝阳'),
    ('Sina', 'http://www.sina.com.cn/', u'王志东'),
    ('163', 'http://www.163.com/', u'丁磊')
]

Website = namedtuple('Website', ['name', 'url', 'founder'])

for website in websites:
    website = Website._make(website)
    print website


# 输出结果:
Website(name='Sohu', url='http://www.sohu.com/', founder=u'\u5f20\u671d\u9633')
Website(name='Sina', url='http://www.sina.com.cn/', founder=u'\u738b\u5fd7\u4e1c')
Website(name='163', url='http://www.163.com/', founder=u'\u4e01\u78ca')

注意，namedtuple是函数，不是类。

四、Counter

用途：统计可哈希的对象。父类为Python内置的dict

寻找序列中出现次数最多的元素。假设你有一个单词列表并且想找出哪个单词出现频率最高：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# __author__ = 'liao gao xiang'

from collections import Counter

words = [
    'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
    'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the',
    'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into',
    'my', 'eyes', "you're", 'under'
]

word_counts = Counter(words)

# 出现频率最高的三个单词
top_three = word_counts.most_common(3)
print(top_three)
# Outputs [('eyes', 8), ('the', 5), ('look', 4)]
print(word_counts['eyes'])

morewords = ['why', 'are', 'you', 'not', 'looking', 'in', 'my', 'eyes']

# 如果你想手动增加计数，可以简单的用加法：
for word in morewords:
    print(word)
    word_counts[word] += 1
print(word_counts['eyes'])

结果如下：

[('eyes', 8), ('the', 5), ('look', 4)]
8
why
are
you
not
looking
in
my
eyes
9

因为Counter继承自dict，所有dict有的方法它都有（defaultdict和OrderedDict也是的），Counter自己实现或重写了6个方法：

• most_common(self, n=None),
• elements(self)
• fromkeys(cls, iterable, v=None)
• update(*args, **kwds)
• subtract(*args, **kwds)
• copy(self)

五、OrderedDict

用途：排序的字段。父类为Python内置的dict

OrderedDict在迭代操作的时候会保持元素被插入时的顺序，OrderedDict内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候，它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。

需要注意的是，一个OrderedDict的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。 所以如果你要构建一个需要大量OrderedDict 实例的数据结构的时候(比如读取100,000行CSV数据到一个 OrderedDict 列表中去)，那么你就得仔细权衡一下是否使用 OrderedDict带来的好处要大过额外内存消耗的影响。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# __author__ = 'liao gao xiang'

from collections import OrderedDict

d = OrderedDict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grok'] = 4
# d['bar'] = 22 #对于一个已经存在的键，重复赋值不会改变键的顺序
for key in d:
    print(key, d[key])

print(d)

import json

print(json.dumps(d))

结果如下：

foo 1
bar 2
spam 3
grok 4
OrderedDict([('foo', 1), ('bar', 2), ('spam', 3), ('grok', 4)])
{"foo": 1, "bar": 2, "spam": 3, "grok": 4}

OrderDict实现或重写了如下方法。都是干嘛的？这个留给大家当课后作业了^_^

• clear(self)
• popitem(self, last=True)
• move_to_end(self, key, last=True)
• keys(self)
• items(self)
• values(self)
• pop(self, key, default=__marker)
• setdefault(self, key, default=None)
• copy(self)
• fromkeys(cls, iterable, value=None)

六、ChainMap

用途：创建多个可迭代对象的集合。类字典类型

很简单，如下：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# __author__ = 'liao gao xiang'

from collections import ChainMap
from itertools import chain

# 不同集合上元素的迭代
a = [1, 2, 3, 4]
b = ('x', 'y', 'z')
c = {1, 'a'}

# 方法一，使用chain
for i in chain(a, b, c):
    print(i)
print('--------------')
# 方法二，使用chainmap
for j in ChainMap(a, b, c):
    print(j)

# 这两种均为节省内存，效率更高的迭代方式

一个 ChainMap 接受多个字典并将它们在逻辑上变为一个字典。然后，这些字典并不是真的合并在一起了，ChainMap 类只是在内部创建了一个容纳这些字典的列表并重新定义了一些常见的字典操作来遍历这个列表。大部分字典操作都是可以正常使用的，比如：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# __author__ = 'liao gao xiang'

# 合并多个字典和映射
a = {'x': 1, 'z': 3}
b = {'y': 2, 'z': 4}
# 现在假设你必须在两个字典中执行查找操作
# (比如先从 a 中找，如果找不到再在 b 中找)。
# 一个非常简单的解决方案就是使用collections模块中的ChainMap类
from collections import ChainMap

c = ChainMap(a, b)

print(c)
a['x'] = 11  # 使用ChainMap时，原字典做了更新，这种更新会合并到新的字典中去

print(c)  # 按顺序合并两个字典
print(c['x'])
print(c['y'])
print(c['z'])

# 对于字典的更新或删除操作影响的总是列中的第一个字典。
c['z'] = 10
c['w'] = 40
del c['x']
print(a)
# del c['y']将出现报错

# ChainMap对于编程语言中的作用范围变量（比如globals,locals等）
# 是非常有用的。事实上，有一些方法可以使它变得简单：
values = ChainMap()  # 默认会创建一个空字典
print('\t', values)
values['x'] = 1
values = values.new_child()  # 添加一个空字典
values['x'] = 2
values = values.new_child()
values['x'] = 30
# values = values.new_child()
print(values, values['x'])  # values['x']输出最后一次添加的值
values = values.parents  # 删除上一次添加的字典
print(values['x'])
values = values.parents
print(values)

a = {'x': 1, 'y': 2}
b = {'y': 2, 'z': 3}
merge = dict(b)
merge.update(a)
print(merge['x'], merge['y'], merge['z'])
a['x'] = 11
print(merge['x'])

输出结果如下：

ChainMap({'x': 1, 'z': 3}, {'y': 2, 'z': 4})
ChainMap({'x': 11, 'z': 3}, {'y': 2, 'z': 4})
11
2
3
{'z': 10, 'w': 40}
     ChainMap({})
ChainMap({'x': 30}, {'x': 2}, {'x': 1}) 30
2
ChainMap({'x': 1})
1 2 3
1

作为ChainMap的替代，你可能会考虑使用 update() 方法将两个字典合并。这样也能行得通，但是它需要你创建一个完全不同的字典对象(或者是破坏现有字典结构)。同时，如果原字典做了更新，这种改变不会反应到新的合并字典中去。

ChainMap实现或重写了如下方法：

• get(self, key, default=None)
• fromkeys(cls, iterable, *args)
• copy(self)
• new_child(self, m=None)
• parents(self)
• popitem(self)
• pop(self, key, *args)
• clear(self)

七、UserDict、UserList、UserString

这三个类是分别对 dict、list、str 三种数据类型的包装，其主要是为方便用户实现自己的数据类型。在 Python2 之前，这三个类分别位于 UserDict、UserList、UserString 三个模块中，需要用类似于 from UserDict import UserDict 的方式导入。在 Python3 之后则被挪到了 collections 模块中。这三个类都是基类，如果用户要扩展这三种类型，只需继承这三个类即可。