0

この多肢選択式の質問で、最終的な回答 (e の選択) が false である理由について、私は混乱しています。

Which of the following statements is the most accurate regarding linked lists?

a. Linked-lists take up more space than STL vectors because they allocate extra storage 
space for future growth.
b. The asymptotic complexity of inserting at the end of a doubly-linked list container 
storing only the pointer to the first element is O(1).
c. A loop in a singly-linked-list can be found in O(log(n)) time and O(n) memory overhead
d. A loop in a singly-linked-list can be found in O(n) time and O(1) memory overhead.
e. The number of elements in a linked-list is end_ptr -start_ptr + 1, where start_ptr points
to the first element in the linked list and end_ptr points to the last item of the linked-list.

つまり、両方がd でないのはなぜですか。そしてe。正しい？イテレータが でサイズを返すのはend_ptr-start_ptr+1どのような場合で、そうでないのはどのような場合でしょうか? end_ptr-start_ptr選択は代わりに述べるべきでしたか？

4

2 に答える 2

4

リンクされたリストは、連続しているとは限りません (実際には、少なくとも実際のシナリオではそうではありません)。

これは、それらのイテレータを減算することは一定時間の操作ではないことを意味します (そうなる可能性はありますが、望ましくないトレードオフがないわけではありません)。

通常、一定時間の操作でない限り、マイナス演算子とプラス演算子は反復子で定義されません。

また、それらを減算できたとしても、反復子は最後の要素ではなく、最後の要素の 1 つ後ろを指します。これは、length = end - begin. プラスワンはいらない。

たとえば、次の場合std::vector:

size_t len = v.end() - v.begin();

（通常はそのまま使用しますがv.size()。）

于 2013-02-28T02:05:16.000 に答える
1

ベクトルとは異なり、リスト内のアイテムは連続した場所に保存されません。したがって、リストの最後をマークするには、リンクされた list.end() を null にする必要があります。そのため、リストのサイズを算術で取得することはできません。また、末尾は、最後の有効な要素の 1 つ後ろの無効なアイテムを指しています。

于 2013-02-28T02:05:27.650 に答える