>From 942dcd50e2b4fd4a12e405455f7c26ed71a869ce Mon Sep 17 00:00:00 2001
From: Vadim Zeitlin <address@hidden>
Date: Fri, 27 Feb 2015 14:46:52 +0100
Subject: [PATCH] Use a sorted vector instead of std::map<> in
 MemberSymbolTable.

This is slightly faster than using a map and, more importantly, provides scope
for the upcoming optimizations.
---
 any_member.hpp | 55 ++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 36 insertions(+), 19 deletions(-)

diff --git a/any_member.hpp b/any_member.hpp
index 70a9e18..8e5f4a6 100644
--- a/any_member.hpp
+++ b/any_member.hpp
@@ -536,8 +536,7 @@ template<typename ClassType>
 class MemberSymbolTable
     :private lmi::uncopyable<MemberSymbolTable<ClassType> >
 {
-    typedef std::map<std::string, any_member<ClassType> > member_map_type;
-    typedef typename member_map_type::value_type member_pair_type;
+    typedef std::vector<any_member<ClassType> > values_vector_type;
 
   public:
     virtual ~MemberSymbolTable();
@@ -561,12 +560,20 @@ class MemberSymbolTable
     template<typename ValueType, typename SameOrBaseClassType>
     void ascribe(std::string const& s, ValueType SameOrBaseClassType::* p2m)
         {
-        ClassType* class_object = static_cast<ClassType*>(this);
-        map_.insert
-            (member_pair_type(s, any_member<ClassType>(class_object, p2m))
-            );
         typedef std::vector<std::string>::iterator svi;
         svi i = std::lower_bound(member_names_.begin(), member_names_.end(), s);
+
+        ClassType* class_object = static_cast<ClassType*>(this);
+
+        member_values_.push_back(any_member<ClassType>(class_object, p2m));
+        typedef typename values_vector_type::size_type vvs_t;
+        vvs_t const first = i - member_names_.begin();
+        vvs_t const last = member_values_.size() - 1;
+        for(vvs_t n = last; n != first; --n)
+            {
+            swap(member_values_[n - 1], member_values_[n]);
+            }
+
         member_names_.insert(i, s);
         }
 #endif // defined __BORLANDC__
@@ -574,7 +581,7 @@ class MemberSymbolTable
   private:
     void complain_that_no_such_member_is_ascribed(std::string const&) const;
 
-    member_map_type map_;
+    values_vector_type member_values_;
     std::vector<std::string> member_names_;
 };
 
@@ -613,12 +620,13 @@ any_member<ClassType>& MemberSymbolTable<ClassType>::operator[]
     (std::string const& s
     )
 {
-    typename member_map_type::iterator i = map_.find(s);
-    if(map_.end() == i)
+    typedef std::vector<std::string>::iterator svi;
+    svi i = std::lower_bound(member_names_.begin(), member_names_.end(), s);
+    if(member_names_.end() == i || s != *i)
         {
         complain_that_no_such_member_is_ascribed(s);
         }
-    return i->second;
+    return member_values_[i - member_names_.begin()];
 }
 
 template<typename ClassType>
@@ -626,12 +634,7 @@ any_member<ClassType> const& MemberSymbolTable<ClassType>::operator[]
     (std::string const& s
     ) const
 {
-    typename member_map_type::const_iterator 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];
 }
 
 #if !defined __BORLANDC__
@@ -663,11 +666,25 @@ void MemberSymbolTable<ClassType>::ascribe
                 >::value
         ));
 
-    ClassType* class_object = static_cast<ClassType*>(this);
-    map_.insert(member_pair_type(s, any_member<ClassType>(class_object, p2m)));
     typedef std::vector<std::string>::iterator svi;
-    // TODO ?? This would appear to be O(N^2).
     svi i = std::lower_bound(member_names_.begin(), member_names_.end(), s);
+
+    ClassType* class_object = static_cast<ClassType*>(this);
+
+    // Using the usual insert() method relies on vector elements being
+    // assignable in C++98, but this is not the case for any_member<>, so we
+    // append the element at the end and then put it into the right place.
+    member_values_.push_back(any_member<ClassType>(class_object, p2m));
+    typedef typename values_vector_type::size_type vvs_t;
+    vvs_t const first = i - member_names_.begin();
+    vvs_t const last = member_values_.size() - 1;
+    for(vvs_t n = last; n != first; --n)
+        {
+        swap(member_values_[n - 1], member_values_[n]);
+        }
+
+    // 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);
 }
 #endif // !defined __BORLANDC__
-- 
2.1.0