http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508
Bug ID: 59508
Summary: std::find could use specialized container's find
Product: gcc
Version: 4.9.0
Status: UNCONFIRMED
Severity: enhancement
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: olegendo at gcc dot gnu.org
It should be possible to invoke a container's specialized find function (e.g.
std::set::find, std::map::find, etc) from within std::find, if it is used in a
compatible way, i.e. std::find is invoked with begin and end iterators of the
container and a value ref.
This could be done by something like this ...
#include <vector>
#include <set>
#include <type_traits>
#include <algorithm>
namespace x
{
template<class InputIt, class T, class Enable = void> struct find_impl;
template<class InputIt, class T>
struct find_impl<InputIt, T, typename std::enable_if<std::is_same<typename
std::set<T>::iterator, InputIt>::value>::type>
{
static InputIt find (InputIt first, InputIt last, const T& value)
{
// if first == container's begin () and
// last == container's end () can use optimized implementation of
// std::set::find.
// but to do that, must be able to get container ref from the given
// iterators somehow, or look at unique properties of begin () and end ()
// iterators as returned from the container.
return first;
}
};
template<class InputIt, class T>
struct find_impl<InputIt, T, typename std::enable_if<!std::is_same<typename
std::set<T>::iterator, InputIt>::value>::type>
{
static InputIt find (InputIt first, InputIt last, const T& value)
{
return std::find (first, last, value);
}
};
template<class InputIt, class T> InputIt
find (InputIt first, InputIt last, const T& value)
{
return find_impl<InputIt, T>::find (first, last, value);
}
}
usage example:
int func1 (std::vector<int>& my_container)
{
return *x::find (my_container.begin (), my_container.end (), 5);
}
int func2 (std::set<int>& my_container)
{
return *x::find (my_container.begin (), my_container.end (), 5);
}
If it's not possible to figure out whether an iterator is a container's begin
() or end () because it would require adding a data member to the iterator,
another option could be to return internal subclasses of std::set::iterator for
begin () and end () and then check the iterator types in std::find. However,
I'm not sure whether containers are allowed to do that according to the
standard.
