This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
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
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |