Algorithms

Detailed Description

SIMD implementations of the standard algorithms.

Each algorithm keeps the name and the meaning of its std counterpart, takes ranges, and calls its operation on SIMD registers. A position comes back as an iterator into the range given, and a count or a reduction as a value. Where the standard uses one name for the in-place and the out-of-place forms, this module has two, eve::algo::transform_inplace and eve::algo::transform_to, because the two loops differ. Every algorithm takes options between brackets, see Options.

Classes
struct	eve::algo::set_intersection_result< I1, I2, O >
	Return type of eve::algo::set_intersection: where each input stopped, and the output. More...

Variables
constexpr auto	eve::algo::max_element = function_with_traits<max_element_>[default_simple_algo_traits]
	SIMD variation on std::max_element not exact match.
constexpr auto	eve::algo::search = function_with_traits<search_>[eve::algo::unroll<4>]
	SIMD version of std::search (subsequence in a sequence).
constexpr auto	eve::algo::all_of = function_with_traits<all_of_>[default_simple_algo_traits]
	a SIMD version of std::all_of
constexpr auto	eve::algo::any_of = function_with_traits<any_of_>[default_simple_algo_traits]
	a SIMD version of std::any_of
constexpr auto	eve::algo::copy = function_with_traits<copy_>[default_simple_algo_traits]
	SIMD optimized copy algorithm.
constexpr auto	eve::algo::copy_backward = function_with_traits<copy_backward_>[default_simple_algo_traits]
	SIMD optimized backward copy algorithm.
constexpr auto	eve::algo::copy_if = function_with_traits<copy_if_>
	SIMD variation on std::copy_if.
constexpr auto	eve::algo::equal = function_with_traits<equal_>[all_of.get_traits()]
	a SIMD version of std::equal
constexpr auto	eve::algo::fill = function_with_traits<fill_>[default_simple_algo_traits]
	a version of std::fill
constexpr auto	eve::algo::find_if = function_with_traits<find_if_>[default_simple_algo_traits]
	SIMD version of std::find_if.
constexpr auto	eve::algo::find = function_with_traits<find_>[find_if.get_traits()]
	a version of find_if with a value to find instead of a predicate to test.
constexpr auto	eve::algo::find_if_not = function_with_traits<find_if_not_>[find_if.get_traits()]
	a version of eve::algo::find_if where the preicate is negated
constexpr auto	eve::algo::find_last_if = function_with_traits<find_last_if_>[default_simple_algo_traits]
	SIMD version of std::ranges::find_last_if.
constexpr auto	eve::algo::find_last = function_with_traits<find_last_>[find_last_if.get_traits()]
	a version of find_last_if with a value to find instead of a predicate to test.
constexpr auto	eve::algo::find_last_if_not = function_with_traits<find_last_if_not_>[find_last_if.get_traits()]
	a version of find_last_if where the preicate is negated
constexpr auto	eve::algo::for_each = function_with_traits<for_each_>
	a basic for_each algorithm.
struct {
}	eve::algo::for_each_iteration_with_expensive_optional_part
	low level util for writing algorithms. A variation on for_each_iteration that has a place for work we don't want duplicated in assembly.
constexpr auto	eve::algo::for_each_selected = function_with_traits<for_each_selected_>
	an algorithm to perform some scalar operation for every element, that matches a given SIMD predicate. Defined in Header
constexpr auto	eve::algo::iota = function_with_traits<iota_>[copy.get_traits()]
	SIMD version of std::iota For conversion/overflow behaviour, should follow the standard.
constexpr auto	eve::algo::keep_if = function_with_traits<keep_if_>[no_traits]
	In-place version of std::copy_if.
constexpr auto	eve::algo::max_value = function_with_traits<max_value_>[default_simple_algo_traits]
	SIMD algorithm that returns maximum value in the range.
constexpr auto	eve::algo::min_element = function_with_traits<min_element_>
	SIMD version of std::min_element.
constexpr auto	eve::algo::min_value = function_with_traits<min_value_>[default_simple_algo_traits]
	SIMD algorithm that returns minimum value in the range.
constexpr auto	eve::algo::mismatch = function_with_traits<mismatch_>[find_if.get_traits()]
	a SIMD version of std::mismatch
constexpr auto	eve::algo::none_of = function_with_traits<none_of_>
	a SIMD version of std::none_of
constexpr auto	eve::algo::reduce = function_with_traits<reduce_>[default_simple_algo_traits]
	SIMD optimized version of std::reduce.
constexpr auto	eve::algo::remove_if = function_with_traits<remove_if_>[no_traits]
	SIMD version of std::remove_if.
constexpr auto	eve::algo::remove = function_with_traits<remove_>[no_traits]
	SIMD version of std::remove.
constexpr auto	eve::algo::reverse = function_with_traits<reverse_>[no_unrolling][no_aligning]
	SIMD version of std::reverse.
constexpr auto	eve::algo::reverse_copy = function_with_traits<reverse_copy_>[algo::unroll<1>]
	SIMD version of std::reverse_copy.
constexpr auto	eve::algo::set_intersection = function_with_traits<set_intersection_>
	SIMD variation on std::set_intersection that HAS A SLIGHTLY DIFFERENT SEMANTICS.
constexpr auto	eve::algo::swap_ranges = function_with_traits<swap_ranges_>[default_simple_algo_traits]
	SIMD version of std::swap_ranges.
constexpr auto	eve::algo::transform_inplace = function_with_traits<transform_inplace_>[default_simple_algo_traits]
	same as;
constexpr auto	eve::algo::transform_to = function_with_traits<transform_to_>[default_simple_algo_traits]
	SIMD version of std::transform.
constexpr auto	eve::algo::transform_copy_if = function_with_traits<eve_implementation_defined>
	Similar to applying eve::transform_to and eve::copy_if at the same time.
constexpr auto	eve::algo::transform_keep_if = function_with_traits<transform_keep_if_>[no_traits]
	In-place version of eve::algo::transform_copy_if.
constexpr auto	eve::algo::transform_reduce = function_with_traits<transform_reduce_>[default_simple_algo_traits]
	SIMD version of std::transform_reduce for a single range.

Variable Documentation

all_of

auto eve::algo::all_of = function_with_traits<all_of_>[default_simple_algo_traits]

inlineconstexpr

a SIMD version of std::all_of

Tests if all of the elements in the range match the predicate. by default aligns and unrolls 4 times.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  bool all_of(Rng&& rng, P p);
}

Parameters

• rng: Relaxed input range to process
• 'p': Predicate

Return value

true if unary p returns true for all elements in the range, false otherwise. Returns true if the range is empty.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <iostream>
#include <vector>
#include <tts/tts.hpp>
 
int main()
{
  std::vector<int>  v = {2,5,-9,3,-8,2,-5,7,-2,3};
 
  std::cout << " -> v                                  = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::all_of(v, i*i >= 4)     = "
            << std::boolalpha << eve::algo::all_of(v, [](auto i){ return i*i >= 4; })<< "\n";
 
  std::cout << " -> eve::algo::all_of(v, eve::is_ltz)  = "
            << std::boolalpha << eve::algo::all_of(v, eve::is_ltz)<< "\n";
 
  return 0;
}

any_of

auto eve::algo::any_of = function_with_traits<any_of_>[default_simple_algo_traits]

inlineconstexpr

a SIMD version of std::any_of

Tests if any of the elements in the range match the predicate. by default aligns and unrolls 4 times.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  bool any_of(Rng&& rng, P p);
}

Parameters

• rng: Relaxed input range to process
• 'p': Predicate

Return value

true if p returns true for at least one element in the range, false otherwise. Returns false if the range is empty.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <iostream>
#include <vector>
#include <tts/tts.hpp>
 
int main()
{
  std::vector<int>  v = {2,6,-10,32,-8,2,-6,8,-2,4};
 
  std::cout << " -> v                                  = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::any_of(v, i >= 4)       = "
            << std::boolalpha << eve::algo::any_of(v, [](auto i){ return i >= 4; })<< "\n";
 
  std::cout << " -> eve::algo::any_of(v, eve::is_odd)  = "
            << std::boolalpha << eve::algo::any_of(v, eve::is_odd)<< "\n";
  return 0;
}

copy

auto eve::algo::copy = function_with_traits<copy_>[default_simple_algo_traits]

inlineconstexpr

SIMD optimized copy algorithm.

Configurable Callable Object performing a SIMD optimized version of the copy. By default, the operation will be unrolled by a factor of 4, align memory accesses and perform conversions if needed.

Note

If you want to copy elements of same scalar type, use std::memmove.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template<typename R1, typename R2>
  void copy(R1&& r1, R2&& r2) requires zip_to_range<R1, R2>;    //  1
 
  void copy(zipped_range_pair auto&& r);                        //  2
}

1. Copy the elements of from r1 to r2.
2. Copy the elements of from get<0>(r) to get<1>(r).

Parameters

• r1 : The range of elements or an iterator to the beginning of the elements to copy from
• r2 : A range or an iterator to the beginning of the destination elements
• r : An eve::algo::zipped_range_pair of ranges and/or iterators.

Example

#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<double>  from_vector = {2.5,6.8,-10.62,3.2,-8.8,2.7,-6.66,8.5,-2.01,4.8};
  std::vector<double>  to_vector(from_vector.size());
  std::vector<double>  to_vector_z(from_vector.size());
 
  std::cout << "from_vector     = "
            << tts::as_string(from_vector)
            << "\n";
 
  eve::algo::copy(from_vector, to_vector);
 
  std::cout << "to_vector       = "
            << tts::as_string(to_vector)
            << "\n";
 
  eve::algo::copy( eve::algo::views::zip(from_vector, to_vector_z) );
 
  std::cout << "to_vector (zip) = "
            << tts::as_string(to_vector_z)
            << "\n";
 
  return 0;
}

copy_backward

auto eve::algo::copy_backward = function_with_traits<copy_backward_>[default_simple_algo_traits]

inlineconstexpr

SIMD optimized backward copy algorithm.

Configurable Callable Object performing backward copy between two ranges' or between a range and an iterator.

By default, eve::algo::copy_backward will be unrolled by a factor of 4, align memory accesses and perform conversions if needed.

Note

If you want to copy between ranges of the same scalar type, use std::memmove.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template<typename R1, typename R2>
  void copy_backward(R1&& r1, R2&& r2) requires zip_to_range<R1, R2>;    //  1
 
  void copy_backward(zipped_range_pair auto&& r);                        //  2
}

1. Copy the elements of from r1 to r2.
2. Copy the elements of from get<0>(r) to get<1>(r).

The elements are copied in reverse order (the last element is copied first), but their relative order is preserved. Due to the specificities of the SIMD algorithm, the second can not be an iterator. Use the zip based overload to do so.

Parameters

• r1 : The range of elements or an iterator to the beginning of the elements to copy from
• r2 : A range of the destination elements
• r : A eve::algo::zipped_range_pair of ranges and/or iterators.

Example

#include <eve/module/algo.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> from_vector = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> to_vector(15);
 
  eve::algo::copy_backward(from_vector, eve::algo::as_range(to_vector.end()-10, to_vector.end()) );
 
  std::cout << "from_vector     = "
            << tts::as_string(from_vector)
            << "\n";
 
  std::cout << "from_vector     = "
            << tts::as_string(to_vector)
            << "\n";
}

copy_if

auto eve::algo::copy_if = function_with_traits<copy_if_>

inlineconstexpr

SIMD variation on std::copy_if.

Defined in Header

#include <eve/module/algo.hpp>

Note

If you need to apply a transformation, you can use eve::algo::views::map or eve::algo::transform_copy_if.

The main difference from std::copy_if is that it accepts output range and not an output iterator. If the output doesn't have enough space, algorithm will fill all of the available output and then stop. The interface difference allows eve to store more then just selected elements which is important for efficiency.

Note

fix-1656: unfortunately at the moment, we only return where writing output finished. We should return where the input stopped too but we couldn't solve that efficiently so far.

Tuning:

• eve::algo::dense_output/eve::algo::sparse_output - if you expect very sparse output (one or two trues per register) - you can pass sparse_output to try to optimize for that.
• Does not support unrolling at the moment. In the exepriments with compress it didn't prove beneficial, but you can always try with eve::algo::for_each, assuming you can overallocate the output.
• Algorithm switches to a much slower version, when there is not enough space to write a full register. Allocating more than input size won't help though.

Callable Signatures

namespace eve::algo
{
   template<relaxed_range In, relaxed_range Out, typename P>
   auto copy_if(In&& in, Out&& out, P p) -> unaligned_iterator_t<Out>
}

** Parameters **

• in - relaxed_range input
• out - relaxed_range output
• p - simd prediocate for elements of in

** Return value **

relaxed_iterator past the last written element.

See also

keep_if

remove_if

transform_keep_if

transform_copy_if

equal

auto eve::algo::equal = function_with_traits<equal_>[all_of.get_traits()]

inlineconstexpr

a SIMD version of std::equal

Tests whether two ranges are equal (accepts anything that zips together as a range of 2 things) By default aligns and unrolls 4 times.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
 
  template <zipped_range_pair Rng>
  bool equal(Rng&& rng);                                             // 1
 
  template <zipped_range_pair Rng, typename P>
  bool equal(Rng&& rng, P p);                                        // 2
 
  template<typename R1, typename R2>
  bool equal(R1&& r1, R2&& r2) requires zip_to_range<R1, R2>;        // 3
 
  template<typename R1, typename R2, typename P>
  bool equal(R1&& r1, R2&& r2, P p) requires zip_to_range<R1, R2>;  // 4
}

1. Compare both halves of zipped_range_pair for equality
2. Compare both halves of zipped_range_pair for equivalence using predicate P
3. Compare r1 and r2 that zip together to zip_range_pair for equality
4. Compare r1 and r2 that zip together to zip_range_pair for equivalence using predicate P

Note

1. and 3. will convert to common type to do equality comparison if necessary to get the same for custom predicate, use [common_type] trait on your zip.

to better understand the zip interfaces, have a look at examples/algorithms/using_existing/memcmp_... or examples/algorithms/using_existing/case_insensitive....

Parameters

• rng: zipped pair of 2 ranges to compare
• r1, r2 - two separate components that zip to a zipped_range_pair
• p - binary predicate for equivalence testing.

Return value

bool whether any values matched the predicate

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <iostream>
#include <vector>
#include <tts/tts.hpp>
 
int main()
{
  std::vector<int>  v = {2,5,-9,3,-8,2,-5,7,-2,3};
  std::vector<int>  w = {-9,3,-8,2,2,5,-5,7,-2,3};
 
  std::cout << " -> v                       = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> w                       = "
            << tts::as_string(w)
            << "\n";
 
  std::cout << " -> eve::algo::equal(v, v)  = " << std::boolalpha << eve::algo::equal(v, v) << "\n";
  std::cout << " -> eve::algo::equal(v, w)  = " << std::boolalpha << eve::algo::equal(v, w) << "\n";
 
  return 0;
}

find

auto eve::algo::find = function_with_traits<find_>[find_if.get_traits()]

inlineconstexpr

a version of find_if with a value to find instead of a predicate to test.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng>
  auto find(Rng&& rng, eve::value_type_t<Rng> v) -> unaligned_iterator_t<Rng>;
}

Parameters

• rng: Relaxed input range to process
• 'v': value to find

Return value

Iterator on the element found or past the end if not found (same as std)

See also

find_if

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> v{12, 0, 5, -9, 3, 0, 5};
 
  std::cout << " -> v                                               = "
            << tts::as_string(v)
            << "\n";
 
  auto pos   = eve::algo::find_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_if(v, eve::is_eqz) - v.begin()  = " << pos - v.begin()   << "\n";
 
  auto posn  = eve::algo::find_if_not(v, [](auto x){return x < 0; });
  std::cout << " <- eve::algo::find_if_not(v, x < 0) - v.begin()    = " << posn - v.begin()  << "\n";
 
  auto pos_v = eve::algo::find(v, 5);
  std::cout << " <- eve::algo::find(v, 5) - v.begin()               = " << pos_v - v.begin() << "\n";
 
  return 0;
}

find_if

auto eve::algo::find_if = function_with_traits<find_if_>[default_simple_algo_traits]

inlineconstexpr

SIMD version of std::find_if.

Configurable Callable Object performing a SIMD optimized version of the find_if By default, the operation will be unrolled by a factor of 4, and align memory accesses.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  auto find_if(Rng&& rng, P p) -> unaligned_iterator_t<Rng>;
}

Parameters

• rng: Relaxed input range to process
• 'p': predicate, if true - we found the value.

Return value

Iterator on the element found or past the end if not (same as std)

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> v{12, 0, 5, -9, 3, 0, 5};
 
  std::cout << " -> v                                               = "
            << tts::as_string(v)
            << "\n";
 
  auto pos   = eve::algo::find_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_if(v, eve::is_eqz) - v.begin()  = " << pos - v.begin()   << "\n";
 
  auto posn  = eve::algo::find_if_not(v, [](auto x){return x < 0; });
  std::cout << " <- eve::algo::find_if_not(v, x < 0) - v.begin()    = " << posn - v.begin()  << "\n";
 
  auto pos_v = eve::algo::find(v, 5);
  std::cout << " <- eve::algo::find(v, 5) - v.begin()               = " << pos_v - v.begin() << "\n";
 
  return 0;
}

find_if_not

auto eve::algo::find_if_not = function_with_traits<find_if_not_>[find_if.get_traits()]

inlineconstexpr

a version of eve::algo::find_if where the preicate is negated

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  auto find_if_not(Rng&& rng, P p) -> unaligned_iterator_t<Rng>;
}

Parameters

• rng: Relaxed range input range to process
• 'p': Predicate to invert and use

Return value

Iterator on the element found or past the end if not found (same as std)

See also

find_if

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> v{12, 0, 5, -9, 3, 0, 5};
 
  std::cout << " -> v                                               = "
            << tts::as_string(v)
            << "\n";
 
  auto pos   = eve::algo::find_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_if(v, eve::is_eqz) - v.begin()  = " << pos - v.begin()   << "\n";
 
  auto posn  = eve::algo::find_if_not(v, [](auto x){return x < 0; });
  std::cout << " <- eve::algo::find_if_not(v, x < 0) - v.begin()    = " << posn - v.begin()  << "\n";
 
  auto pos_v = eve::algo::find(v, 5);
  std::cout << " <- eve::algo::find(v, 5) - v.begin()               = " << pos_v - v.begin() << "\n";
 
  return 0;
}

find_last

auto eve::algo::find_last = function_with_traits<find_last_>[find_last_if.get_traits()]

inlineconstexpr

a version of find_last_if with a value to find instead of a predicate to test.

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng>
  auto find_last(Rng&& rng, eve::value_type_t<Rng> v) -> unaligned_iterator_t<Rng>;
}

Parameters

• rng: Relaxed input range to process
• 'v': value to find

Return value

Iterator on the element found or past the end if not found

See also

find_if

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> v{12, 0, 5, -9, 3, 0, 5};
 
  std::cout << " -> v                                                        = "
            << tts::as_string(v)
            << "\n";
 
  auto pos   = eve::algo::find_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_if(v, eve::is_eqz) - v.begin()           = " << pos - v.begin()   << "\n";
 
  auto pos_b = eve::algo::find_last_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_last_if(v, eve::is_eqz) - v.begin()  = " << pos_b - v.begin()   << "\n";
 
  auto pos_bn  = eve::algo::find_last_if_not(v, [](auto x){return x < 0; });
  std::cout << " <- eve::algo::find_last_if_not(v, x < 0) - v.begin()    = " << pos_bn - v.begin()  << "\n";
 
  auto pos_bv = eve::algo::find_last(v, 5);
  std::cout << " <- eve::algo::find_last(v, 5) - v.begin()               = " << pos_bv - v.begin() << "\n";
 
  return 0;
}

find_last_if

auto eve::algo::find_last_if = function_with_traits<find_last_if_>[default_simple_algo_traits]

inlineconstexpr

SIMD version of std::ranges::find_last_if.

Configurable Callable Object performing a SIMD optimized version of the std::ranges::find_last_if By default, the operation will be unrolled by a factor of 4, and align memory accesses.

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  auto find_last_if(Rng&& rng, P p) -> unaligned_iterator_t<Rng>;
}

Parameters

• rng: Relaxed input range to process
• 'p': predicate, if true - we found the value.

Return value

Iterator on the element found or past the end if nothing was found.

See also

find_if

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> v{12, 0, 5, -9, 3, 0, 5};
 
  std::cout << " -> v                                                        = "
            << tts::as_string(v)
            << "\n";
 
  auto pos   = eve::algo::find_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_if(v, eve::is_eqz) - v.begin()           = " << pos - v.begin()   << "\n";
 
  auto pos_b = eve::algo::find_last_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_last_if(v, eve::is_eqz) - v.begin()  = " << pos_b - v.begin()   << "\n";
 
  auto pos_bn  = eve::algo::find_last_if_not(v, [](auto x){return x < 0; });
  std::cout << " <- eve::algo::find_last_if_not(v, x < 0) - v.begin()    = " << pos_bn - v.begin()  << "\n";
 
  auto pos_bv = eve::algo::find_last(v, 5);
  std::cout << " <- eve::algo::find_last(v, 5) - v.begin()               = " << pos_bv - v.begin() << "\n";
 
  return 0;
}

find_last_if_not

auto eve::algo::find_last_if_not = function_with_traits<find_last_if_not_>[find_last_if.get_traits()]

inlineconstexpr

a version of find_last_if where the preicate is negated

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  auto find_if_not(Rng&& rng, P p) -> unaligned_iterator_t<Rng>;
}

Parameters

• rng: Relaxed range input range to process
• 'p': Predicate to invert and use

Return value

Iterator on the element found or past the end if not found

See also

find_if

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> v{12, 0, 5, -9, 3, 0, 5};
 
  std::cout << " -> v                                                        = "
            << tts::as_string(v)
            << "\n";
 
  auto pos   = eve::algo::find_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_if(v, eve::is_eqz) - v.begin()           = " << pos - v.begin()   << "\n";
 
  auto pos_b = eve::algo::find_last_if(v, eve::is_eqz);
  std::cout << " <- eve::algo::find_last_if(v, eve::is_eqz) - v.begin()  = " << pos_b - v.begin()   << "\n";
 
  auto pos_bn  = eve::algo::find_last_if_not(v, [](auto x){return x < 0; });
  std::cout << " <- eve::algo::find_last_if_not(v, x < 0) - v.begin()    = " << pos_bn - v.begin()  << "\n";
 
  auto pos_bv = eve::algo::find_last(v, 5);
  std::cout << " <- eve::algo::find_last(v, 5) - v.begin()               = " << pos_bv - v.begin() << "\n";
 
  return 0;
}

for_each

auto eve::algo::for_each = function_with_traits<for_each_>

inlineconstexpr

a basic for_each algorithm.

• The operation is called with iterator and ignore.
• Result of the operation is ignored.
• Operation is passed by value.
• There is no default traits.
• We do not return anything.
• The unrolling just calls the single step.
• Will align by default.

If you have a more advanced unrolling, consider using the for_each_iteration.

Required header: #include <eve/module/algo/algo/for_each.hpp>

[struct]

struct { ... } eve::algo::for_each_iteration_with_expensive_optional_part

low level util for writing algorithms. A variation on for_each_iteration that has a place for work we don't want duplicated in assembly.

Defined in Header

#include <eve/module/algo.hpp>

for_each_iteration, even if not unrolled, generates a few copies of the callback code. For some algorithms we want to move out a piece of callback code but we still don't want a function call. Think search: we want to move the more expensive part of validating match outside.

You can find example usage in the search implementation.

for_each_selected

auto eve::algo::for_each_selected = function_with_traits<for_each_selected_>

inlineconstexpr

an algorithm to perform some scalar operation for every element, that matches a given SIMD predicate. Defined in Header

#include <eve/module/algo.hpp>

The scalar equivalent of this algorithm would be:

bool for_each_selected(std::ranges::forward_range auto&& r,
                       auto is_selected,
                       auto&& loop_body) {
  for (auto f = std::ranges::begin(r); f != std::ranges::end(r); ++f) {
    if (is_selected(*f) && loop_body(f)) {
      return true;
    }
  }
  return false;
}

Callable Signatures

namespace eve::algo
{
  template<relaxed_range Rng, typename P, irregular_predicate<unaligned_iterator_t<Rng>> LoopBody>
  bool for_each_selected(Rng&& rng, P is_selected, LoopBody loop_body);
}

Parameters

• rng - relaxed range which we iterate
• is_selected - simd predicate to check values
• loop_body - operation to perform for each value (should return true to break),

Return value

returns true iff the iteration was interrupted.

Example

#include <eve/module/algo.hpp>
#include <eve/module/core.hpp>
 
#include <iostream>
#include <vector>
 
#include <span>
#include <string_view>
#include <tts/tts.hpp>
 
std::vector<std::string_view>
split_by(std::string_view s, char by)
{
  std::vector<std::string_view> res;
  std::string_view::iterator    last = s.begin();
 
  auto maybe_add_a_string = [&](std::string_view::iterator it) {
    // skipping empty
    if( it != last ) res.push_back({last, it});
  };
 
  // arm has weird char type, so we cast.
  std::span<const std::uint8_t> us{ (const std::uint8_t*) s.data(), s.size() };
 
  eve::algo::for_each_selected(
      us,
      [&](auto x) { return x == (std::uint8_t)by; },
      [&](std::span<const std::uint8_t>::iterator us_it)
      {
        auto it = s.begin() + (us_it - us.begin());
        maybe_add_a_string(it);
        last = it + 1;
        return false;  // return true here if you want to break.
      });
  maybe_add_a_string(s.end());
 
  return res;
}
 
int
main()
{
  std::string_view in = "Words shall be    split   !";
  std::cout << " -> in    = "
            << in
            << "\n";
  std::cout << " -> split = "
            << tts::as_string(split_by(in, ' '))
            << "\n";
}

iota

auto eve::algo::iota = function_with_traits<iota_>[copy.get_traits()]

inlineconstexpr

SIMD version of std::iota For conversion/overflow behaviour, should follow the standard.

Required header: #include <eve/module/algo/algo/iota.hpp>

keep_if

auto eve::algo::keep_if = function_with_traits<keep_if_>[no_traits]

inlineconstexpr

In-place version of std::copy_if.

Defined in Header

#include <eve/module/algo.hpp>

Takes values that pass the predicate, and copies them to the beginning of the range. Values past the returned sentinel are to be considered garbage.

Acts like an eager version of filter, or an in-place version of std::copy_if:

std::copy_if(r.begin(), r.end(), r.begin(), predicate);

Note

If you need to apply a transformation, you can use eve::algo::views::map or eve::algo::transform_keep_if.

Tuning

::dense_output/::sparse_output: if you expect very sparse output (one or two trues per register), you can call ::keep_if[::sparse_output](...) to optimize for that scenario.

Callable Signatures

{
  template<relaxed_range Rng, typename P>
  auto keep_if(Rng&& rng, P p) -> unaligned_iterator_t<Rng>
}

Parameters

• rng: Range to modify
• p: SIMD predicate over elements of rng

Return value

Iterator past the last written element.

See also

copy_if

remove_if

transform_keep_if

transform_copy_if

max_element

auto eve::algo::max_element = function_with_traits<max_element_>[default_simple_algo_traits]

inlineconstexpr

SIMD variation on std::max_element not exact match.

Note

if you just need a value and not position, use eve::algo::max_value.

By default unrolls by 4 and aligned all memory accesses.

Note

for equivalent elements we return the second among equal. std::max_element returns first but this is more correct and this is also what std::minmax_element will return as max.

we assume that eve::is_less defined for your type is total order. (this comes up when switching min with max)

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
   template<relaxed_range Rng, typename Less>
   auto max_element(Rng&& rng, Less less) -> unaligned_iterator_t<Rng>;   // 1
 
   template<relaxed_range Rng>
   auto max_element(Rng&& rng) -> unaligned_iterator_t<Rng>;            // 2
}

1. Returns the position of a maximum value, according to less. If the range is empty - returns past the end.
2. Same as 1 but the less is eve::is_less

Parameters

• rng: Relaxed input range to process
• less: SIMD strict weak ordering.

Return value

iterator to max element (end if the range is empty).

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>  // as_string
#include <vector>
 
int main()
{
  std::vector<int> v{ 2, 4, -1, 4, 0, 1 };
 
  std::cout << " -> v                                                       = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::max_value(v)                                 = "
            << *eve::algo::max_value(v) << "\n";
 
  std::cout << " -> eve::algo::max_element(v) - v.begin()                   = "
            << eve::algo::max_element(v) - v.begin() << "\n";
 
  std::cout << " -> eve::algo::max_value(v, eve::is_greater)                = "
            << *eve::algo::max_value(v, eve::is_greater) << "\n";
 
  std::cout << " -> eve::algo::max_value(v, eve::is_greater) - v.begin()    = "
            << eve::algo::max_element(v, eve::is_greater) - v.begin() << "\n";
}

See also

max_value

min_element

max_value

auto eve::algo::max_value = function_with_traits<max_value_>[default_simple_algo_traits]

inlineconstexpr

SIMD algorithm that returns maximum value in the range.

The standard only has _element versions of min/max algorithms. However, in SIMD finding the value is much faster then also finding the position - hence this algorithm.

Note

for equivalent elements we return the second among equal.

we assume that eve::is_less defined for your type is total order. (this comes up when switching max with min)

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename Less>
  std::optional<eve::value_type_t<Rng>> max_value(Rng&& rng, Less less);          // 1
 
  template <eve::algo::relaxed_range Rng>
  std::optional<eve::value_type_t<Rng>> max_value(Rng&& rng);                    // 2
}

1. Returns the maximum value, according to less. If the range is empty - returns nullopt.
2. Same as 1 but the less is eve::is_less

Parameters

• rng: Relaxed input range to process
• less: SIMD strict weak ordering.

Return value

maximum value from the range. If the input range was empty, it's std::nullopt.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>  // as_string
#include <vector>
 
int main()
{
  std::vector<int> v{ 2, 4, -1, 4, 0, 1 };
 
  std::cout << " -> v                                                       = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::max_value(v)                                 = "
            << *eve::algo::max_value(v) << "\n";
 
  std::cout << " -> eve::algo::max_element(v) - v.begin()                   = "
            << eve::algo::max_element(v) - v.begin() << "\n";
 
  std::cout << " -> eve::algo::max_value(v, eve::is_greater)                = "
            << *eve::algo::max_value(v, eve::is_greater) << "\n";
 
  std::cout << " -> eve::algo::max_value(v, eve::is_greater) - v.begin()    = "
            << eve::algo::max_element(v, eve::is_greater) - v.begin() << "\n";
}

See also

min_value

max_element

min_element

auto eve::algo::min_element = function_with_traits<min_element_>

inlineconstexpr

SIMD version of std::min_element.

Note

for equivalent elements we return the first among equal.

we assume that eve::is_less defined for your type is total order. (this comes up when switching min with max)

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
   template<relaxed_range Rng, typename Less>
   auto min_element(Rng&& rng, Less less) -> unaligned_iterator_t<Rng>;   // 1
 
   template<relaxed_range Rng>
   auto min_element(Rng&& rng) -> unaligned_iterator_t<Rng>;            // 2
}

1. Returns the position of a minimum value, according to less. If the range is empty - returns past the end.
2. Same as 1 but the less is eve::is_less

Parameters

• rng: Relaxed input range to process
• less: SIMD strict weak ordering.

Return value

iterator to min element (end if the range is empty).

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>  // as_string
#include <vector>
 
int main()
{
  std::vector<int> v{ 2, -1, 4, -1, 0 };
 
  std::cout << " -> v                                                                              = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::min_value(v)                                                       = "
            << *eve::algo::min_value(v) << "\n";
 
  std::cout << " -> eve::algo::min_element(v) - v.begin()                                         = "
            << eve::algo::min_element(v) - v.begin() << "\n";
 
  std::cout << " -> eve::algo::min_value(v, eve::is_greater)                                      = "
            << *eve::algo::min_value(v, eve::is_greater) << "\n";
 
  std::cout << " -> eve::algo::min_value(v, eve::is_greater) - v.begin()                          = "
            << eve::algo::min_element(v, eve::is_greater) - v.begin() << "\n";
 
 
  auto absolutes = eve::views::map(v, eve::abs);
  std::cout << " -> eve::algo::min_element[eve::algo::single_pass](absolutes) - absolutes.begin() = "
            << eve::algo::min_element[eve::algo::single_pass](absolutes) - absolutes.begin() << "\n";
 
}

See also

min_value

max_element

Note

if you just need a value and not position, use eve::algo::min_value.

Can be one of two algorithms: one pass and two pass (default).

Two pass finds a value and then does a linear search for the value. This proves to be faster on smaller simpler arrays. By default unrolls by 4 and aligned all memory accesses.

The one pass version keeps track of index and is better suited for complicated predicates. You can opt in by using single_pass or expensive_callable traits. The single_pass opt-in will be aligning all data accesses

min_value

auto eve::algo::min_value = function_with_traits<min_value_>[default_simple_algo_traits]

inlineconstexpr

SIMD algorithm that returns minimum value in the range.

C++ standard only has std::min_element that returns iterator to the minimum element. We have that too (see: eve::algo::min_element) but it's slower then just getting the value. So we also provide min_value for when you don't care about the position. By default unrolls by 4 and aligned all memory accesses.

Note

for equivalent elements we return the first among equal.

we assume that eve::is_less defined for your type is total order. (this comes up when switching min with max)

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename Less>
  std::optional<eve::value_type_t<Rng>> min_value(Rng&& rng, Less less);          // 1
 
  template <eve::algo::relaxed_range Rng>
  std::optional<eve::value_type_t<Rng>> min_value(Rng&& rng);                    // 2
}

1. Returns the minimum value, according to less. If the range is empty - returns nullopt.
2. Same as 1 but the less is eve::is_less

Parameters

• rng: Relaxed input range to process
• less: SIMD strict weak ordering.

Return value

minimum value from the range. If the input range was empty, it's std::nullopt.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>  // as_string
#include <vector>
 
int main()
{
  std::vector<int> v{ 2, -1, 4, -1, 0 };
 
  std::cout << " -> v                                                                              = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::min_value(v)                                                       = "
            << *eve::algo::min_value(v) << "\n";
 
  std::cout << " -> eve::algo::min_element(v) - v.begin()                                         = "
            << eve::algo::min_element(v) - v.begin() << "\n";
 
  std::cout << " -> eve::algo::min_value(v, eve::is_greater)                                      = "
            << *eve::algo::min_value(v, eve::is_greater) << "\n";
 
  std::cout << " -> eve::algo::min_value(v, eve::is_greater) - v.begin()                          = "
            << eve::algo::min_element(v, eve::is_greater) - v.begin() << "\n";
 
 
  auto absolutes = eve::views::map(v, eve::abs);
  std::cout << " -> eve::algo::min_element[eve::algo::single_pass](absolutes) - absolutes.begin() = "
            << eve::algo::min_element[eve::algo::single_pass](absolutes) - absolutes.begin() << "\n";
 
}

See also

max_value

min_element

mismatch

auto eve::algo::mismatch = function_with_traits<mismatch_>[find_if.get_traits()]

inlineconstexpr

a SIMD version of std::mismatch

Finds the point where two ranges are different (accepts anything that zips together as a range of 2 things). By default aligns and unrolls 4 times.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
 
  template <zipped_range_pair Rng>
  auto mismatch(Rng&& rng) -> unalinged_t<decltype(rng.begin())>;       // 1
 
  template <zipped_range_pair Rng, typename P>
  auto mismatch(Rng&& rng, P p) -> unalinged_t<decltype(rng.begin())>;  // 2
 
  template<typename R1, typename R2>
  auto mismatch(R1&& r1, R2&& r2) requires zip_to_range<R1, R2>         // 3
     -> eve::views::zip_iterator;
 
  template<typename R1, typename R2, typename P>
  auto mismatch(R1&& r1, R2&& r2, P p) requires zip_to_range<R1, R2>    // 4
     -> eve::views::zip_iterator;
}

1. Compare both halves of zipped_range_pair for equality
2. Compare both halves of zipped_range_pair for equivalence using predicate P
3. Compare r1 and r2 that zip together to zip_range_pair for equality
4. Compare r1 and r2 that zip together to zip_range_pair for equivalence using predicate P

Note

1. and 3. will convert to common type to do equality comparison if necessary to get the same for custom predicate, use [common_type] trait on your zip.

to better understand the zip interfaces, have a look at examples/algorithms/using_existing/memcmp_... or examples/algorithms/using_existing/case_insensitive....

Parameters

• rng: zipped pair of 2 ranges to compare
• r1, r2 - two separate components that zip to a zipped_range_pair
• p - binary predicate for equivalence testing.

Return value

eve::views::zip_iterator to the place where the mismatch happened. (if not found, will point past the end of both halves).

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <iostream>
#include <vector>
#include <tts/tts.hpp>
 
int main()
{
  std::vector<int>  v = {2,5,-9,  9,  3,-8,2,-5,7,-2,3};
  std::vector<int>  w = {2,5,-9, -9, -9,-8,2,-5,7,-2,3};
 
  std::cout << " -> v                             = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> w                             = "
            << tts::as_string(w)
            << "\n";
 
  auto [vv, ww] = eve::algo::mismatch(v, w);
  std::cout << " <- auto [vv, ww]                 = eve::algo::mismatch(v, ww);\n";
  std::cout << " -> mismatch at " << eve::read(vv) << " != " << eve::read(ww) << std::endl;
 
  // ignoring sign
  auto [no_sign_vv, no_sign_ww] = eve::algo::mismatch(v, w, [](auto x, auto y) {
    return x == y || x == -y;
  });
 
  std::cout << " <- auto [no_sign_vv, no_sign_ww] = eve::algo::mismatch(v, w, [](...){ });\n";
  std::cout << " -> mismatch at " << eve::read(no_sign_vv) << " != " << eve::read(no_sign_ww) << std::endl;
}

none_of

auto eve::algo::none_of = function_with_traits<none_of_>

inlineconstexpr

a SIMD version of std::none_of

Tests if none of the elements in the range match the predicate. by default aligns and unrolls 4 times.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename P>
  bool none_of(Rng&& rng, P p);
}

Parameters

• rng: Relaxed input range to process
• 'p': Predicate

Return value

true if p returns true for no elements in the range, false otherwise. Returns true if the range is empty.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <iostream>
#include <vector>
#include <tts/tts.hpp>
 
int main()
{
  std::vector<int>  v = {2,5,-9,3,-8,2,-5,7,-2,3};
 
  std::cout << " -> v                                   = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::none_of(v, i == 0)       = "
            << std::boolalpha << eve::algo::none_of(v, [](auto i){ return i == 0; })<< "\n";
 
  std::cout << " -> eve::algo::none_of(v, eve::is_ltz)  = "
            << std::boolalpha << eve::algo::none_of(v, eve::is_ltz)<< "\n";
 
  return 0;
}

reduce

auto eve::algo::reduce = function_with_traits<reduce_>[default_simple_algo_traits]

inlineconstexpr

SIMD optimized version of std::reduce.

Configurable Callable Object performing a SIMD optimized version of the reduce By default, the operation will be unrolled by a factor of 4, align memory accesses and perform conversions if needed.

Due to the nature of how SIMD algorithms work, the reduce operation has to be paired with its, neutral element. For example, for add you pass {add, zero} as zero is the identity for add. Instead of zero it can be beneficial to pass eve's constants like eve::zero, eve::one because sometimes the implementation can be improved

Note

• The interface differs from the standard to be homogeneous with eve::algo::transform_reduce.
• Compilers can auto-vectorize reductions, especially with special options. Maybe you don't need a library implementation.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename U>
  U reduce(Rng&& rng, U init);                              // 1
 
  template <eve::algo::relaxed_range Rng, typename Op, typename Zero, typename U>
  U reduce(Rng&& rng, std::pair<Op, Zero> op_zero, U init)  // 2
}

1. Reduces the range rng along with the initial value init using regular addition.
2. Reduces the range rng along with the initial value init over op_zero.

Parameters

• rng: Relaxed range input range to process
• init: Initial value. Also type of init matches the result type
• op_zero: Pair of reduction operation (commutative/associative) and an identity (zero) for it. Default add_zero is {eve::add, eve::zero}.

Return value

1. Sum of init and every elements of rng.
2. Generalized sum of init and every elements of rng using op_zero.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <numeric>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<double>  v = {1.2,2.3,3.4,4.5,5.6,6.7};
 
  std::cout << " -> v                                                        = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::reduce(v, 0.)                                 = "
            << eve::algo::reduce(v, 0.) << "\n";
 
  std::cout << " -> eve::algo::reduce(v, std::pair{eve::mul, 1.}, 1.)        = "
            << eve::algo::reduce(v, std::pair{eve::mul, 1.}, 1.) << "\n";
 
  std::cout << " -> std::reduce(v.begin(), v.end(), 1., std::multiplies<>{}) = "
            << std::reduce(v.begin(), v.end(), 1., std::multiplies<>{}) << "\n";
 
  return 0;
}

remove

auto eve::algo::remove = function_with_traits<remove_>[no_traits]

inlineconstexpr

SIMD version of std::remove.

Defined in Header

#include <eve/module/algo.hpp>

TODO: docs

remove_if

auto eve::algo::remove_if = function_with_traits<remove_if_>[no_traits]

inlineconstexpr

SIMD version of std::remove_if.

Defined in Header

#include <eve/module/algo.hpp>

TODO: docs

See also

keep_if

copy_if

transform_keep_if

transform_copy_if

reverse

auto eve::algo::reverse = function_with_traits<reverse_>[no_unrolling][no_aligning]

inlineconstexpr

SIMD version of std::reverse.

• default unrolling is 1.
• will won't align because it makes the logic more complex and does not win.

Required header: #include <eve/module/algo/algo/reverse.hpp>

reverse_copy

auto eve::algo::reverse_copy = function_with_traits<reverse_copy_>[algo::unroll<1>]

inlineconstexpr

SIMD version of std::reverse_copy.

• Accepts two things zipping together to range of pair.
• Also can accept a zipped_range_pair.
• returns void.
• default unrolling is 1.
• will align by default.
• will do conversions if necessary.

NOTE: reverese_copy(it, range) works but it's the same as reverse_copy(views::zip(it, range)), so it will be treated as first not last.

Required header: #include <eve/module/algo/algo/reverse.hpp>

search

auto eve::algo::search = function_with_traits<search_>[eve::algo::unroll<4>]

inlineconstexpr

SIMD version of std::search (subsequence in a sequence).

Defined in Header

#include <eve/module/algo.hpp>

Some ideas are taken from the previous work:

• Wojciech Mula: http://0x80.pl/articles/simd-strfind.html
• Ash Vardanian: https://github.com/ashvardanian/StringZilla/blob/07e0a2a4ad8330c91a20fccb66022715b386e1b4/include/stringzilla/stringzilla.h#L3784
• strstr from glibc: https://codebrowser.dev/glibc/glibc/sysdeps/x86_64/multiarch/strstr-sse2-unaligned.S.html

Note

: to look for one element use eve::algo::find. It is also slightly faster, so if one element case is common - you might consider an if on the needle len.

Tuning:

• Aligning search for initial test. Passing no_aligning will remove this aligning.
• Unrolling search for initial test. By default we unroll 4 times, with expensive predicates might not be beneficial

Callable Signatures

namespace eve::algo
{
    template<relaxed_range R1, relaxed_range R2, typename Equal>
    auto search(R1&& haystack, R2&& needle, Equal equal)  // (1)
      -> unaligned_iterator_t<R1>
 
    template<relaxed_range R1, relaxed_range R2>
    auto search(R1&& haystack, R2&& needle)  // (2)
      -> unaligned_iterator_t<R1>
}

(2) calls (1) with eve::is_equal. In order to mimic the behaviour of std::search, it will also cast the types, so that you can search unrelated types.

Version (1) won't do implicit types conversions for you, you can either handle them in the predicate or use views::convert.

Parameters (1)

• haystack - where we search the subsequence.
• needle - the subsequence we are searching for.
• equal - the predicate of the elements.

Return value

unaligned iterator pointing to where in haystack the sequence is.
If the needle is empty found == haystack.begin() is returned.
If the needle isn't found == haystack.end().

Example

#include <eve/module/algo.hpp>
#include <eve/module/core.hpp>
 
#include <span>
#include <vector>
 
#include <string_view>
#include <iostream>
 
std::ptrdiff_t
substring_in_string(std::string_view haystack, std::string_view needle)
{
  // NOTE: eve is not supporting `char` directly, you need to use int8_t or uint8_t
  std::span h(reinterpret_cast<const std::uint8_t *>(haystack.data()), haystack.size());
  std::span n(reinterpret_cast<const std::uint8_t *>(needle.data()), needle.size());
 
  auto res = eve::algo::search(h, n);
  return res - h.begin();
}
 
void
basic_example()
{
  std::cout << __func__ << std::endl;
  std::string_view haystack("one two three");
 
  std::cout << "empty: " << substring_in_string(haystack, "") << std::endl;
  std::cout << "one: " << substring_in_string(haystack, "one") << std::endl;
  std::cout << "two: " << substring_in_string(haystack, "two") << std::endl;
  std::cout << "three: " << substring_in_string(haystack, "three") << std::endl;
  std::cout << "not there: " << substring_in_string(haystack, "not there") << std::endl;
 
  std::cout << "<<<<<<<\n" << std::endl;
}
 
void
implicit_conversions()
{
  std::cout << "<<< " << __func__ << " <<<" << std::endl;
 
  std::vector<double>      haystack {0.0, 1.0, 2.0, 3.0, 4.0, 5.0};
  std::vector<std::int8_t> needle {2, 3};
 
  std::cout << "chars in doubles: " << (eve::algo::search(haystack, needle) - haystack.begin())
            << std::endl;
 
  std::cout << "<<<<<<<\n" << std::endl;
}
 
std::ptrdiff_t
substring_in_string_case_insensitive(std::string_view haystack, std::string_view needle)
{
  // NOTE: eve is not supporting `char` directly, you need to use int8_t or uint8_t
  std::span h(reinterpret_cast<const std::uint8_t *>(haystack.data()), haystack.size());
  std::span n(reinterpret_cast<const std::uint8_t *>(needle.data()), needle.size());
 
  // @the-moisrex provided this. See `case_insensitive_equals.cpp` for details.
  auto to_upper = [](eve::like<std::uint8_t> auto c)
  {
    constexpr std::uint8_t alphabet_length = 'z' - 'a';
    constexpr std::uint8_t a_A_offset      = 'a' - 'A';
 
    return eve::sub[(c - std::uint8_t('a')) <= alphabet_length](c, a_A_offset);
  };
 
  // NOTE: we could also use views::map
  return eve::algo::search(h, n, [&](auto x, auto y) { return to_upper(x) == to_upper(y); })
         - h.begin();
}
 
void
custom_predicates()
{
  std::cout << "<<< " << __func__ << " <<<" << std::endl;
 
  std::cout << "substring_in_string_case_insensitive: "
            << substring_in_string_case_insensitive("Uabc Ab", "C A") << std::endl;
  std::cout << "substring_in_string_case_insensitive: "
            << substring_in_string_case_insensitive("Uabc Ab", "Ab") << std::endl;
 
  std::cout << "<<<<<<<\n" << std::endl;
}
 
int
main()
{
  basic_example();
  implicit_conversions();
  custom_predicates();
}

set_intersection

auto eve::algo::set_intersection = function_with_traits<set_intersection_>

inlineconstexpr

SIMD variation on std::set_intersection that HAS A SLIGHTLY DIFFERENT SEMANTICS.

Defined in Header

#include <eve/module/algo.hpp>

The main idea for the algorithm comes from "Faster-Than-Native Alternatives for x86 VP2INTERSECT Instructions" by Guillermo Diez-Canas. Link: https://arxiv.org/abs/2112.06342

Differences:

• duplicate handling, eve::algo::set_intersection does not guarantee how many copies of a duplicated element will be in the output. Example: [a, a] intersect with [a, a, a] might produce [a], [a, a] and [a, a, a].
• we require both "Less" and "Equal" predicates, unlike std getting equal from less will be expensive.
• eve requires an output range instead of an output iterator. eve will do checks that there is enough output space and if there isn't, it will stop. If the algorithm stopped because of insufficient output space, the return value will contain where it stopped - (in1, in2) will point past the last written duplicate. TODO(#1630): provide support for output overallocation.

Other:

• Less and Equal have to be semantically compatible
• Eve always writes from the first range in case of equivalent elements. If eve::is_less/is_greater and eve::is_equal are passed in, elements are considered to be equal and eve can write from either range.

Tuning:

• Has expect_smaller_range<0>, expect_smaller_range<1> variations. These use combined simd/scalar approach. Since the problem is very data dependent, you want to measure for your usecase.
• Version expect_smaller_range<0> can be slightly faster, eve can't always use that due to a stability requirement but you might want to swap your inputs.
• The provided solution is minimal, eve won't search for beginning of intersection in any way. eve also won't do any dispatch based on size. If this is something that can be beneficial for your case - consider it.
• sparse_output/dense_output - controls which eve::algo::compress_copy is used, default is dense.
• Basic version does not support aligning/unrolling. expect_smaller_range do.

Callable Signatures

namespace eve::algo
{
  template<relaxed_range R1, relaxed_range R2, relaxed_range RO, typename Less, typename
  Equal> auto set_intersection(R1&& r1, R2&& r2, RO&& ro, Less less, Equal equal)  // (1)
    -> set_intersection_result<unaligned_iterator_t<R1>,
                               unaligned_iterator_t<R2>,
                               unaligned_iterator_t<RO>>
 
  template<relaxed_range R1, relaxed_range R2, relaxed_range RO>
  auto set_intersection(R1&& r1, R2&& r2, RO&& ro)                          // (2)
    -> set_intersection_result<unaligned_iterator_t<R1>,
                               unaligned_iterator_t<R2>,
                               unaligned_iterator_t<RO>>
}

(2) calls (1) with eve::is_less, eve::is_equal and converting to common type.

Parameters (1)

• r1, r2 - relaxed ranges to intersect
• ro - output relaxed range
• less - simd strict weak ordering for elements from r1 and r2
• equal - simd predicate for equivalence, compatible with less.

Return value

set_intersection{ .in1, .in2, .out }.

• if ro had enough space for all common elements - .in1 == r1.end(), .in2 == r2.end(), .out is an iterator in ro past the last written elements (same as std::set_intersection)
• if we ran out of space in ro before finishing the algorithm, .in1 and .in2 will point to positions past the last common element. .out == ro.end()

Example

#include <eve/module/algo.hpp>
#include <eve/module/core.hpp>
 
#include <numeric>
#include <iostream>
#include <utility>
#include <vector>
 
#include <tts/tts.hpp>
 
void
basic_example()
{
  std::cout << "basic =================\n";
 
  std::vector<int> v1 {1, 3, 5, 7};
  std::vector<int> v2 {2, 3, 4, 5, 6};
  std::vector<int> r;
 
  /*
   * The basic case, where output has guaranteed enough space
   * for the intersected elements.
   *
   * We will see all of the common elements in the output.
   * in1, in2 equal to the v1.end(), v2.end()
   */
  r.resize(v1.size());
  r.erase(eve::algo::set_intersection(v1, v2, r).out, r.end());
  TTS_EQUAL(r, (std::vector{3, 5}));
 
  std::cout << "-> v1:" << tts::as_string(v1) << '\n';
  std::cout << "-> v2:" << tts::as_string(v2) << '\n';
  std::cout << "-> r: " << tts::as_string(r) << '\n';
}
 
void not_enough_space_example()
{
  std::cout << "not enough space ====================\n";
 
  std::vector<int> v1 {1, 3, 5, 7};
  std::vector<int> v2 {2, 3, 4, 5, 6};
  std::vector<int> r;
 
  /*
   * The not enough space case - we will stop whe the output
   * runs out.
   *
   * in1 and in2 will be after the last common element.
   */
  r.resize(1);
  auto [in1, in2, out] = eve::algo::set_intersection(v1, v2, r);
 
  TTS_EQUAL(r, std::vector{3});
  TTS_EQUAL(*in1, 5);
  TTS_EQUAL(*in2, 4);
  TTS_EQUAL(out, r.end());
 
  std::cout << "r:             " << tts::as_string(r) << "\n";
  std::cout << "*in1:          " << *in1 << "\n";
  std::cout << "*in2:          " << *in2 << "\n";
  std::cout << "out == r.end() " << tts::as_string(out == r.end()) << "\n";
}
 
void
pairs_example()
{
  std::cout << "mixing types, custom predicate =================\n";
 
  /*
   * Example that does set_union for tuples and integers.
   */
 
  using pair_t = kumi::tuple<int, double>;
 
  eve::algo::soa_vector<pair_t> pairs {{0, 1.1f}, {2, 2.2f}, {3, 3.3f}, {4, 4.4f}};
  std::vector<int>              scalars {2, 4};
 
  eve::algo::soa_vector<pair_t> r;
  r.resize(pairs.size());
 
  auto project = []<typename T>(T a) {
    if constexpr (eve::like<T, pair_t>) return get<0>(a);
    else return a;
  };
 
  /*
   * Unfortunately, unlike std::set_intersect, we for now require that
   * the callback applies both ways.
   * FIX-1631
   */
  auto lt = [&](auto a, auto b) {
    return project(a) < project(b);
  };
 
  auto eq = [&](auto a, auto b) {
    return project(a) == project(b);
  };
 
  r.erase(eve::algo::set_intersection(pairs, scalars, r, lt, eq).out, r.end());
 
  eve::algo::soa_vector<pair_t> r_expected {{2, 2.2f}, {4, 4.4f}};
  TTS_EQUAL(r, r_expected);
 
  std::cout << "-> pairs:   " << tts::as_string(pairs) << '\n';
  std::cout << "-> sclaras: " << tts::as_string(scalars) << '\n';
  std::cout << "-> r:       " << tts::as_string(r) << '\n';
}
 
void
different_scalar_types_example()
{
  std::cout << "different_scalar_types =================\n";
 
  std::vector<double> f64 {10.1, 20, 30.3, 40.4};
  std::vector<int>    i32 {20, 40};
 
  // We will convert from the intersection to the output type
  std::vector<float> r0(5u, 0.0);
 
  // We will use eve::common_type for comparisons between different types
  // if predicates are defaulted.
  r0.erase(eve::algo::set_intersection(f64, i32, r0).out, r0.end());
  TTS_EQUAL(r0, std::vector<float>{20});
 
  auto project = [](auto a) {
    return eve::convert(a, eve::as<std::int64_t>{}) / 10;
  };
 
  auto lt = [&](auto a, auto b) {
    return project(a) < project(b);
  };
 
  auto eq = [&](auto a, auto b) {
    return project(a) == project(b);
  };
 
  // The output is always copied from the first range, so r1, r2 will give
  // different results.
  std::vector<float> r1(5u, 0.0);
  r1.erase(eve::algo::set_intersection(f64, i32, r1, lt, eq).out, r1.end());
  TTS_EQUAL(r1, (std::vector<float>{20, 40.4}));
 
  std::vector<float> r2(5u, 0.0);
  r2.erase(eve::algo::set_intersection(i32, f64, r2, lt, eq).out, r2.end());
  TTS_EQUAL(r2, (std::vector<float>{20, 40}));
 
  std::cout << "-> f64: " << tts::as_string(f64) << '\n';
  std::cout << "-> i32: " << tts::as_string(i32) << '\n';
  std::cout << "-> r0:  " << tts::as_string(r0) << '\n';
  std::cout << "-> r1:  " << tts::as_string(r1) << '\n';
  std::cout << "-> r2:  " << tts::as_string(r2) << '\n';
}
 
void
biase_example()
{
  std::cout << "smaller range hint =================\n";
  std::vector<int> v1(1000u, 0), v2{531, 917};
  std::iota(v1.begin(), v1.end(), 0);
 
  std::vector<int> r0{0, 1}, r1{0, 1};
 
  eve::algo::set_intersection[eve::algo::expect_smaller_range<0>](v1, v2, r0);
  eve::algo::set_intersection[eve::algo::expect_smaller_range<1>](v2, v1, r1);
 
  TTS_EQUAL(r0, v2);
  TTS_EQUAL(r1, v2);
 
  std::cout << "-> r0:  " << tts::as_string(r0) << '\n';
  std::cout << "-> r1:  " << tts::as_string(r1) << '\n';
}
 
void
sparse_output_example()
{
  std::cout << "sparse_output hint =================\n";
 
  std::vector<int> v1(20u, 0), v2(20u, 0);
  for (int i = 0; auto& x : v1) x = i++ * 3;
  for (int i = 0; auto& x : v2) x = i++ * 5;
 
  std::vector<int> r;
  r.resize(20);
 
  r.erase(
    eve::algo::set_intersection[eve::algo::sparse_output](v1, v2, r).out,
    r.end());
 
  std::cout << " -> r: " << tts::as_string(r) << std::endl;
  TTS_EQUAL(r, std::vector({0, 15, 30, 45}));
}
 
int
main()
{
  basic_example();
  not_enough_space_example();
  pairs_example();
  different_scalar_types_example();
  biase_example();
  sparse_output_example();
}

swap_ranges

auto eve::algo::swap_ranges = function_with_traits<swap_ranges_>[default_simple_algo_traits]

inlineconstexpr

SIMD version of std::swap_ranges.

• Accepts two things zipping together to range of pair.
• Also can accept a zipped_range_pair.
• returns void.
• default unrolling is 4.
• will align by default.
• will do conversions if necessary.

Required header: #include <eve/module/algo/algo/swap_ranges.hpp>

transform_copy_if

auto eve::algo::transform_copy_if = function_with_traits<eve_implementation_defined>

inlineconstexpr

Similar to applying eve::transform_to and eve::copy_if at the same time.

Defined in header

#include <eve/module/algo.hpp>

Note

If the scalar operation is cheap enough, ::copy_if + views::map might be slightly faster.

For an in-place version, see ::transform_keep_if.

Conditionally copies values from an input range to an output range, transforming them in the process.

If the output range is too small, fills all the available space and then stops.

If the output range's element type is different from the type of the values returned by the transforming function, performs the appropriate conversions.

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range In, eve::algo::relaxed_range Out, typename Func>
  auto transform_copy_if(In&& in, Out&& out, Func func) const -> unaligned_iterator_t<Out>
}

Parameters

• in: Input range
• out: Output range
• func: Function that takes elements from in as SIMD registers and returns a pair of:
  • the transformed values
  • a logical mask.

Return value

Output iterator past the last written element.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> input(16);
  eve::algo::iota(input, 0);
  std::cout << "Input vector:\n  " << tts::as_string(input) << "\n\n";
 
  auto func = [](eve::like<int> auto x) {
    return kumi::make_tuple(-x, eve::is_even(x));
  };
 
  std::vector<int> output_big(42);
  output_big.erase(eve::algo::transform_copy_if(input, output_big, func), output_big.end());
  std::cout << "Output (opposites of even numbers):\n  "
            << tts::as_string(output_big)
            << "\n\n";
 
  std::vector<unsigned char> output_small(5);
  output_small.erase(eve::algo::transform_copy_if(input, output_small, func), output_small.end());
  std::cout << "Output on a range too small to hold all the results,\nwith conversion to unsigned char:\n  "
            << tts::as_string(output_small)
            << std::endl;
 
  return 0;
}

See also

keep_if

copy_if

remove_if

transform_keep_if

transform_to

views::map

transform_inplace

auto eve::algo::transform_inplace = function_with_traits<transform_inplace_>[default_simple_algo_traits]

inlineconstexpr

same as;

eve::algo::transform_to(eve::views::zip(r, r), op)

but slightly more efficient

Required header: #include <eve/module/algo/algo/transform.hpp>

transform_keep_if

auto eve::algo::transform_keep_if = function_with_traits<transform_keep_if_>[no_traits]

inlineconstexpr

In-place version of eve::algo::transform_copy_if.

Defined in Header

#include <eve/module/algo.hpp>

Conditionally copies values that pass a predicate to the beginning of the range, transforming them in the process. Values past the returned sentinel are to be considered garbage.

Note

If the scalar operation is cheap enough, ::keep_if + views::map might be slightly faster.

See ::transform_copy_if and ::keep_if for more details.

Callable Signatures

{
  template<relaxed_range Rng, typename Func>
  auto transform_keep_if(Rng&& rng, Func func) -> unaligned_iterator_t<Rng>
}

Parameters

• rng: Range to modify
• func: Function that takes elements from rng as SIMD registers and returns a pair of:
  • the transformed values
  • a logical mask

Return value

Iterator past the last written element.

See also

keep_if

copy_if

remove_if

transform_copy_if

transform_inplace

views::map

transform_reduce

auto eve::algo::transform_reduce = function_with_traits<transform_reduce_>[default_simple_algo_traits]

inlineconstexpr

SIMD version of std::transform_reduce for a single range.

Configurable Callable Object performing a SIMD optimized version of the transform_reduce By default, the operation will be unrolled by a factor of 4, align memory accesses and perform conversions if needed.

Due to the nature of how SIMD algorithms work, the reduce operation has to be paired with its, neutral element. For example, for add you pass {add, zero} as zero is the identity for add. Instead of zero it can be beneficial to pass eve's constants like eve::zero, eve::one because sometimes the implementation can be improved.

Supports fuse_operations trait => map_op starts to take an extra parameter: current sum. Allows to use fma. Note that add operations and zero are still used and have to be correct.

Note

• The interface differs from the standard because we felt this better matches our use case: do unary transformation and then accumulate that.
• Multiple range interface is omitted for simplicity. Use eve::zip to get that effect.
• eve::transform_reduce requires less requirement on the operations than eve::views::map. In transform_reduce we don't need the map_op to be a template, for example.
• Compilers can auto-vectorize reductions, especially with special options. Maybe you don't need a library implementation.

Alternative Header

#include <eve/algo.hpp>

Callable Signatures

namespace eve::algo
{
  template <eve::algo::relaxed_range Rng, typename MapOp, typename U>
  U transform_reduce(Rng&& rng, MapOp map_op, U init);                                    // 1
 
  template< eve::algo::relaxed_range Rng, typename MapOp
          , typename AddOp, typename Zero, typename U
          >
  U transform_reduce(Rng&& rng, MapOp map_op, std::pair<AddOp, Zero> add_zero, U init);   // 2
}

1. Applies map_op to each element in the range rng and reduces the results along with the initial value init using regular addition as the reduce operation.
2. Applies map_op to each element in the range rng and reduces the results along with the initial value init using the add_zero reduce operation and neutral element.

Parameters

• rng: Relaxed input range to process
• init: Initial value. Also type of init matches the result type
• map_op: Transformation operation
• add_zero: Pair of reduction operation (commutative/associative) and an identity (zero) for it. Default add_zero is {eve::add, eve::zero}.

Return value

1. Sum of init and map_op applied on each element of rng.
2. Generalized sum of init and map_op applied on each element of rng using add_zero.

Example

#include <eve/module/core.hpp>
#include <eve/module/algo.hpp>
#include <tts/tts.hpp>
#include <iostream>
#include <vector>
#include <numeric>
 
int main()
{
  std::vector<float>  v = {1.0f, 2.0f, 3.0f, 4.0f, -1.0f, -2.0f, -3.0f, -4.0f, 1.0f, 2.0f, 3.0f, 4.0f};
 
  std::cout << " -> v                                                                                                                        = "
            << tts::as_string(v)
            << "\n";
 
  std::cout << " -> eve::algo::transform_reduce(v, [](auto x) { return x + x }, 0.f)                                                         = "
            << eve::algo::transform_reduce(v, [](auto x) { return x + x; }, 0.) << "\n";
 
  std::cout << " -> std::transform_reduce(v.begin(), v.end(), std::plus<>{}, 0.f, [](auto x) { return x + x })                               = "
            << std::transform_reduce(v.begin(), v.end(), 0., std::plus<>{}, [](auto x) { return x + x; }) << "\n";
 
  std::cout << " -> eve::algo::reduce(eve::views::map(v, [](auto x) { return x + x }), 0.f)                                                  = "
            << eve::algo::reduce(eve::views::map(v, [](auto x) { return x + x; }), 0.f) << "\n";
 
  std::cout << " -> eve::algo::transform_reduce(v, [](auto x) { return x + x }, std::pair{eve::mul, eve::one}, 1.f)  = "
            << eve::algo::transform_reduce(v, [](auto x) { return x + x; }, std::pair{eve::mul, eve::one}, 1.f) << "\n";
 
  std::cout << " -> eve::algo::transform_reduce[eve::algo::fuse_operations](v, [](auto x, auto sum) { return eve::fma(x, 2.f, sum); }, 0.f)  = "
            << eve::algo::transform_reduce[eve::algo::fuse_operations](v, [](auto x, auto sum) { return eve::fma(x, .5f, sum); }, 0.f) << "\n";
}

transform_to

auto eve::algo::transform_to = function_with_traits<transform_to_>[default_simple_algo_traits]

inlineconstexpr

SIMD version of std::transform.

• Accepts two things zipping together to range of pair.
• Also can accept a zipped_range_pair.
• returns void.
• default unrolling is 4.
• will align by default.
• the output type of the operation, is not considered in cardinal computation. (otherwise we'd have to require the predicate to be a template).
• if the operation output type differs from the output range type, converts.

Required header: #include <eve/module/algo/algo/transform.hpp>