1

C++\STL テスト用紙の 1 つにそのような質問があることに気付きました。

何か案は？

おそらく、コレクション内の要素を削除すると、ベクトル内の「すべて削除された後」のイテレータとセット内の削除されたイテレータのみが無効になるという事実と関係がありますか?

4

2 に答える 2

4

この違いは、イテレータ自体よりもコンテナの性質の違いに大きく関係しています。

1 つの側面は、これらのコンテナーの「並べ替え済み/並べ替えなし」の性質に関連しています。並べ替え済みコンテナー内にある要素は、順序が崩れるため、変更できません。

別の側面は、「コンパクト/拡張」格納メカニズムに関連しています。ベクトルの要素は単一の割り当てブロックにまとめて格納され、セット (またはリスト) の要素は個別に格納されます。その結果、ベクトルの挿入/削除により、要素の変位が変化します。セットまたはリストでの挿入/削除は再リンクを引き起こし、既存のすべての要素がその場所を保持します (したがって、それらを参照する反復子を無効にしません)

ストレージに常に関連するもう 1 つの側面は、vector::iterator が「ランダム アクセス」であることです。変位は算術的に計算できるため、++i、i+=3、i+=100 には同じ時間がかかります。セット (および「リンクされたコンテナー」) では、反復子は単に「双方向」です。++i と --i は即時計算ですが、i+=5 または i+=100 はまったく異なる時間がかかります (少なくとも線形ループが必要です)。

于 2013-01-11T10:11:27.163 に答える
3

set::iteratora が参照するオブジェクトは です。これconstは、 a のエントリの値をset順序どおりに変更することは許可されていないためです (値を変更すると、順序が崩れる可能性があります)。の場合はそうではありませんvector::iterator。

例えば：

#include <vector>
#include <set>

int main()
{
    std::set<int> s;
    std::vector<int> v;

    *v.begin() = 4;
    *s.begin() = 4; // Line 10.
    return 0;
}

MSVC++ コンパイラは次を出力します。

main.cpp(10): エラー C3892: 'std::_Tree<_Traits>::begin': const である変数に割り当てることはできません

g++ コンパイラは以下を出力します:

エラー: 読み取り専用の場所の割り当て 's.std::set<_Key, _Compare, _Alloc>::begin with _Key = int, _Compare = std::less, _Alloc = std::allocator.std::_Rb_tree_const_iterator<_Tp >::operator* with _Tp = int'</p>

于 2013-01-11T09:52:25.247 に答える