本文整理几种基本容器：列表、元组、字典和集合的用法和collections中几种已经预先实现的容器数据结构：namedtuple(),双向链表deque，ChainMap，Counter，OrderedDict，defaultdict。其中，deque是一个双向链表的结构，namedtuple是tuple的拓展，ChainMap，Counter,OrderedDict,defaultdict都可以视作是字典的拓展。

1. 基本顺序存储结构——列表与元组

Python中的基本顺序存储结构是列表与元组，在操作的复杂度上和数组完全相同，其中列表是可变数据类型，元组是不可变数据类型。这里先介绍一下两种数据结构共有的方法：

 

这些都不涉及对数组内元素的更改，因此是列表和元组都可以使用的。注意元组只能使用以上的方法。

接下来介绍可变有序容器的方法，注意各种方法都有利用切片赋值的实现！

此外，列表还独有s.sort(key=None, reverse=None)，其中key是一个函数名，也就是比较函数，reverse为布尔值，True的话则会列表反向。

Sort单独列出来是因为如果自己从可变有序容器里面派生的话并没有这个方法。

1. 基本哈希存储结构——字典

字典是基于哈希表的一种映射结构，注意本文中介绍的Python的数据结构并没有任何一种使用了红黑树的搜索结构。

1. 键值相等的字典——集合set与frozenset

Python中由set和frozenset两种集合结构。由于set中的元素既是键又是值，所以他的内容必须是不可修改的，frozenset就是被声明为常量的set，，用于建立集合的集合

首先介绍两种集合共有的方法：

注意用的都是逻辑运算符进行衍生而不是+

 

而set独有的方法是，一个是诸如&=之类的运算符，还有：

 

1. Tuple的拓展的生成器collections.namedtuple(typename, field_names, verbose=False, rename=False)

这是一个生成器，本身并不是类。它生成的就是有名字的元组类型，很适合于存储表条目，例如下面的代码：

Point = namedtuple('Point', ['x', 'y'])

这样做，Point会定义一个具有x和y成员的类，想要调用相应对象的x属性，既可以使用p[0],也可以使用p.x。注意虽然叫namedtuple，但是其本身是可以更改的，可以视作是一种简单的结构体的定义方式。可以使用p=Point(1,2)进行定义

如果verbose为真，那么会将定义过程显示的输出到控制台；如果rename为真，属性中不符合命名规则的属性会被自动更名为'_index'，如一些保留字或者数字开头。

利用这种有名字的生成器，可以使程序更加简洁，并且更加易读，用它作为value再来建字典就非常的方便了。

有几个内建方法，比如：

_make(iterable):使用一个可迭代的对象建立namedtuple，例如列表。

_asdict():转化为一个字典（Py3.1后为OrderedDict）

利用字符串格式的属性名找出值getattr(p,'x');

dict转化为Tuple要利用Unpacking语法 **args，即Point(**somedict),**语法会把dict切分开，注意此语法只发生在参数传递过程中才是有效的。

一个*是把容器中的元素一个一个传递，两个*是专门用于解包字典，键值对应使用。

还有内置属性可以以字符串的形式输出参数的名字 ._fields

1. 字典组ChainMap

定义时候，后边按元组的形式接受参数ChainMap(*map)，每一个参数都应该是一个字典名，最后返回一个字典组。

建立之后，其中有maps属性，是所有的字典组成的列表；parents属性，是除了第一个字典之外的所有字典的列表。

内建的new_child(m=None)方法，是添加一个新的字典到列表中作为第一个字典，等价于ChainMap(m,*d.maps).

字典组拥有字典的各种操作，它的特点是所有涉及到更新的操作如插入删除等都是只针对第一个字典，而查找的操作则是按照顺序对全部字典进行查找。如果希望更新操作也是对全部字典，则可以使用它进行派生，并且对maps使用for循环。

1. 计数器Counter（本质是C++multiset、sql bag）

可以认为他是一个key-int字典，不过他实际上是一个multiset！，int默认为0，有几个创建方法：

从一般可迭代对象c = Counter('gallahad')，从字典c = Counter({'red': 4, 'blue': 2})，直接指明（字典也可以这样初始化，是底层方法）c = Counter(cats=4, dogs=8) 。

它具有字典的全部操作，同时又添加了一下计数器的很自然的操作。

.elements():列表形式一个一个列出元素。

.most_common([n]):列出出现次数最多的前n个元素的列表，如果n没有，则按顺序列出所有的。

.subtrackc(other):两个计数器相减，可以出现0或负数。可以用+c 这一语句清除0和负数

四种运算：+,-,&,|，按key的加减，按multiset取交和并，注意出现的负数和0会被清楚

1. 特殊字典OrderedDict和defaultdict

这两个都具有普通字典的全部功能，不过有一些不同：

1. defaultdict(class)

指定了值的类型，会用这种类型自动构造，相当于可以提前使用这种类的方法，一个有趣的例子是：

>>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]

>>> d = defaultdict(set)

>>> for k, v in s:

...     d[k].add(v)

...

>>> sorted(d.items())

[('blue', {2, 4}), ('red', {1, 3})]

1. class collections.OrderedDict([items])

这种容器不光存储了键值对，还维护了被加入字典的顺序，使它能够像栈一样弹出，增加了两个方法：

.popitem(last = True):    移除最后一个加入的键值对，如果last=false则移除第一个加入的键值对。

.move_to_end(key,last = True):    将某一个键的条目作为最后一个加入的（false->作为最先加入的）

这个数据类型可以简单地实现LRU的算法，可以通过一个key:(value,forekey,nextkey)的字典结构实现此类。

1. 双向链表deque

class collections.deque([iterable[, maxlen]])

就是简单意义上的双向链表（双向队列），注意这里不再支持切片操作了，随机访问的操作保留，可以通过随机访问通过del实现删除，但是没有切片无法用于替换，截取等操作，无法sort：

注意其没有截取，切片等操作，只能通过copy，pop的方式实现截取操作。