Re: [boost] associative_vector: request for formal review

From: Mark Rodgers (mark.rodgers_at_[hidden])
Date: 2000-06-01 02:53:20

> The former, actually. I would have put it in detail if I
> intended to protect it.

Fair enough.  I had assumed it was like the tree behind the std
associative containers - i.e., not for public use.

One further thought - it would be nice if you could improve the
efficiency of bulk inserts.  I tried adding the following
function to associative_vector:

  template<class Iterator>
  void insert_equal_x(Iterator first, Iterator last) {
    m_impl.insert(m_impl.end(), first, last);
    std::sort(m_impl.begin(), m_impl.end(),
        compose_f_gx_hy(m_key_compare, KeyOfValue(), KeyOfValue()));
  }

I then used the following test function

void test(int n, int m)
{
    std::vector<int> initial(n);
    std::generate_n(initial.begin(), n, std::rand);

    std::vector<int> add(m);
    std::generate_n(add.begin(), m, std::rand);

    avint av1;
    av1.insert_equal_x(initial.begin(), initial.end());
    avint av2;
    av2.insert_equal_x(initial.begin(), initial.end());

    std::cout << n << "," << m << std::endl;
    {
        boost::timer t;
        av1.insert_equal(add.begin(), add.end());
        std::cout << "\t" << t.elapsed() << std::endl;
    }
    {
        boost::timer t;
        av2.insert_equal_x(add.begin(), add.end());
        std::cout << "\t" << t.elapsed() << std::endl;
    }
}

and measured the results for various values of n and m.  The results
were fascinating

1,10000
        1.1
        0.025
10,10000
        0.65
        0.025
100,10000
        0.643
        0.026
1000,10000
        0.754
        0.028
10000,10000
        1.773
        0.052
10000,1000
        0.131
        0.035
10000,100
        0.016
        0.058
10000,10
        0.004
        0.466
10000,1
        0.004
        2.517

It suggests that there is probably some rule that could be used to
switch between the two algorithms.  Either

1.  size() < N, or
2.  distance(first, last) > M, or
3.  distance(first, last) / size() > P.

I would think that at least vector_multiset's ranged constructor 
could take advantage of this alternative.

For insert_unique perhaps something along the lines of

  template<class Iterator>
  void insert_unique_x(Iterator first, Iterator last) {
    m_impl.insert(m_impl.end(), first, last);
    std::sort(m_impl.begin(), m_impl.end(),
              compose_f_gx_hy(m_key_compare, 
                              KeyOfValue(), 
                              KeyOfValue()));
    m_impl.erase(std::unique(m_impl.begin(), 
                             m_impl.end(),
                             compose_f_gx_hy(m_key_compare, 
                                             KeyOfValue(),
                                             KeyOfValue())),
                  m_impl.end());
  }

would be advantageous in certain circumstances.

Just a thought.

Mark