std :: map插入或std :: map查找？

Question

假设您想要保存现有条目的地图。 20％的时间，您插入的条目是新数据。使用返回的迭代器执行std :: map :: find然后std :: map :: insert是否有优势？或者，尝试插入然后根据迭代器是否指示记录已插入或未插入而动作更快？

Answer 1

答案是你没做。相反，你想Scott Meyers做点什么通过项目的Effective STL 24提示：

typedef map<int, int> MapType; // Your map type may vary, just change the typedef 

MapType mymap; 
// Add elements to map here 
int k = 4; // assume we're searching for keys equal to 4 
int v = 0; // assume we want the value 0 associated with the key of 4 

MapType::iterator lb = mymap.lower_bound(k); 

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first))) 
{ 
    // key already exists 
    // update lb->second if you care to 
} 
else 
{ 
    // the key does not exist in the map 
    // add it to the map 
    mymap.insert(lb, MapType::value_type(k, v)); // Use lb as a hint to insert, 
                // so it can avoid another lookup 
} 

Answer 2

2之间的速度几乎没有任何区别，find将返回一个迭代器，insert会执行相同的操作，并且无论如何将搜索映射以确定条目是否已经存在。

所以......它归结为个人喜好。我总是尝试插入，然后根据需要进行更新，但有些人不喜欢处理返回的对。

Answer 3

map [key] - 让stl把它整理出来。这是最有效地传达你的意图。

是的，够公平的。

如果您执行查找，然后执行插入操作，则在执行2 x O（log N）时会发生错误，因为查找只会让您知道是否需要插入插入的位置（lower_bound可能帮助你）。只是一个直接插入，然后检查结果是我会走的方式。

Answer 4

任何有关效率的答案将取决于您的STL的确切实施。唯一可以确定的方法是通过两种方式进行基准测试。我猜猜这种差异不太可能是重要的，所以根据你喜欢的风格来决定。

Answer 5

我想如果你做了一个查找然后插入，额外的成本将是当你没有找到钥匙和执行后插入。这就像是按照字母顺序浏览书籍，而不是找到书本，然后再次查看书籍以查看插入它的位置。它归结为你将如何处理钥匙，如果他们不断变化。现在有一些灵活性，如果你没有找到它，你可以登录，例外，做任何你想要的...

Answer 6

如果你关心效率，你可能想检查出hash_map<>。

典型地图<>被实现为二叉树。根据您的需要，hash_map可能更有效。

Answer 7

的这个问题的答案也取决于它是多么昂贵的创建你在地图存储值类型：

typedef std::map <int, int> MapOfInts; 
typedef std::pair <MapOfInts::iterator, bool> IResult; 

void foo (MapOfInts & m, int k, int v) { 
    IResult ir = m.insert (std::make_pair (k, v)); 
    if (ir.second) { 
    // insertion took place (ie. new entry) 
    } 
    else if (replaceEntry (ir.first->first)) { 
    ir.second->second = v; 
    } 
} 

对于值类型如int，上面会更有效率比查找后跟插入（在没有编译器优化的情况下）。如上所述，这是因为通过地图的搜索只发生一次。

然而，插入电话要求你已经有了新的“价值”建设：

class LargeDataType { /* ... */ }; 
typedef std::map <int, LargeDataType> MapOfLargeDataType; 
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult; 

void foo (MapOfLargeDataType & m, int k) { 

    // This call is more expensive than a find through the map: 
    LargeDataType const & v = VeryExpensiveCall (/* ... */); 

    IResult ir = m.insert (std::make_pair (k, v)); 
    if (ir.second) { 
    // insertion took place (ie. new entry) 
    } 
    else if (replaceEntry (ir.first->first)) { 
    ir.second->second = v; 
    } 
} 

为了调用“插入”我们正在付出的昂贵的调用来构建我们的价值型 - 和从你在问题中所说的话你不会在20％的时间内使用这个新值。在上述情况下，如果更改映射值类型不是一个选项，那么首先执行“查找”以检查是否需要构造该元素会更有效。

或者，可以更改地图的值类型，以使用您最喜欢的智能指针类型将句柄存储到数据中。插入调用使用空指针（构造非常便宜），并且只有在必要时才是构造的新数据类型。

Answer 8

我失去最多的回答。

查找回报map.end（），如果它没有找到任何这意味着如果你有够慢的

map.insert 

任何元素不增加新的东西，然后

iter = map.find(); 
if (iter == map.end()) { 
    map.insert(..) or map[key] = value 
} else { 
    // do nothing. You said you did not want to effect existing stuff. 
} 

两次已经在地图中，因为它将不得不搜索两次。一旦看到它是否在那里，再次找到放置新事物的地方。

Answer 9

我似乎没有足够的观点留下评论，但被选中的答案似乎很长时间对我有利 - 当你认为insert会返回迭代器时，为什么要搜索lower_bound，何时可以使用迭代器返回。奇怪。