Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unsequenced std::find, and std::any_of by value

Say I have an std::vector<int> and want to know if it contains a 3 or get the iterator to the 3.

I do not want to use an std::set or std::multiset for whatever reason.

I would like to do this in std::execution::par_unseq mode.
The two options I see are std::any_of and std::find, but they do not quite do it for me.

#include <execution>
#include <functional>
#include <iostream>
#include <vector>

int main()
{
  std::vector vec{ 1, 1, 1, 1, 1, 3, 3, 3, 3 };

  bool contains{ std::any_of(
      std::execution::par_unseq,
      vec.begin(), vec.end(),
      std::bind(std::equal_to{}, std::placeholders::_1, 3)) };

  auto found{ std::find(std::execution::par_unseq, vec.begin(), vec.end(), 3) };

  return 0;
}

The std::any_of should do what I want, but the call is extremely messy for what it does. Ranges and std::bind_front will help, but not a whole lot.

The problem with std::find is that it has to find the first occurrence of a 3, which limits its efficiency, as I do not care which 3 it finds.

  • Is there an alternative to std::any_of that searches by value?
  • Is there std::find (and std::search) that finds any match, not the first?

Answers up to c++20 are welcome.


EDIT:

For clarification, I do not want a function that checks for contains and gives me an iterator at the same time. I am looking for two distinct functions (One that returns an iterator, one that returns a bool).

like image 753
nascardriver Avatar asked Nov 15 '19 09:11

nascardriver


2 Answers

Say I have an std::vector and want to know if it contains a 3 and optionally get the iterator to the 3.

I would pack the std::any_of version to a template-function and use a lambda instead of std::bind.

Note that the std::any_of is possibly implimented by std::find_if

#include <iostream>
#include <vector>
#include <algorithm> // std::find_if
#include <execution> // std::execution
#include <iterator>  // std::distance

template<typename Iterator, typename Predicate>
auto find_any_of(Iterator first, Iterator last, Predicate pred) -> std::pair<bool, Iterator>
{
   const Iterator iter = std::find_if(std::execution::par_unseq, first, last, pred);
   return { iter != last, iter };
}

int main()
{
   std::vector vec{ 1, 1, 1, 1, 1, 3, 3, 3, 3 };
   // you call the function like
   const auto [found, ele_iter]
      = ::find_any_of(vec.cbegin(), vec.cend(), [](const int ele) { return ele == 3; });

   if (found)
      std::cout << "Element found at index: " << std::distance(vec.cbegin(), ele_iter);
   return 0;
}
like image 98
JeJo Avatar answered Sep 23 '22 09:09

JeJo


I don't quite see what you consider bad about any_of, especially if you use a lambda instead of the std::bind chant:

bool contains = std::any_of(std::execution::par_unseq,
                            vec.begin(), vec.end(),
                            [](auto elem) { return elem == 3; });

(Distribute line breaks and whitespace to your liking...)


Alternatively, if this is common, you might also define a functor object yourself that takes the value to compare to in the constructor. Or, more conveniently, something like this:

template<class T>
auto equalTo(T value)
{
  return [value](auto other) { return other == value; };
}

// ...

bool contains = std::any_of(std::execution::par_unseq,
                            vec.begin(), vec.end(),
                            equalTo(3));

As for something like std::find_any that takes advantage of early cancellation when executed in parallel: Such a thing does not exist in the standard library yet. The serial versions are obviously optimal by returning upon finding the first occurrence, but noone went and added a different algorithm to improve the parallel case. It would also be uncommon for calls to the standard library to have timing-dependent results (even if race-free), so I wouldn't get my hopes up.

I'll also note that the current MSVC implementation actually does the fast cancellation optimization discussed above (how much it really helps depends on the chunking policy, which I can't figure out at a glance). For clang I can't really tell anything...

like image 38
Max Langhof Avatar answered Sep 24 '22 09:09

Max Langhof