Dekel Tsur <[EMAIL PROTECTED]> writes:
| There are more important things to do with the time it would take to do the
| changes.
| You can alway make the changes in the future, if needed.
Ahh... so you want me do the changes instead of you.
Besides IMO the InsetTable(pos, 0) looks strange when it really only
is the pos that you are looking for.
Ever wondered why I never apply patches "just like that", I want to
read them and have answered/corrected/argumented parts that I object
to/have questions about/want done another way first.
| > And you didn't save a lot of typing either. I am sure you even can
| > figure out a name for the functor that is shorter than
| > "InsetTable(pos, 0)".
|
| You do need the InsetTable(pos, 0) even if you use a function
| object.
Why?
lower_bound(vec.begin(), vec.end(), cmppos(), pos, cmppos());
struct cmppos {
public:
bool operator()(InsetTable const & a, pos_type p) const
return a.pos < p;
}
};
(ok so my first functor was not perfect...)
| > | Because lowerbound() takes logarithmic time for a sorted vector, but it is
| > | linear time for a sorted list.
| >
| > hmm da hmm...
| >
| > but insertion is O(n)... what about a std::set?
| >
|
| When we insert a new inset to the list, we need to update the positions of
| the other insets, so it will take linear time even if insetlist is stored
| using a list
| (std::map can also be used [not std::set] but it isn't better than a vector).
No not really we are speaking of O(n) + O(n) vs. O(log(n)) + O(n)
With a set you can shortcut to the insert position and then do a
linear search on the rest. With a vector you have to go linear all the
time. Anyway none of this is important since we are talking about a
small number of elements.
Lgb
