17

このコードは 0.012 秒間実行されました。

 std::list<int> list;
 list.resize(100);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

これは 9.378 秒間:

 std::list<int> list;
 list.resize(100000);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

私の意見では、そのような方法で std::list を実装することは可能であり、そのサイズはプライベート変数に格納されますが、これによれば、サイズを呼び出すたびに再度計算されます。誰でも理由を説明できますか？

4

2 に答える 2

16

size()定数時間と定数時間の間に競合がありlist.spliceます。委員会は賛成することを選択したsplice。

2 つのリスト間でノードをスプライスする場合、2 つのリストのサイズを更新するために、移動したノードをカウントする必要があります。いくつかの内部ポインターを変更するだけで、ノードをスプライシングする利点の多くが失われます。

コメントに記載されているように、C++11 は O(1) をいくつかのまれな (?) 使用のために放棄することでこれを変更しましたsplice:

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);

複雑さ: 定数時間 if &x == this; それ以外の場合は線形時間。

于 2012-10-31T11:47:31.620 に答える
9

、ISO/IEC 14882:2011§C.2.12、条項 23:「コンテナ ライブラリ」:

変更: size() メンバー関数の複雑さが一定になりました

理由: size() の複雑さの仕様の欠如により、一貫性のないパフォーマンス特性を持つ分岐実装が発生しました。

元の機能への影響: C++ 2003 に準拠する一部のコンテナー実装は、この国際標準で指定されている size() 要件に準拠していない場合があります。std::list などのコンテナーをより厳しい要件に合わせて調整するには、互換性のない変更が必要になる場合があります。

コメントについて:

23.3.5.5 - 「リスト操作」、再びISO/IEC 14882:2011:

list は、あるリストから別のリストに要素を破壊的に移動する 3 つのスプライス操作を提供します。get_allocator() != x.get_allocator() の場合、スプライス操作の動作は未定義です。

void splice(const_iterator position, list& x);
void splice(const_iterator position, list&& x);
必須: &x != this.
効果: x の内容を position の前に挿入し、x を空にします。x の移動された要素へのポインターと参照は、同じ要素を参照するようになりましたが、*this のメンバーとして参照されます。移動された要素を参照するイテレータは引き続きそれらの要素を参照しますが、x ではなく *this へのイテレータとして動作するようになりました。
複雑さ: 一定時間。

void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list&& x, const_iterator i);
効果: リスト x の i が指す要素を位置の前に挿入し、その要素を x から削除します。position == i または position == ++i の場合、結果は変更されません。*i へのポインターと参照は、引き続きこの同じ要素を参照しますが、*this のメンバーとして参照します。*i への反復子 (i 自体を含む) は引き続き同じ要素を参照しますが、x ではなく *this への反復子として動作するようになりました。
Requires : i は x の有効な逆参照可能な反復子です。
複雑さ: 一定時間。

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);
効果: [first,last) の範囲内の要素を位置の前に挿入し、要素を x から削除します。 必須: [first, last) は x の有効な範囲です。position が範囲 [first,last) の反復子である場合、結果は未定義です。x の移動された要素へのポインターと参照は、同じ要素を参照するようになりましたが、*this のメンバーとして参照されます。移動された要素を参照するイテレータは引き続きそれらの要素を参照しますが、x ではなく *this へのイテレータとして動作するようになりました。
複雑さ: &x == this; の場合は一定時間。それ以外の場合は線形時間。

于 2012-10-31T11:57:25.360 に答える