[C++][cpponsea 2024] C++ Cache Friendly Data + Functional + Ranges summary

Reference:
https://www.youtube.com/watch?v=XJzs4kC9d-Y
https://github.com/rollbear/columnist

https://godbolt.org/z/a8P7oTjoh

#include <functional>
#include <iostream>
#include <tuple>
#include <vector>

template<typename... Ts>
class Table {
 public:
  using row = std::tuple<Ts&...>;
  row operator[](size_t i) {
    auto access = [&]<size_t... Is>(std::index_sequence<Is...>) {
      return row{std::get<Is>(data_)[i]...};
    };
    return std::invoke(access, indexes);
  }

  Table() {
    init(indexes);
  }

 private:
  static constexpr std::index_sequence_for<Ts...> indexes{};
  std::tuple<std::vector<Ts>...> data_;

 private:
  template<size_t... I>
  constexpr void init(std::index_sequence<I...>) {
    ((std::get<I>(data_).push_back({42}),...));
  }
};

struct Data1 {
 int value;
};

struct Data2 {
 int value;
};

int main() {

  Table<Data1, Data2> table;
  auto row = table[0];
  std::cout << std::get<0>(row).value << '\n'; // print 42
};

Iterator

Use sentinal pattern.

struct sentinel {}; // or using sentinal = void;

struct iterator {
  using value_type = row;
  using difference_type = ssize_t;

  value_type operator*() const {
    return std::invoke([&]<size_t... Is>(std::index_sequence<Is...>) {
      return value_type{std::get<Is>(t->data_)[offset]...};
    }, t->indexes);
  }

  iterator& operator++() { ++offset; return *this;}
  iterator operator++(int) { auto copy = *this; ++*this; return copy;}
  bool operator==(const iterator&) const = default;
  bool operator==(sentinel) const { return offset == t->size(); }
  table* t;
  size_t offset;
};

Plug in

template<typename... Ts>
class Table {
 public:
  friend class iterator;
  iterator begin() { return {this, 0}; }
  sentinel end() { return {}; }
...
};

Reference:

https://en.cppreference.com/w/cpp/utility/integer_sequence

template<typename...>
struct Table;

template<typename, typename>
struct Row;


template <typename... Ts, size_t... Cs>
struct Row<Table<Ts...>, std::index_sequence<Cs...>> {
  using row_id = typename Table<Ts...>::row_id;

  // Indirection to make std::index_sequence<0, 2, 4> -> I==1 means std::get<2>(...)
  template<size_t I>
  friend auto& get(const Row& r) {
    static constexpr std::array columns{Cs...};
    return std::get<columns[I]>(r.t->data_)[r.offset];
  }

  ...
  Table<Ts...>* t;
  size_t offset;
};


template<typename Table, size_t... Cs>
struct std::tuple_size<Row<Table, std::index_sequence<Cs...>>>
 : std::integral_constant<size_t, sizeof...(Cs)> {};


template <size_t I, typename... Ts, size_t... Cs>
struct std::tuple_element<I, Row<Table<Ts...>, std::index_sequence<Cs...>>> {
  static constexpr std::array indexes = { Cs... };
  using type = Ts...[indexes[I]]&;
};

Select:

template<size_t... Is, typename Table, size_t... Cs>
auto select(const Row<Table, std::index_sequence<Cs...>>& r) {
  static constexpr size_t columns[] { Cs... };
  return Row<Table, std::index_sequence<columns[Is]...>>(r);
}

Usage:

drop_if(values, [](auto r){ auto [x,z] = select<0, 2>(r); return x < z; });

template<typename R, size_t... Cs>
struct range_selector {
  using r_iterator = decltype(std::declval<R&>().begin());
  struct iterator : r_iterator {
    using difference_type = ssize_t;
    using value_type = decltype(select<Cs...>(*std::declval<r_iterator>()));
    
    iterator(const r_iterator& i) : r_iterator(i) {}
    auto operator*() const {
      const r_iterator& i = *this;
      return select<Cs...>(*i);
    }
  };

  iterator begin() { return iterator{ r.begin() }; }
  auto end() { return r.end(); }

  R& r;
};

template<size_t... Cs>
struct range_selector_maker {
  template<typename R>
  friend range_selector<R, Cs...> operator|(R& r, range_selector_maker) {
    return { r };
  }
};

template<size_t... Cs>
range_selector_maker<Cs...> select() { return {}; }

Usage:

for (auto [x, d] : values | select<0, 3>()) {
  std::println("d={} x={}", d, x);
}

Concepts:

template<typename>
inline constexpr bool row_type_v = false;

template<typename T, typename Cs>
inline constexpr bool row_type_v<Row<T, Cs>> = true;

template<typename T>
concept row_type = row_type_v<T>;

Select:

template<size_t... Cs, typename F>
auto select(F&& f) 
  requires (! row_type<std::remove_cvref_t<F>>)
{
  return [f = std::forward<F>(f)]<typename T, typename Is>(row<T, Is> r) {
    return f(select<Cs...>(r));
  };

}

template<typename F>
auto apply(F&& f) {
  return [f = std::forward<F>(f)]<row_type R>(R r) {
    return std::invoke([&]<size_t... Cs>(std::index_sequence<Cs...>) {
      return f(get<Cs>(r)...);
    }, std::make_index_sequence<std::tuple_size_v<R>>{});
  };
}

Usage:

drop_if(values, select<0, 2>(apply([](auto x, auto z) { return x < z; })));

or just:

drop_if(values, select<0, 2>(apply(std::less{})));