std::find vs. deriving template from vector

Question

I use vectors a lot in my programming, and generally to traverse a vector for an existing value I use std::find as in:

std::vector<int> foo;
std::vector<int>::iterator pos( std::find( foo.begin(), foo.end(), bar );

This is a real bore. So I went to deriving a template from std::vector to provide a find method:

template<class T>
class foovector : public std::vector<T>
{
public:
    typename std::vector<T>::iterator find( const T& value )
    {
        return std::find( this->begin(), this->end(), value );
    }
};

And so now I can do find's more naturally:

foovector<int> foo;
foovector<int>::iterator pos( foo.find( bar ) );

My question is that this seems such a natural and obvious extension to vector, so why isn't it part of the STL or even boost? I feel like I'm missing some Arcane Knowledge here.

Answer 1

Because if you typically need to do a lot of finds, you should use a set or map (or a hashed version of either). Not only is it easier to write, but these have O(log n) find complexity, whereas an unsorted vector is O(n).

With map:

map<stuff> m
m[bar] // returns a reference to the element with key bar.

Set is similar.

Answer 2

1. Inheriting from STL containers is not considered a great idea - they don't have virtual destructors since they were not designed for this.

2. <vector>'s strength is not its searchability - there are other containers specialized for that.

3. I suspect that most people just don't find the code you are replacing that bothersome.

Answer 3

The STL design is to provide collections that have a narrow interface that only implements methods that you cannot implement without access to private members.

Then, they add template functions on iterators (not collections). This means that many of those functions work well even if you make your own collection as long as you provide standard iterators. You don't need inheritance to make this work -- so things can stay separate.

Answer 4

Possibly because vector is the simplest type of container and there are better (associative) containers to use if searching is a priority.

Vector has O(1) performance if you search by index, but if you use a search algorithm, you lose all that benefit.

Answer 5

What about you do what you want to achieve and still not go into the dubious path of inheriting from std::vector

define a freestanding function

template <typename T>
typename std::vector<T>::const_iterator find( const std::vector<T>& v, const T& value )
 {
     return std::find( v.begin(), v.end(), value );
 }

you can put this into namespace std(which, technically speaking is not allowed), or in some other namespace (with the tradeoff that it won't be found by ADL, so you will need to qualify it). HTH

P.S. by the way you could generalize this for all containers

template <typename Container, typename T>
typename Container::const_iterator find( const Container& c, const T& value )
{
     return std::find( c.begin(), c.end(), value );
}

Answer 6

If you're looking at searching more often than insertion, i.e. your vector is a designed around write once functionality, than may I suggest the sort followed by binary_search of algorithms?

Then you'll have O( ln ) time.

Answer 7

Actually, I have wrapped most of the free functions defined in <algorithm> with versions taking containers / ranges instead of iterators. Not only is it much safer (I can add simple checks, make sure the range is valid, etc...) it's also much more convenient.

For your case, the generic way to do this is:

template <typename Container>
typename Container::iterator find(Container& c,
                                  typename Container::value_type const& v)
{
  return std::find(c.begin(), c.end(), v);
}

template <typename Container>
typename Container::const_iterator find(Container const& c,
                                        typename Container::value_type const& v)
{
  return std::find(c.begin(), c.end(), v);
}

This can be used with any STL-compliant container.

Of course, what would be nice would be to adapt this through Concept in order to use the member function find if available...