Binary_search in STL set over set's member function find?

Question

Why do we have 2 ways like above to search for an element in the set?

Also find algorithm can be used to find an element in a list or a vector but what would be the harm in these providing a member function as well as member functions are expected to be faster than a generic algorithm?

Why do we need remove algorithm and create all the drama about erase remove where remove will just shift the elements and then use erase to delete the actual element..Just like STL list provides a member function remove why cant the other containers just offer a remove function and be done with it?

Answer 1

Binary_search in STL set over set's member function find?
Why do we have 2 ways like above to search for an element in the set?

Binary search returns a bool and set::find() and iterator. In order to compare apples to apples, the algorithm to compare set::find() with is std::lower_bound() which also returns an iterator.

You can apply std::lower_bound() on an arbitrary sorted range specified by a pair of (forward / bidirectional / random access) iterators and not only on a std::set. So having std::lower_bound() is justified. As std::set happens to be a sorted range, you can call

std::lower_bound(mySet.begin(), mySet.end(), value);

but the

mySet.find(value);

call is not only more concise, it is also more efficient. If you look into the implementation of std::lower_bound() you will find something like std::advance(__middle, __half); which has different complexity depending on the iterator (whether forward / bidirectional / random access iterator). In case of std::set, the iterators are bidirectional and advancing them has linear complexity, ouch! In contrast, std::set::find() is guaranteed to perform the search in logarithmic time complexity. The underlying implementation (which is a red and black tree in case of libstdc++) makes it possible. Offering a set::find() is also justified as it is more efficient than calling std::lower_bound() on std::set.

Also find algorithm can be used to find an element in a list or a vector but what would be the harm in these providing a member function as well as member functions are expected to be faster than a generic algorithm?

I don't see how you could provide a faster member function for list or vector, unless the container is sorted (or possesses some special property).

Why do we need remove algorithm and create all the drama about erase remove where remove will just shift the elements and then use erase to delete the actual element..Just like STL list provides a member function remove why cant the other containers just offer a remove function and be done with it?

I can think of two reasons.

Yes, the STL is seriously lacking many convenience functions. I often feel like I live in a begin-end hell when using algorithms on an entire container; I often proved my own wrappers that accept a container, something like:

template <typename T>
bool contains(const std::vector<T>& v, const T& elem) {

    return std::find(v.begin(), v.end(), elem) != v.end();
}

so that I can write

if (contains(myVector, 42)) { 

instead of

if (std::find(myVector.begin(), myVector.end(), 42) != myVector.end()) { 

Unfortunately, you quite often have to roll your own or use boost. Why? Because standardization is painful and slow so the standardization committee focuses on more important things. The people on the committee often donate their free time and are not paid for their work.

Now deleting elements from a vector can be tricky: Do you care about the order of your elements? Are your elements PODs? What are your exception safety requirements?

Let's assume you don't care about the order of your elements and you want to delete the i-th element:

std::swap(myVector[i], myVector.back());
myVector.pop_back();

or even simpler:

myVector[i] = myVector.back(); // but if operator= throws during copying you might be in trouble
myVector.pop_back();

In C++11 with move semantics:

myVector[i] = std::move(myVector.back());
myVector.pop_back();

Note that these are O(1) operations instead of O(N). These are examples of the efficiency and exception safety considerations that the standard committee leaves up to you. Providing a member function and "one size fits all" is not the C++ way.

Having said all these, I repeat I wish we had more convenience functions; I understand your problem.

Answer 2

I'll answer part of your question. The Erase-Remove idiom is from the book “Effective STL” written by Scott Meye. As to why remove() doesn't actually delete elements from the container, there is a good answer here, I just copy part of the answer:

The key is to realize that remove() is designed to work on not just a container but on any arbitrary forward iterator pair: that means it can't actually delete the elements, because an arbitrary iterator pair doesn't necessarily have the ability to delete elements.

Why STL list provides a member function remove and why can't the other containers just offer a remove function and be done with it? I think it's because the idiom is more efficient than other methods to remove specific values from the contiguous-memory containers.