C++ std::vector 是如何实现的?
我一直在使用 std::vector，最近我问自己这个问题:std::vector 是如何实现的?"
I have been using std::vector a lot, and recently I asked myself this question: "How is std::vector implemented?"
我有两个选择:
1) 链表，然后让 API 感觉像是随机访问(即重载 operator[]).
1) Linked list, and then making the API feel like random access (i.e. overloading operator[]).
2) 使用 new，例如Foo* temp = new Foo[20]:我相信他们会做这样的事情，但随后又提出了一个问题.他们是否总是分配最大 (uint32_t) 存储空间来提供随机访问?(这在内存方面是低效的.)
2) Using new, e.g. Foo* temp = new Foo[20]: I believe they do something like this, but then it raises one more question. Do they always allocate a maximum (uint32_t) storage to give random access? (This is inefficient in terms of memory.)
或者还有什么我应该注意的吗?
Or is there something else that I should be aware of?
推荐答案
它是通过使用底层数组实现的.
It's implemented by using an underlying array.
不可能实现 std::vector 使用链表，因为标准保证列表中的元素将保存在连续内存中.
It's not possible to implement a std::vector<T> with a linked list because the standard guarantees the elements in the list will be held in contiguous memory.
相关文章