[lmi-commits] [lmi] odd/any_member-opt a6e80e5 3/5: Use a sorted vector instead of std::map<> in MemberSymbolTable [292]

[Greg Chicares]

branch: odd/any_member-opt
commit a6e80e5ef93ffefa4e4f21c0c66c2e960312a369
Author: Vadim Zeitlin <vadim@tt-solutions.com>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Use a sorted vector instead of std::map<> in MemberSymbolTable [292]
    
    This is slightly faster than using a map and, more importantly, provides
    scope for the upcoming optimizations.
---
 any_member.hpp | 29 +++++++++++++----------------
 1 file changed, 13 insertions(+), 16 deletions(-)

diff --git a/any_member.hpp b/any_member.hpp
index 94c0951..cdca2c9 100644
--- a/any_member.hpp
+++ b/any_member.hpp
@@ -543,9 +543,6 @@ MemberType const* member_cast(any_member<ClassType> const& 
member)
 template<typename ClassType>
 class MemberSymbolTable
 {
-    typedef std::map<std::string, any_member<ClassType>> member_map_type;
-    typedef typename member_map_type::value_type member_pair_type;
-
   public:
     virtual ~MemberSymbolTable();
 
@@ -569,7 +566,7 @@ class MemberSymbolTable
     [[noreturn]]
     void complain_that_no_such_member_is_ascribed(std::string const&) const;
 
-    member_map_type map_;
+    std::vector<any_member<ClassType>> member_values_;
     std::vector<std::string> member_names_;
 };
 
@@ -606,12 +603,12 @@ any_member<ClassType>& 
MemberSymbolTable<ClassType>::operator[]
     (std::string const& s
     )
 {
-    auto i = map_.find(s);
-    if(map_.end() == i)
+    auto const i = std::lower_bound(member_names_.begin(), 
member_names_.end(), s);
+    if(i == member_names_.end() || (*i != s))
         {
         complain_that_no_such_member_is_ascribed(s);
         }
-    return i->second;
+    return member_values_[i - member_names_.begin()];
 }
 
 template<typename ClassType>
@@ -619,12 +616,7 @@ any_member<ClassType> const& 
MemberSymbolTable<ClassType>::operator[]
     (std::string const& s
     ) const
 {
-    auto const i = map_.find(s);
-    if(map_.end() == i)
-        {
-        complain_that_no_such_member_is_ascribed(s);
-        }
-    return i->second;
+    return (const_cast<MemberSymbolTable<ClassType>&>(*this))[s];
 }
 
 template<typename ClassType>
@@ -649,10 +641,15 @@ void MemberSymbolTable<ClassType>::ascribe
             >::value
         );
 
+    auto const i = std::lower_bound(member_names_.begin(), 
member_names_.end(), s);
+
     ClassType* class_object = static_cast<ClassType*>(this);
-    map_.insert(member_pair_type(s, any_member<ClassType>(class_object, p2m)));
-    // TODO ?? This would appear to be O(N^2).
-    auto i = std::lower_bound(member_names_.begin(), member_names_.end(), s);
+
+    auto const index = i - member_names_.begin();
+    member_values_.emplace(member_values_.begin() + index, class_object, p2m);
+
+    // Notice that insert() may invalidate the iterator, so it can only be done
+    // after using "i" for computing the index into member_values_ above.
     member_names_.insert(i, s);
 }