From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-437575-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 22202 invoked by alias); 14 Dec 2013 13:25:40 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Received: (qmail 21971 invoked by uid 48); 14 Dec 2013 13:25:36 -0000
From: "olegendo at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/59508] New: std::find could use specialized container's find
Date: Sat, 14 Dec 2013 13:25:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: olegendo at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter
Message-ID: <bug-59508-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg01230.txt.bz2

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.