序列容器-列表

python list

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

# PyObject_VAR_HEAD: 变长对象的公共头部信息
# ob_item：一个二级指针，指向一个PyObject *类型的指针数组，这个指针数组保存的便是对象的指针，而操作底层数组都是通过ob_item来进行操作的。
# allocated：容量, 我们知道列表底层是使用了C的数组, 而底层数组的长度就是列表的容量

注意在python中万物皆对象，所以list的结构可以理解为：

list-> PyObject *底层数组[]-> PyObject

python list支持自动扩容和缩容

扩容规则：

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{   //参数self就是列表啦，newsize指的元素在添加之后的ob_size
    //比如列表的ob_size是5，那么在append的时候发现容量不够，所以会扩容，那么这里的newsize就是6
    //如果是extend添加3个元素，那么这里的newsize就是8
    //当然list_resize这个函数不仅可以扩容，也可以缩容，假设列表原来有1000个元素，这个时候将列表清空了
    //那么容量肯定缩小，不然会浪费内存，如果清空了列表，那么这里的newsize显然就是0
    
    //items是一个二级指针，显然是用来指向指针数组的
    PyObject **items;
    //新的容量，以及对应的内存大小
    size_t new_allocated, num_allocated_bytes;
    //获取原来的容量
    Py_ssize_t allocated = self->allocated;
	
    //如果newsize达到了容量的一半，但还没有超过容量, 那么意味着newsize、或者新的ob_size和容量是匹配的，所以不会变化
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        //只需要将列表的ob_size设置为newsize即可
        Py_SIZE(self) = newsize;
        return 0;
    }

    //走到这里说明容量和ob_size不匹配了，所以要进行扩容或者缩容。
    //因此要申请新的底层数组，申请多少个?这里给出了公式,一会儿我们可以通过Python进行测试
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    //显然容量不可能无限大，是有范围的，当然这个范围基本上是达不到的
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }
	
    //如果newsize为0，那么容量也会变成0，假设将列表全部清空了，容量就会变成0
    if (newsize == 0)
        new_allocated = 0;
    
    //我们说数组中存放的都是PyObject *, 所以要计算内存
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    //申请相应大小的内存，将其指针交给items
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        //如果items是NULL, 代表申请失败
        PyErr_NoMemory();
        return -1;
    }
    //然后让ob_item = items, 也就是指向新的数组, 此时列表就发生了扩容或缩容
    self->ob_item = items;
    //将ob_size设置为newsize, 因为它维护列表内部元素的个数
    Py_SIZE(self) = newsize;
    //将原来的容量大小设置为新的容量大小
    self->allocated = new_allocated;
    return 0;
}

c++ vector

//_Alloc 表示内存分配器，此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

vector底层实现也是数组，在此基础上增加了自动扩容等功能

由于数组大小不可变的特性，所以每次扩容缩容都会弃用现有的内存空间，重新申请新的内存空间，所以其相关的指针、引用和迭代器可能会失效。

此外vector初始化时指定了存储元素类型，其数组中保存的就是存储元素本身（python list中是指针）

扩容与缩容逻辑：

根据扩容因子加逻辑优化，扩容因子一般是1.5或2.0，根据实现不同决定。

如vs2013

    // grow by 50% or at least to _Count
	size_type _Grow_to(size_type _Count) const
	{
		size_type _Capacity = capacity();

		_Capacity = max_size() - _Capacity / 2 < _Capacity 
		? 0 : _Capacity + _Capacity / 2;	// try to grow by 50%
		
		if (_Capacity < _Count)
			_Capacity = _Count;
		
		return (_Capacity);
	}

容器操作

	python	c++
创建容器	list()	#include std::vector v;
添加元素	append()	push_back() / emplace_back()
插入元素	insert()	insert() / emplace()
删除元素	pop()	pop_back()(容量不变)
	pop(i)	erase(pos)(容量不变)
	remove() 删除第一个匹配到的元素	remove() 删除所有和指定元素相等的元素(容量不变)
	clear()	clear() 删除所有元素，(容量不变)
访问元素	list[i]	vector[i] / vector.at(i)
	list[0], list[-1]	front() / back()
		data()
	len()	size()
迭代器		c/r/cr begin()/end()
排序		sort()
	sort() sorted()	stable_sort() 原地排序

c++ vector去除多余容量的两种方式：

1. swap
vector<T>(x).swap(x);
vector<T>().swap(x);
2. c++11 shrink_to_fit()
x.shrink_to_fit();

python源码学习强烈推荐：https://github/zpoint/CPython-Internals