Sign in to follow this  
3dcgmodeling

vector item find

Recommended Posts

The find function is defined in <algorithm>, so just add:

#include<algorithm>

...To your source code, and the the function definition is:

template<class InputIterator, class Type>
InputIterator find(
InputIterator _First,
InputIterator _Last,
const Type& _Val
);

So, to search an entire vector, you would use:



std::vector<VectorType>::iterator Found = std::find(MyVec.begin(), MyVec.end(), value);





If no match weas found, the function will return MyVec.end(), and you can check for equvalency with (Found == MyVec.end()). For the find operator to work, on vectors, of say, your own custom classes, you have to overload the '==' operator for find to function correctly. See here for an example of operator overloading.

Share this post


Link to post
Share on other sites
#include <algorithm> and use std::find:

std::vector<int> v;
v.push_back(3);
v.push_back(4);
v.push_back(5);
std::vector<int>::iterator pos = std::find(v.begin( ), v.end( ), 4);
if (pos != v.end( ))
std::cout << "The number 4 is in the vector.\n";


-jouley

[Edit: Double beated...]

Share this post


Link to post
Share on other sites
Quote:
std::find()
std::find_if()
To elaborate a bit, find() is a generic algorithm that searches a range bounded by a pair of 'input iterators'. It can be used with SC++L container types such as vector and list (but not with container adapters such as stack). It can also be used with 'raw' arrays, or really anywhere that the 'input iterator' model can be applied.

This generality comes at a cost though. Since find() knows very little about the nature of the container it is searching, it really can't do much other than plow through the elements in sequence until it finds what it's looking for. In other words, its complexity is linear - at worst it will check every element in a container while searching for the specified item.

vector is an unordered sequential container. As such, there's really nothing 'special' it can do to search itself for a particular item. Given that a vector::find() function would most likely do the same thing as the corresponding global function, there would be little point to its existence.

std::map, on the other hand, does have its own find function. This is because a map can be searched much more efficiently than a vector in the general case, due to its internal structure (typically a binary tree). Since std::find() is not aware of this internal structure (only that it's been passed a pair of input iterators), it can't take advantage of it. This is, in essence, why map has a find function and vector does not.

There may however be cases where you know that a vector or other container is sorted or that its elements are arranged in a certain way. In these cases you can forgo the generic 'find' algorithm in favor of specialized algorithms such as binary_search().

(Standard disclaimer: I'm not a C++ pro, nor do I have a background in computer science, so I can't completely guarantee the accuracy or correctness of the information presented above.)

Share this post


Link to post
Share on other sites
Quote:
Original post by 3dcgmodeling
are there any tutorial avaiable to common and frequent used or useful stl stuff?
Someone else will probably mention it if I don't, so I'll go ahead and point out that technically it's not the STL, but rather the Standard C++ Library (much of which is derived from the original STL).

For a quick and easy reference on the topic, I usually go here. Note that the front page includes links to some other useful resources.

You can find a .pdf summarizing the algorithms portion of the SC++L here.

One of the first two Game Programming Gems books also has an introductory article on using the SC++L containers. There are also a number of books on the subject available (these are of course more in-depth references, and not really 'tutorials' per se).

Google is also of course a good resource. The second hit for the search string 'using the stl' is this tutorial, which looks promising. (Correct terminology aside, you'll probably have better luck searching for the term 'STL' than for 'SC++L' or 'standard C++ library').

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
For a quick and easy reference on the topic, I usually go here. Note that the front page includes links to some other useful resources.


Note that this covers the STL and not the SC++L. In particular, it will mention parts of the STL that are not actually provided in C++ (although I personally feel in most cases that they really should have been). In these cases, the page will clearly indicate the situation ("this function/class is an SGI extension; it is not provided in C++" or words to that effect).

Quote:
Google is also of course a good resource. The second hit for the search string 'using the stl' is this tutorial, which looks promising. (Correct terminology aside, you'll probably have better luck searching for the term 'STL' than for 'SC++L' or 'standard C++ library').


True, unfortunately. :(

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this