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
set_intersection{ .in1, .in2, .out }.
#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;
r.resize(v1.size());
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;
r.resize(1);
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";
using pair_t = kumi::tuple<int, double>;
std::vector<int> scalars {2, 4};
auto project = []<typename T>(T a) {
else return a;
};
auto lt = [&](auto a, auto b) {
return project(a) < project(b);
};
auto eq = [&](auto a, auto b) {
return project(a) == project(b);
};
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};
std::vector<float> r0(5u, 0.0);
TTS_EQUAL(r0, std::vector<float>{20});
auto project = [](auto a) {
};
auto lt = [&](auto a, auto b) {
return project(a) < project(b);
};
auto eq = [&](auto a, auto b) {
return project(a) == project(b);
};
std::vector<float> r1(5u, 0.0);
TTS_EQUAL(r1, (std::vector<float>{20, 40.4}));
std::vector<float> r2(5u, 0.0);
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};
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.erase(
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();
}
Specifies semantic compatibility between wrapper/wrapped types.
Definition product_type.hpp:107
constexpr auto sparse_output
for algorithms that output data based on input (eve::algo::copy_if, eve::algo::remove_if,...
Definition traits.hpp:419
constexpr auto expect_smaller_range
some algorithms (for example set_intersection) have a better implementation if we know that one of th...
Definition traits.hpp:331
constexpr auto convert
Converts a value to another type.
Definition convert.hpp:83
void resize(size_type n, value_type value)
Resizes the container to contain count elements.
Definition soa_vector.hpp:233
iterator erase(const_iterator pos)
Removes an element from the container.
Definition soa_vector.hpp:191
SIMD-aware container for product types.
Definition soa_vector.hpp:50
auto end() -> iterator
Returns an iterator to the end.
Definition soa_vector.hpp:341
Lightweight type-wrapper.
Definition as.hpp:29