2016-06-27 8 views
0

をマッピング私は、このようなコードを持っている:は、どのように私はSTDに挿入::より効率的に

struct Record{ 
    std::string key; 
    // ... 
}; 

void push_record(Record &out, std::map<std::string, int> &vmap){ 
    const auto &it = vmap.find(out.key); 

    long pos; 

    if (it != vmap.end()){ 
     pos = it->second; 
    }else{ 
     pos = calculate_pos(out); 
     vmap.insert(Record(std::move(out.key), pos)); // here move 
    } 

    // use pos 
} 

がどのように私は、コードをより効率的にすることができますか?

現時点では、地図を2度参照するため、コードはあまり効率的ではありません。最初に値をチェックするときは最初に挿入し、2番目のときは挿入します。

std::move(out.key)も使用したいので、これはvmap[out.key]のようなものを使用しなかった理由です。

insertに提案を渡すことができますが、良い例は見つかりませんでした。

+1

'std :: map'の2つのルックアップのためにコードが遅いことは確かですか? 'std :: map'のルックアップは' O(log n) 'です。これは非常に大きなマップであってもかなり速くなければなりません。 – Holt

+1

ほとんどの*本当の点は2つのルックアップではなく、あなたが挿入する必要があることを知っていない限り 'calculate_pos'呼び出しを避けるためです。そして関連しているのは、もしあなたの牛肉が本当にあなたの肉牛であるならば、注文が重要ではない(あなたは一方的にも別の方法も指定していない)場合、おそらく 'unordered_map'がもっと適しているでしょう。 – WhozCraig

+1

実際にコードをコンパイルしていますか? 'vmap'は' std :: string、int'型ですが、 'Record'型のインスタンスを挿入します。 – marcinj

答えて

1

std::mapはあなたの現在の要素よりも大きい最初の要素を見つけるために使用できる方法upper_boundあります。マップは重複キーを含めることはできませんので

const auto it = vmap.upper_bound(out.key); 

を、そしてこれは最初の要素であります大きい、与えられたキーと値が唯一で、すべてのマップに以前のイテレータの位置にあること、またはことができませんでした:

他の人が言ったように
// Begin iterator means it definitely isn't in map 
if(vmap.empty() || it == vmap.begin()) { 
    // Perform insert... 
} else { 
    if((--it)->first != out.key)) { 
     // Doesn't exist, perform insert with hint. 
     // Note it will be inserted just prior to this (C++11). 
     vmap.insert(++it, ...); 
    } else { 
     // It's in the map, do stuff with it 
    } 
} 

が、これは可能性があります最高でマイクロ最適化。これはまたコードを醜くて読みにくくするので、私は真剣にこのようなものを使う前にプロファイリングを提案します。

+0

興味深いですが、私は同様のアルゴリズム(明らかに少し異なります)に 'lower_bound'を使用しています。 – WhozCraig

+0

ここで、過度のデクリメントとインクリメントのない 'std :: map :: lower_bound'があります。この場合、条件チェックが異なる場合があります。 – ilotXXI

関連する問題