
Boost : 
From: Mark Rodgers (mark.rodgers_at_[hidden])
Date: 20000601 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk