Jump to content
  • Advertisement
Sign in to follow this  
3dcgmodeling

vector item find

This topic is 4187 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!