内置标准库之collections

数据结构的概念很好理解，就是用来将数据组织在一起的结构。换句话说，数据结构是用来存储一系列相关联数据的数据集合。在 Python 中有四种内建的数据结构，分别是 List、 Tuple、Dictionary 以及 Set。大部分的应用程序不需要其他类型的数据结构，但若是真需要也有很多高级数据结构可供选择，例如 Array、 Heapq、 Bisect、 Collection、 Weakref、 Copy 以及 Pprint。下面将介绍这些数据结构的用法，看看它们是如何帮助我们提高使用效率的。

---

• 官网地址

  • collections — Container datatypes
  • Python 3 Module of the Week

• 函数概览

编号	函数名称	对应含义解释说明
1	deque	类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)
2	nametuple()	创建命名元组子类的工厂函数
3	Counter	字典的子类，提供了可哈希对象的计数功能
4	OrderedDict	字典的子类，保存了他们被添加的顺序
5	defaultdict	字典的子类，提供了一个工厂函数，为字典查询提供一个默认值
6	UserDict	封装了字典对象，简化了字典子类化
7	UserList	封装了列表对象，简化了列表子类化
8	UserString	封装了列表对象，简化了字符串子类化
9	ChainMap	类似字典(dict)的容器类，将多个映射集合到一个视图里面

---

1. deque

类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)。

• Deque 是一种由队列结构扩展而来的双端队列(double-ended queue)，队列元素能够在队列两端添加或删除。因此它还被称为头尾连接列表(head-tail linked list)，尽管叫这个名字的还有另一个特殊的数据结构实现。

• Deque 是线程安全的，经过优化的 append 和 pop 操作，在队列两端的相关操作都能够达到近乎于 O(1) 的时间复杂度。虽然 list 也支持类似的操作，但是它是对定长列表的操作表现很不错，而当遇到 pop(0) 和 insert(0, v) 这样既改变了列表的长度又改变其元素位置的操作时，其复杂度就变为 O(n) 了。

In [1]: import collections

In [2]: lst = collections.deque()

In [3]: lst.append('B')

In [4]: lst.append('C')

In [5]: lst.appendleft('A')

In [6]: lst
Out[6]: deque(['A', 'B', 'C'])

In [7]: lst.insert(2, 'D')

In [8]: lst
Out[8]: deque(['A', 'B', 'D', 'C'])

In [9]: lst.pop()
Out[9]: 'C'

In [10]: lst.popleft()
Out[10: 'A'

In [11]: lst
Out[11]: deque(['B', 'D'])

In [12]: lst.remove('B')

In [13]: lst.index('D')
Out[13]: 0

In [14]: lst
Out[14]: deque(['D'])

• 双端队列 Deque 比普通的列表多了一些特殊方法，如 rotate 方法是队列的旋转操作，正参数是将右端的元素移动到左端，而 负参数则相反。

In [1]: import collections

In [2]: lst = collections.deque(range(5))

In [3]: lst
Out[3]: deque([0, 1, 2, 3, 4])

In [4]: lst.rotate(3)

In [5]: lst
Out[5]: deque([2, 3, 4, 0, 1])

In [6]: lst.rotate(-3)

In [7]: lst
Out[7]: deque([0, 1, 2, 3, 4])

---

2. nametuple

创建命名元组子类的工厂函数。

• 顾名思义，nametuple 就是一个命名元组，可以使用名子的方式访问元素内容的 tuple 子类。以前，使用命名元组会创建一个类，需要我们事先定义好名称和属性。如下例所示，名称为 People 且存在三个属性，分别为 name、 age、 sex。

# 传统元组写法
In [1]: Bob = ('bob', 30, 'male')

In [2]: f'{Bob[0]} is {Bob[1]} years old {Bob[2]}'
Out[2]: 'bobis30 years old male'

# 使用命名元组的写法
In [1]: from collections import namedtuple

In [2]: People = namedtuple('People', 'name age sex')

In [3]: Bob = People('bob', 30, 'male')

In [4]: f'{Bob.name} is {Bob.age} years old {Bob.sex}'
Out[4]: 'bobis30 years old male'

---

3. Counter

字典的子类，提供了可哈希对象的计数功能。

• 如果你想统计一个单词在给定的序列中一共出现了多少次，诸如此类的操作就可以用到 Counter 这个 Python 自带的计数器实现。它不仅支持字符串、列表、字典等的计数统计，而且还是对计数进行叠加。

In [1]: from collections import Counter

In [2]: c = Counter('hello world')

In [3]: c.most_common(2)
Out[3]: [('l', 3), ('o', 2)]

In [4]: c = Counter(['a', 'b', 'c', 'a', 'b', 'a'])

In [5]: c
Out[5]: Counter({'a': 3, 'b': 2, 'c': 1})

In [6]: c.update(['a', 'b', 'a', 'c'])

In [7]: c
Out[7]: Counter({'a': 5, 'b': 3, 'c': 2})

In [8]: c = Counter({'a': 2, 'b': 5})

In [9]: c.update(['a', 'b'], a=3, c=1)

In [10]: c
Out[10]: Counter({'a': 6, 'b': 6, 'c': 1})

---

4. OrderedDict

顾名思义，有顺序的词典，次序不再是随机的。

普通的dict不记录插入的顺序，遍历其值的时候是随机的，相反，OrderedDict记录插入的顺序，在迭代的时候可以看出差异。

遍历

• 一个OrderedDict是一个字典子类，它记住添加其内容的顺序。

# input
print 'Regular dictionary:'
d = {}
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
for key, value in d.items():
    print key, value


# output
Regular dictionary:
a A
c C
b B

# input
print 'OrderedDict:'
d = collections.OrderedDict()
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
for key, value in d.items():
    print key, value


# output
OrderedDict:
a A
b B
c C

>>> # regular unsorted dictionary
>>> d = {'banana': 3, 'apple':4, 'pear': 1, 'orange': 2}

>>> # dictionary sorted by key
>>> OrderedDict(sorted(d.items(), key=lambda t: t[0]))
OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])

>>> # dictionary sorted by value
>>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

>>> # dictionary sorted by length of the key string
>>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

相等比较

• 比较两个词典是否相等，普通词典比较只看内容，内容相同即判定相等为真。
• 而OrderedDict同时会考虑顺序，item被添加的顺序。

print 'dict       :',
d1 = {}
d1['a'] = 'A'
d1['b'] = 'B'
d1['c'] = 'C'

d2 = {}
d2['b'] = 'B'
d2['a'] = 'A'
d2['c'] = 'C'

print d1 == d2
dict       : True

print 'OrderedDict:',
d1 = collections.OrderedDict()
d1['a'] = 'A'
d1['b'] = 'B'
d1['c'] = 'C'

d2 = collections.OrderedDict()
d2['b'] = 'B'
d2['a'] = 'A'
d2['c'] = 'C'

print d1 == d2
OrderedDict: False

重新排序

• 通过使用 move_to_end() 方法可以将指定的元素移动到序列的开始或结尾位置，可以改变 OrderedDict 中的键值顺序。最后一个参数告诉 move_to_end() 是否将项目移动到键序列中的最后一个(当为True时)或第一个(当为False时)。

# collections_orderedict_move_to_end.py
import collections

d = collections.OrderedDict(
    [('a', 'A'), ('b', 'B'), ('c', 'C')]
)

print('Before:')
for k, v in d.items():
    print(k, v)
d.move_to_end('b')

print('\nmove_to_end():')
for k, v in d.items():
    print(k, v)
d.move_to_end('b', last=False)

print('\nmove_to_end(last=False):')
for k, v in d.items():
    print(k, v)

$ python3 collections_ordereddict_move_to_end.py
Before:
a A
b B
c C

move_to_end():
a A
c C
b B

move_to_end(last=False):
b B
a A
c C

---

5. defaultdict

提供了一个工厂函数，为字典查询提供一个默认值。

• 这个类型，除了在处理不存在的键的操作之外与普通的字典完全相同。当查找一个不存在的键操作发生时，它的 default_factory 会被调用，提供一个默认的值，并且将这对键值存储下来。其他的参数同普通的字典方法 dict() 一致，一个 defaultdict 的实例同内建 dict 一样拥有同样地操作。

from collections import defaultdict

def default_factory():
    return 'default value'

d = defaultdict(default_factory, foo='bar')
print('d:', d)
print('foo =>', d['foo'])
print('bar =>', d['bar'])

$ python3 collections_defaultdict.py
d: defaultdict(<function default_factory at 0x101341950>,
{'foo': 'bar'})
foo => bar
bar => default value

• defaultdict 对象在当你希望使用它存放追踪数据的时候很有用。举个例子，假定你希望追踪一个单词在字符串中的位置，那么你可以这么做。

• 这里是选择 lists 或 sets 与 defaultdict 搭配取决于你的目的。使用 list 能够保存你插入元素的顺序，而使用 set 则不关心元素插入顺序，它会帮助消除重复元素。

from collections import defaultdict

s = "the quick brown fox jumps over the lazy dog"

words = s.split()
location = defaultdict(list)
for m, n in enumerate(words):
    location[n].append(m)
print(location)

defaultdict(<class 'list'>,
            {'brown': [2],
             'dog': [8],
             'fox': [3],
             'jumps': [4],
             'lazy': [7],
             'over': [5],
             'quick': [1],
             'the': [0, 6]})

• 另一种，创建multidict的方法。

s = "the quick brown fox jumps over the lazy dog"

d = {}
words = s.split()
for key, value in enumerate(words):
    d.setdefault(key, []).append(value)
print(d)

---

6. ChainMap

类似字典(dict)的容器类，将多个映射集合到一个视图里面。

ChainMap 将其搜索的映射列表存储在其 maps 属性的列表中。该列表是可变的，因此可以直接添加新映射或更改元素的顺序以控制查找和更新行为。

import collections

a = {'a': 'A', 'c': 'C'}
b = {'b': 'B', 'c': 'D'}

m = collections.ChainMap(a, b)

print(m.maps)
print('c = {}\n'.format(m['c']))

# reverse the list
m.maps = list(reversed(m.maps))

print(m.maps)
print('c = {}'.format(m['c']))

$ python3 collections_chainmap_reorder.py
[{'a': 'A', 'c': 'C'}, {'b': 'B', 'c': 'D'}]
c = C

[{'b': 'B', 'c': 'D'}, {'a': 'A', 'c': 'C'}]
c = D

---

7. User

这三个类是分别对 dict、list、str 三种数据类型的包装，其主要是为方便用户实现自己的数据类型。

• UserDict

这个类封装了字典对象。

• UserList

这个类封装了列表对象。

• UserString

Python 支持一个 String，如 collections 模块中存在一个名为 UserString 的容器。此类充当字符串对象的包装器类。当一个人想要创建自己的带有某些修改功能或某些新功能的字符串时，此类非常有用。它可以被视为为字符串添加新行为的一种方式。此类采用任何可以转换为字符串的参数，并模拟其内容保留在常规字符串中的字符串。该类的 data 属性可以访问该字符串。

from collections import UserString

# ''
user1 = UserString("")
print(user1.data)

# 12344
user2 = UserString(12344)
print(user2.data)

from collections import UserString

class Mystring(UserString):
    def append(self, s):
        self.data += s

    def remove(self, s):
        self.data = self.data.replace(s, "")

# Original String:Geeks
user1 = Mystring("Geeks")
print("Original String:", user1.data)

# String After Appending:Geekss
user1.append("s")
print("String After Appending:", user1.data)

# String after Removing:Gkss
s1.remove("e")
print("String after Removing:", s1.data)