Re: [PATCH v2] Implement the ability to set/unset environment variables to GDBserver when starting the inferior

[Simon Marchi <simon.marchi@polymtl.ca>]

On 2017-08-12 06:33, Sergio Durigan Junior wrote:
>> Actually, if we expected the user to set thousands of environment
>> variables and needed it to be fast to set and unset variables, it
>> would be good to use std::set because of the O(log(N))
>> lookups/insertions/removals, which matters more when you have a lot of
>> elements.  But when you just have a few elements, the constant cost is
>> more significant.  A vector-based set would have O(N) complexity for
>> these operations (at least for insertions and removals, for lookups it
>> depends if it is sorted), which would be bad if we had thousands of
>> elements.  But since we expect to have just a few, it would likely be
>> faster than std::set's constant cost.
> 
> You mean std::vector's constant cost, right?

No, I meant std::set's constant cost, although it wasn't clear.  I meant 
the constant hidden by the big-O notation.  The complexity of removing 
from a set may be O(log(N)), but we could also write it as "C1 * 
log(N)", where C1 is a constant.  For a vector, it would take "C2 * N", 
where C2 is a constant.  If C1 is much larger than C2, then using a set 
only starts being interesting with large Ns.  That does a much better 
job at explaining than I do:

http://lafstern.org/matt/col1.pdf

Thanks,

Simon