c++ - C++ 中的双向链表、链表和动态数组

Question

我是 C++ 的新手，这些问题可能非常简单和基础 [很抱歉!]。这里我有两个基本问题:

1. 据我了解，C++ 中的 vector 是动态数组。他们可以通过将后/前元素插入其中来改变大小。

   我的问题是: vector 是动态分配的还是“动态数组”名称只是因为改变大小的能力而被调用？动态分配数组和动态数组让我完全迷茫!

2. STL 列表是 C++ 中的链表(同样，据我所知)。这些是双向链表还是单向链表？

谢谢，

Answer 1

vector 是动态分配的，正如您在提到的 documentation 中看到的那样.您可以在 push_back 函数中更清楚地看到这一点:

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

此外，请牢记这一点，它的复杂性是摊销常数(例如，您可以看到 this )。

有关更多信息(在评论中提及)，您可以在 forward_list 中找到真实列表:

It is implemented as a singly-linked list and essentially does not have any overhead compared to its implementation in C. Compared to std::list this container provides more space efficient storage when bidirectional iteration is not needed.

此外，如 documentation 中所述, 列表被实现为双向链表。

List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.