CODEWITHSUNDEEP
c++liststlbinary-search
Rajat
Rajat

Reputation: 323

Binary search in a sorted list with all nodes as struct C++

I have a list with all the elements as struct of form

typedef struct person_node{
    string name;
    string country;
}person;

std::list<person> list;

The list is already sorted on person name.

How do I use the inbuilt binary_search() function in this?

I already know how to use this binary_search() on a list with only numbers as data, but I wonder how can I use it for such a list.

I am using this binary function as:

binary_search (list.begin(), list.end(), value, compare_function);

Only thing I don't know is, "What should I enter in place of value, if I need to look for a specific name in the list?"

Also I want an iterator to point to that node, if found.

Upvotes: 1

Views: 6275

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490378

You enter a person containing the name you want to find.

Also note that binary_search is only rarely useful (it only tells you whether the item is present, not where it is in the collection. It is doubly useless on a std::list, because it requires random-access iterators to work at all well (which std::list doesn't provide).

So, what you probably want is an std::vector<person> or std::deque<person>, which you'll probably want to search with std::lower_bound or std::upper_bound. std::lower_bound and std::upper_bound will each return an iterator to the item they found, giving you access to that object.

Upvotes: 6

CashCow
CashCow

Reputation: 31445

The 3rd item describes what you are searching for in such a way that you can call

compare_function(*iter, value )

or

compare_function( value, *iter )

where iter is a valid iterator within your collection. This should return true in the first case if *iter must appear before value in your list for it to remain sorted, and in the second case vice versa.

Note, therefore, that you can actually pass in a string as the 3rd parameter if your compare_function supports both these overloads. The prototype is:

template <class ForwardIterator, class T, class Compare>
   bool binary_search ( ForwardIterator first, ForwardIterator last,
                   const T& value, Compare comp );

and it is not necessary that the T is the value type of the iterator.

Incidentally whilst you can use it for a std::list, it is extremely inefficient for iterators that are not random-access as each std::advance statement is O(N) thus the whole operation is O(N log N). Even a regular std::find would be faster.

Use vector or multiset if you can have duplicates or set if you do not allow duplicates.

Also binary_search itself returns true/false as to whether the item exists and doesn't find you the item (so you won't know their country). If you have duplicates you can use std::equal_range to get a list of all such values. If you do not you can use std::lower_bound which will get you an iterator to the first item with a name equal to or greater than yours, then check if it is equal, rather than greater.

Upvotes: 2

Related Questions