Re: [boost] associative_vector: request for formal review

From: Mark Rodgers (mark.rodgers_at_[hidden])
Date: 2000-06-02 03:45:18

From: John E. Potter <jpotter_at_[hidden]
> Since the iterators are input_iterators, there is a bit of a
> problem with distance.  Dispatch on iterator_category would
> allow it for forward and above.

Yes it could.  I envisage something like this:

  template<class Iterator>
  void insert_equal(Iterator first, Iterator last) {
    insert_equal_aux(first, last, 
        std::iterator_traits<Iterator>::iterator_category());
  }
 
  template<class Iterator>
  void insert_equal_aux(Iterator first, Iterator last, 
                        std::input_iterator_tag) {
    insert_equal_sort(first, last);
  }
 
  template<class Iterator, class Category>
  void insert_equal_aux(Iterator first, Iterator last, 
                        Category) {
    if (first != last)
    {
      if (m_impl.size() / std::distance(first, last) < 100)
        insert_equal_sort(first, last);
      else
        insert_equal_loop(first, last);
    }
  }
 
  template<class Iterator>
  void insert_equal_loop(Iterator first, Iterator last) {
    for ( ; first != last; ++first)
      insert_equal(*first);
  }

  template<class Iterator>
  void insert_equal_sort(Iterator first, Iterator last) {
    m_impl.insert(m_impl.end(), first, last);
    std::stable_sort(m_impl.begin(), m_impl.end(), 
      compose_f_gx_hy(m_key_compare, KeyOfValue(), KeyOfValue()));
  }
    
Now here is a result which may surprise you:  It may be better
to sort always when we don't know distance.  The reason is that 
I switched to using stable_sort and it is always quite quick, 
and usually much quicker.  Here are some numbers from my test 
program.  You'll note that sorting is never particularly bad -
the worst times that are slower than looping are 0.02/0.009 and 
0.015 / 0.005 , i.e. 2-3 times slower.  OTOH, looping can be 
1.1/0.025 = ~40 times slower than sorting.

size(),distance(first,last)
        loop
        sort
        size/distance < 100 ? sort : loop
1,10000
        1.113
        0.025
        0.025
10,10000
        0.655
        0.025
        0.019
100,10000
        0.645
        0.025
        0.026
1000,10000
        0.755
        0.026
        0.025
10000,10000
        1.78
        0.045
        0.04
10000,1000
        0.13
        0.015
        0.021
10000,200
        0.026
        0.015
        0.014
10000,100
        0.009
        0.02
        0.011
10000,50
        0.005
        0.015
        0.005
10000,10
        0.006
        0.014
        0
10000,1
        0
        0.014
        0

Mark