public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/59508] New: std::find could use specialized container's find
@ 2013-12-14 13:25 olegendo at gcc dot gnu.org
  2013-12-15 16:38 ` [Bug libstdc++/59508] " daniel.kruegler at googlemail dot com
                   ` (6 more replies)
  0 siblings, 7 replies; 8+ messages in thread
From: olegendo at gcc dot gnu.org @ 2013-12-14 13:25 UTC (permalink / raw)
  To: gcc-bugs

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.


^ permalink raw reply	[flat|nested] 8+ messages in thread
end of thread, other threads:[~2024-01-08 10:58 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-12-14 13:25 [Bug libstdc++/59508] New: std::find could use specialized container's find olegendo at gcc dot gnu.org
2013-12-15 16:38 ` [Bug libstdc++/59508] " daniel.kruegler at googlemail dot com
2013-12-15 17:28 ` olegendo at gcc dot gnu.org
2013-12-15 18:34 ` daniel.kruegler at googlemail dot com
2013-12-15 19:48 ` olegendo at gcc dot gnu.org
2013-12-16 17:04 ` redi at gcc dot gnu.org
2013-12-16 17:45 ` olegendo at gcc dot gnu.org
2024-01-08 10:58 ` redi at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).