序列容器-列表
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
更多推荐
python与C++容器对比学习(一)list与vector
发布评论