C++のコンテナの要素のランク（位置インデックス+ 1）をvectorまたはlistのように取得する必要があります。そうする便利な方法はありますか？私はランクを見つけるためにnth_elementに基づいてテストを行った可能性があります。または、私は並べ替え、ランクを見つけるためにバイナリ検索を行うことができます。しかし、これらのすべては、最悪の場合、非常に効率的ではないように見えます。私はO（lgn）の複雑さを得たいと思っており、可能であればSTLアルゴリズムを使っています。C++でベクトルの要素のランクを取得する方法
リニア検索よりも効率的な方法が見つかる可能性は非常に低いようです。最悪の場合は必然的に、すべての要素を検索対象と比較する必要があります。これがまさに線形検索によって得られるものです。
コンテナにランダムアクセスイテレータ（ベクターなど）があり、ソートされている場合は、std::lower_bound()アルゴリズムを使用して、O（log n）の複雑さで要素インデックスを取得できます。たとえば：
std::vector<int> v({10,20,30,30,20,10,10,20});
std::sort(v.begin(), v.end());
auto iter = std::lower_bound(v.begin(), v.end(), 20);
std::cout << "index " << int(iter - v.begin()) << std::endl;
は（私はコードを短くするためにC++ 11の構文を使用していますが、あなたのアイデアを得る必要があります）。
要素をソートされた方法でベクトルに挿入できるため、インデックスを検索する前にソートする必要はありません。
すでにベクトルにデータがあり、イテレータを使用している場合は、イテレータをベクトルの先頭（または最後）から減算して、その位置を取得する必要がありますソートされます - ランクです。
vector<int> myvector;
vector<int>::iterator it;
for (it=myvector.begin() ; something ; something)
*it++; //
int rank = it - myvector.begin();
すでにイテレータがある場合、ソートは関係ありません。とにかく、OPにはコンテナ内の要素に対するハンドルが一切ないことは明らかです。 –
これは不安定かもしれません。
ベクトルの要素がメモリ内で連続しているという事実を利用できます。
はそうあなたがしなければならないものを
1））興味
2の要素のイテレータアドレスを取得し、総メモリ
3を得るために）（vector.beginと減算です）1つの要素のサイズで割ります
これはあなたに位置（またはランク）を与えるはずです。
これは要素が固定サイズであると仮定しています。
コンテナをスキャンするよりも使いたい場合は、間違ったコンテナを選んだとします。少なくとも、すべてのコンテナタイプに最適な_catch-all_アプローチはありません。 –
えええええええええええええええええええええええええええええええええええええええええええええええええだしんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんだんじょうだんかんじゅうかんじゅんあなたは、それぞれのアイテムを潜在的に見ることなく、ベクターのようなコレクションでこれを達成することができるとはどのように考えていますか？これは実際にパフォーマンスの問題ですか？私はあなたがそれが証明されていれば、その仕事に間違ったデータ構造を使用しているとの結論に至りました。 –
@EdS .: "Q：方法は何ですか？" "A：方法を使用してください。"うーん。 –