ソートされたベクトルに要素を挿入し、要素をソートしたままにする

Question

ベクトルがあるので、要素を常にソートする必要があります。そのベクトルに要素を挿入し、それらをポップするときに要素をソートしておく方法についてはどうすればよいですか。私はstd::lower_boundを調べましたが、それは私が望んでいたものの反対を与えました。

たとえば、これは私が望むものです：ベクトルのすべての要素をポップすると、それは次のようになります： 1 2 3 4 5.これは、ベクトルが5 4 3 2 1としてそれらを保存しなければならないことを意味します。下限の場合、ベクトルはそれらを1 2 3 4 5として格納し、5 4 3 2 1としてポップされます。また、compare functorが渡され、lower_bound関数がcompare functorを使用します。比較ファンクタの反対側を取る方法はありますか？

Answer 1

ベクトルを常にソートするには、新しい要素を常に適切な位置に挿入する必要があります。昇順に要素をポップし、vectorはpop_back（）メソッドのみを提供するので、降順で要素をソートする必要があります。その最初のあなたは適切な位置を検索し、そこに挿入する必要があります：ところで

typedef std::vector<int> ints; 

void insert(ints &cont, int value) { 
    ints::iterator it = std::lower_bound(cont.begin(), cont.end(), value, std::greater<int>()); // find proper position in descending order 
    cont.insert(it, value); // insert before iterator it 
}