6

vector：のこの架空の実装を考えてみましょう。

template<class T>  // ignore the allocator
struct vector
{
    typedef T* iterator;
    typedef const T* const_iterator;

    template<class It>
    void insert(iterator where, It begin, It end)
    {
        ...
    }

    ...
}

問題

ここで直面する微妙な問題があります。同じベクトル内のアイテムを参照する可能
性があります。beginend where

たとえば、ユーザーが次のように言った場合：

vector<int> items;
for (int i = 0; i < 1000; i++)
    items.push_back(i);
items.insert(items.begin(), items.end() - 2, items.end() - 1);

Itがポインタタイプでない場合は、問題ありません。
しかし、私たちは知らないので、それが[begin, end)すでにベクトル内にある範囲を参照していないことを確認する必要があります。

しかし、これをどのように行うのでしょうか？C ++によると、同じ配列を参照していない場合、ポインターの比較は未定義になります。
そのため、コンパイラは、アイテムがエイリアスしないと誤って通知する可能性がありますが、実際にはエイリアスしているため、不要なO（n）の速度が低下します。

考えられる解決策と警告

1つの解決策は、ベクトル全体を毎回コピーし、新しいアイテムを含めてから、古いコピーを破棄することです。

ただし、上記の例のように、すでに十分な容量がある場合でも、1つのアイテムを挿入するためだけに1000のアイテムをコピーするシナリオでは、これは非常に低速です。

この問題を（正しく）効率的に解決する一般的な方法はありますか？つまり、エイリアシングが何もない場合にO（n）の速度低下に悩まされることはありませんか？

4

3 に答える 3

6

std::less生のポインタ比較がそうでない場合でも、全順序を与えることが保証されている述語などを使用できます。

標準から[comparisons]/8：

テンプレートgreater、less、greater_equal、less_equalの場合、組み込み演算子<、>、<=、> =が生成しない場合でも、任意のポインター型の特殊化により全順序が生成されます。

于 2012-08-20T03:31:57.113 に答える
0

しかし、どうやってこれを行うのでしょうか? C++ によると、それらが同じ配列を参照しない場合、ポインターの比較は未定義になります!

違う。ポインターの比較はunspecifiedであり、undefined ではありません。C++03 §5.9/2 [expr.rel] から:

[...] (ポインター変換後の) 同じ型のオブジェクトまたは関数へのポインターは、次のように定義された結果と比較できます。

[...] -
その他のポインター比較は指定されていません。

したがって、コストはかかるが正しいコピーを実行する前に、オーバーラップがあるかどうかをテストするのが安全です。

興味深いことに、C99 はこの点で C++ と異なり、関連のないオブジェクト間のポインター比較は未定義の動作です。C99 §6.5.8/5 から:

2 つのポインターを比較すると、結果は、指しているオブジェクトのアドレス空間内の相対位置によって異なります。[...] 他のすべての場合、動作は未定義です。

于 2012-08-20T03:43:33.513 に答える
0

実際、これは通常の iterator であっても当てはまります。誰もがやっていることを止めるものは何もありません

std::vector<int> v; 
// fill v 
v.insert(v.end() - 3, v.begin(), v.end());

それらがエイリアスであるかどうかを判断することは、イテレータの実装にとって問題です。

ただし、欠けているのは、あなたが実装であることです。移植可能なコードを使用する必要はありません。実装として、やりたいことは何でもできます。「まあ、私の実装では x86 に従っており、任意のポインターに使用しても問題<ありません」と言うことができ>ます。そして、それは問題ありません。

于 2012-08-20T03:57:43.353 に答える