Jump to content
  • Advertisement
Sign in to follow this  
rish2005

Searching Vector of C++ objects

This topic is 4655 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

I have vector of C++ objects.. see sample code: class objclass { public: objclass(int i); int data; ~objclass(); }; objclass::objclass(int i) { data=i; } ---------------------------------- vector<objclass > *objvector=new vector<objclass> objclass obj1(20); objclass obj2(10); objclass obj3(40); objvector->push_back(obj1); objvector->push_back(obj2); objvector->push_back(obj3); --------------------------------------- Now i want to search for the object containing value '10' in a vector. Is there any efficeint way to search except going through a vector elemnt one by one in a for loop and comparing the data stored in object with '10'. I want to search a vector conatining 3000 objects. ------------------------------------------------

Share this post


Link to post
Share on other sites
Advertisement
You have two options here:

1) make sure the data in the vector is ordered, then use a binary search.

2) use a more advanced structure to store your data such as a tree or a hash table.

and unordered vector cant be searched any faster.

Share this post


Link to post
Share on other sites
First off why are you dynamically allocating std::vector? because generally you don't need to do this unless you want to be able to share a vector instance in this case i would use a smart pointer for that.

Anyways back to your question yes you can do better from your linear to logarithmic time complexity. There are two main ways to go about this both require the ability to compare instances of your user-defined type.

The first is use std::set/multi_set this an always sorted container that gives you logarithmic time lookup.

The second alternative is to sort the vector by using one of following algorithms std::sort/stable_sort then use one the following binary search algorithms std::binary_search/lower_bound/upper_bound/equal_range.

To use either of those you need to be able to compare elements and there are anumber of methods for that:

Overload the relational less than operator for your user-defined type.

Or provide a custom predicate functor/function then provide it to the library.

Check here for further details.

Share this post


Link to post
Share on other sites
If the data you are looking for could be at any position in your array, you have to examine every object in the array to know if an object is definatley not in the array.

You have to consider tradeoffs here:

finding an element in an unsorted vector is an O(n) operation.
inserting an element into an unsorted vector is O(1).

finding an element in a sorted vector is an O(logn) operation.
inserting an element into an unsorted vector is O(n).

Share this post


Link to post
Share on other sites
Quote:
Original post by rish2005
I have vector of C++ objects..
see sample code:
class objclass
{
public:
objclass(int i);
int data;
~objclass();
};

objclass::objclass(int i)
{
data=i;
}

----------------------------------
vector<objclass > *objvector=new vector<objclass>

objclass obj1(20);
objclass obj2(10);
objclass obj3(40);

objvector->push_back(obj1);
objvector->push_back(obj2);
objvector->push_back(obj3);
---------------------------------------
Now i want to search for the object containing value '10' in a vector.
Is there any efficeint way to search except going through a vector elemnt one by one in a for loop and comparing the data stored in object with '10'.
I want to search a vector conatining 3000 objects.
------------------------------------------------


find or find_if

Share this post


Link to post
Share on other sites
Quote:
Original post by George2
find or find_if
That's O(n), which the OP wants to avoid. The only way to be (algorithmically) faster is to have a sorted vector.

Note that it may not be faster in all cases; just because its O(n) doesn't mean it's slower than O(logn) for a given dataset.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!