Re: RFC: where to put sorted vector template/class?

On 07/10/2012 10:07 AM, Noel Grandin wrote:
> On 2012-07-10 15:35, Caolán McNamara wrote:
> > On Tue, 2012-07-10 at 14:53 +0200, Noel Grandin wrote:
> > > Rather than re-implement such a class/template repeatedly, is there a
> > > common place I could stash such a template, and then include it in the
> > > places it is necessary?
> > o3tl maybe ?
>
> Since I have your attention, and I know very little about modern 
> template programming :-)
> How does this look? It's the bare minimum I need in a sorted_vector 
> class.
>
> namespace o3tl
> {
> /** Represents a sorted vector of values.
>
>     @tpl Value
>     @tpl Compare comparison method
> */
> template <class Value, class Compare = less<Value>>
> class sorted_vector : vector<Value>
> {
> public:
>
>     // MODIFIERS
>     pair<iterator,bool> insert( const Value& x );
>     size_type           erase( const Value& x );
>
>     // OPERATIONS
>     /* Searches the container for an element with a value of x
>      * and returns an iterator to it if found, otherwise it returns an
>      * iterator to sorted_vector::end (the element past the end of the 
> container).
>      */
>     iterator            find( const Value& x ) const;
>
> };
>
>
>
> // IMPLEMENTATION
>
> template <class Value, class Compare>
> pair<iterator,bool> sorted_vector<Value,Compare>::insert( const Value& 
> x )
> {
>     iterator it = std::lower_bound(begin(), end(), p, Compare);
>     if( !Compare(*it, x) )
>     {
>         return make_pair( it, false );
>     }
>     it = insert( it, p );
>     return make_pair( it, true );
> }
>
> template <class Value, class Compare>
> size_type sorted_vector<Value,Compare>::erase( const Value& x )
> {
>     iterator it = std::lower_bound(begin(), end(), p, Compare);
>     if( !Compare(*it, x) )
>     {
>         erase( it );
>         return 1;
>     }
>     return 0;
> }
>
> template <class Value, class Compare>
> iterator sorted_vector<Value,Compare>::find( const Value& x )
> {
>     iterator it = std::lower_bound(begin(), end(), p, Compare);
>     if( !Compare(*it, x) )
>     {
>         return it;
>     }
>     return end();
> }

How large do you expect the sorted vector to be? I ask because a linear 
search is used, which on average will take time n/2 to find the item and 
n to not find the item (assuming vector of size n). Perhaps for this 
particular class that does not matter, and if you know that the vectors 
will be small, it is likely faster than anything else you can do. I 
consider this a minor point since it is likely as efficient as what you 
are replacing.

Also, I agree with Philipp Riemer about using find, then you can always 
change find to make it more efficient when needed.

Also, consider using an already created STL sorted vector.... don't know 
if that can be done.

I believe that the LOKI library has one that is licensed with MIT license
http://loki-lib.sourceforge.net/

This one has no particular license attached so you would need to ask the 
author
http://www.codeproject.com/Articles/3217/An-STL-compliant-sorted-vector

I believe that set and multi-set are backed by a binary tree

--
Andrew Pitonyak
My Macro Document: http://www.pitonyak.org/AndrewMacro.odt
Info:  http://www.pitonyak.org/oo.php