は、どのように私はSTDに挿入::より効率的に

Question

をマッピング私は、このようなコードを持っている：

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に提案を渡すことができますが、良い例は見つかりませんでした。

Answer 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 
    } 
} 

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