4

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.

codefool
  • 331
  • 1
  • 6
  • 3
    Free functions are preferred over member functions. That's the knowledge you're missing. Oh, and `std::vector* v = new foovector; delete v; // UB`. – GManNickG Oct 12 '10 at 16:20
  • 2
    Why is it an "obvious extension"? It is only obvious if you assume that member functions are preferred over non-member functions. That's pretty much an article of faith in Java, but that doesn't make it *true*. In C++, non-member functions are generally preferred whenever possible, as @GMan says. (In particular, `std::find` is generic and reusable. it works on `std::list` or `std::deque` too -- or even on your own home-made container. A member function can't be reused on other container types, so why should it be preferred?) – jalf Oct 12 '10 at 17:14
  • 1
    Another advantage of the non-member version is that it works on iterators, not on the vector itself. I can use it to search only in the first 10 elements of the vector: `std::find( foo.begin(), foo.begin() + 10)`. You lose that ability as well in the member version. – jalf Oct 12 '10 at 17:17
  • 1
    make a free function instead: `iter find(vector& v, T val);` so you dont have to write `begin(), end()` over and over. – Inverse Oct 12 '10 at 17:22
  • Because the call never changes - it's always std::find(begin(),end(),value) - hence it should be flattened into a separate, simpler call. In this case the vector isn't large, but I'm using it to keep track of seen indexes as they go by. std::set would do better, but seems overkill for what I need it for, as is std::map in this case. – codefool Oct 12 '10 at 17:25
  • 1
    @codefool: then write a non-member wrapper, so you can call `find(myVec)` and then it internally calls `std::find(myVec.begin(), myVec.end())`. It doesn't have to be a member function to avoid the iterator clutter. – jalf Oct 12 '10 at 17:26
  • 1
    @codefool: How is `std::set` "overkill"? It's just another container. – GManNickG Oct 12 '10 at 17:30
  • @GMan - I'm working with 20 numbers max. Not worth instantiating std:set and building a btree. To clarify, I'm just wanting to get rid of the clutter of the call and getting something more concise. It just seemed to me that it should already exist, but Deep Thought always has a reason, and that's what I was asking. Thank you all for your input. – codefool Oct 12 '10 at 17:36
  • GMan - Where in the literature is the support for "free functions are preferred over member functions"? No doubt it's there - somewhere - just not finding it. – codefool Oct 21 '10 at 16:46

6 Answers6

6

  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.

Community
  • 1
  • 1
Steve Townsend
  • 53,498
  • 9
  • 91
  • 140
  • `` can host a faster search than `` as long as it's sorted. One problem is that there are two kinds of search, and a member called `find` would be a little ambiguous. – Potatoswatter Oct 12 '10 at 16:24
  • @Potatoswatter - agree search of sorted vector can be faster but for large and/or fast-changing datasets would you recommend this approach? A lot of element shuffling, memory reallocating, manual sorting just to get a fast find. – Steve Townsend Oct 12 '10 at 17:23
  • Simple linear scan of an unsorted vector is faster than anything else up to about 10 elements. Measure it. It's interesting. – Zan Lynx Oct 12 '10 at 18:30
  • Yes I know, I have used this construct in my code. I just don't think it's a very scalable solution to the general case. – Steve Townsend Oct 12 '10 at 18:36
  • @Steve: Call `sort` on the vector's range and it's sorted. No manual shuffling or reallocating needed. Even if it were, people go to great lengths to get a fast find. – Potatoswatter Oct 12 '10 at 18:36
  • @potatoswatter - I know how this works. I just think that if you have a vector of large size (>> 10, say) it's not a great solution compared to the alternative ordered-by-design choices. Shuffling is (surely?) needed if elements are out of order. Reallocation is needed if vector size changes. – Steve Townsend Oct 12 '10 at 18:40
  • @Steve: `sort` handles the "shuffling" and `vector` handles the "reallocation." If you use `map`, then it handles the shuffling and allocation. Both are O(N log N) for the process, but `vector` will have a much lower coefficient and O(1) overhead instead of O(N). If I don't need the elements to be sorted after every insertion, I'll probably choose between a sorted `vector` or a `priority_queue` which is a differently-sorted `vector`. – Potatoswatter Oct 13 '10 at 01:51
6

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 );
}
Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
  • 2
    @Inverse: What we want are "range-based" algorithms. See Alexandrescu's "Iterators Must Go" and Boost.Range. – GManNickG Oct 12 '10 at 17:31
  • 1
    Doesn't that need to be `const_iterator`? – Mark Ransom Oct 12 '10 at 17:34
  • exactly, sorry, I copy-pasted it from the OP's code, didn't bother to recheck. Editing – Armen Tsirunyan Oct 12 '10 at 17:36
  • 1
    in this case a separate function should be provided that takes Container& and returns typename Container::iterator – Armen Tsirunyan Oct 12 '10 at 17:39
  • @GMan: sort of. I'm still not entirely convinced by his proposal. Iterators seem a more natural fit for some algorithms (it makes sense for `find`, for example, to return an iterator, not a range), so what I'd like to see is good support for both (and smooth interoperability between them, of course) – jalf Oct 12 '10 at 17:46
  • @jalf: I agree, having both and them being interoperable would definitely be the best of both worlds :) – Matthieu M. Oct 12 '10 at 18:15
5

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.

Lou Franco
  • 87,846
  • 14
  • 132
  • 192
  • The standard has to be as generic as possible, at the cost of being a little verbose. You're always free to optimize your own common use case. – Mark Ransom Oct 12 '10 at 17:32
2

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.

Component 10
  • 10,247
  • 7
  • 47
  • 64
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.

JoshD
  • 12,490
  • 3
  • 42
  • 53
1

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...

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722