search

majintao0131 / yaml-cpp

Automatically exported from code.google.com/p/yaml-cpp
MIT License
0 stars 0 forks source link

Maps should use a secondary hashmap just for string keys for performance #178

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
So if you look up a string key, it has O(1) performance instead of O(n).

Original issue reported on code.google.com by jbe...@gmail.com on 28 Nov 2012 at 12:19

GoogleCodeExporter commented 9 years ago 
Isn't lookup in a map O(log n)?

Original comment by oster.t...@gmail.com on 29 Jan 2013 at 7:05

GoogleCodeExporter commented 9 years ago 
Right now it's O(n).

Original comment by jbe...@gmail.com on 29 Jan 2013 at 9:09

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
Just to clarify, the issue is that yaml-cpp linearly searches through the keys 
ATM, hence the O(N), std::map is indeed O(log n) though.

Original comment by domuradi...@gmail.com on 30 Jan 2013 at 2:27

GoogleCodeExporter commented 9 years ago 
Yes; but the plan isn't to use std::map, but a hashmap, which is O(1).

Original comment by jbe...@gmail.com on 30 Jan 2013 at 3:22

GoogleCodeExporter commented 9 years ago 
std::unordered_map is O(1) to O(n), this probably depends on reallocations and 
other memory things. std::map is O(log n). Since YAML stores the entire file in 
Nodes now it makes sense to organize it into a map and vector setup for maps 
and sequences.

If this is changed to do that, please allow access to the maps and vectors.

Original comment by ARandomFurry on 2 Feb 2014 at 2:05

GoogleCodeExporter commented 9 years ago 
This issue has moved to github: https://github.com/jbeder/yaml-cpp/issues/178

Original comment by jbe...@gmail.com on 30 Mar 2015 at 1:33