ベクトルに順番に追加された場合、ベクトル<int>をソートする必要はありますか？

Question

既にソートされているファイルから順にアイテムを読み込んだ場合、ベクターをソートする必要はありますか？それが不必要な場合は、パフォーマンスの低下を招きたくはありません。参考までに、これは私がそれを構築するために使用していて、それが読み込まれていて、各項目を順番には何かということです。

@dribeas'はコメント

std::vector<int> split(const std::string &s, char delim) { 
    std::vector<int> elems; 
    std::stringstream ss(s); 
    std::string item; 
    while(std::getline(ss, item, delim)) { 
     elems.push_back(static_cast<int>(atoi(item.c_str()))); 
    } 
    return elems; 
} 

Answer 1

ありません後に編集、あなたベクトルをソートする必要はありません。 push_backは、という要素を明示的に末尾にと追加します。

あなたのAPIはelemsを取り込み、それを（参考として）返すことに注意してください。ベクターに既に含まれているコンテンツはどうなりますか？あなたが始めたとき、ベクターが空だった（それがあなたの元のサンプルコードからはっきりしていない）との項目がありません、あなたが望む順序で添加したpush_backはに上の項目をプッシュするので、あなたは、ソートする必要はありません提供

Answer 2

ベクトルのバック（終了）：

は現在の最後の要素の後に、ベクトルの最後に新しい要素を追加します。

---

あなたの編集後、空でないと起動することリストの可能性が今なくなっています。このセクションは、それが可能性のある元の質問を表しています。

最初にベクターが空でない場合は、新しいものを順番に追加しても、そこにあるものが順不同である可能性があります。

あなたはそれをソートしていますことを確認、しかし絶対に必要な場合を除き、あなたは添加後の後工程として、何かのようにそれを行うことができますソートを回避したい場合：

は

std::vector<int> &split (const std::string &s, char sep, std::vector<int> &vec) 
{ 
    std::stringstream ss (s); 
    std::string item; 
    while (std::getline (ss, item, sep)) 
     vec.push_back (static_cast<int> (atoi (item.c_str()))); 

    bool sorted = true; 
    for (int i = vec.size() - 1; (i > 0) && sorted; i--) 
     sorted = (vec[i] >= vec[i-1]); 
    if (!sorted) { 
     // Sort it here. 
    } 

    return vec; 
} 

これは、比較的高速スキャンになりますそれらがソートされているかどうかを確認するための要素（そして最初にの順序が間違っているグループが見つかるまで）。

ソートされていない場合は、お気に入りのソートアルゴリズム（バッテリーは含まれません）でソートされます。

---

しかし、それはまだデータが希望の順序で到着しない場合があることを前提とするために最善のことことがあります。あなたはまだのようなもので、唯一のソート必要なときに同様の方法を使用することができます。その場合は

std::vector<int> split (const std::string &s, char delim) { 
    std::vector<int> elems; 
    std::stringstream ss (s); 
    std::string item; 
    int lastOne = std::numeric_limits<int>::min(); 
    bool isSorted = true; 

    while (std::getline(ss, item, delim)) { 
     int thisOne = atoi (item.c_str()); 
     if (thisOne < lastOne) isSorted = false; 
     elems.push_back (static_cast<int> (thisOne)); 
     lastOne = thisOne; 
    } 

    if (!isSorted) { 
     // Sort it here. 
    } 

    return elems; 
} 

は、各要素は、それが少なくとも同じ大きだ確実にするために、最後の1に対してチェックされます。そうでなければ、ベクトルはソートのためにフラグが付けられます。

これで、チェックに要するコストは最小限に抑えられますが、ルールに従わないデータを処理することができます。

Answer 3

std::vectorにアイテムを押し込む順序を保持するかどうかを尋ねる場合は、「はい」を選択します。それは契約の大部分です。