tuple_vector.hpp

Go to the documentation of this file.

// Copyright 2022-2024 Ekumen, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#ifndef BELUGA_CONTAINERS_TUPLE_VECTOR_HPP
#define BELUGA_CONTAINERS_TUPLE_VECTOR_HPP
 
#include <tuple>
#include <vector>
 
#include <beluga/type_traits.hpp>
#include <beluga/views/zip.hpp>
#include <range/v3/algorithm/copy.hpp>
#include <range/v3/iterator/insert_iterators.hpp>
#include <range/v3/view/const.hpp>
#include <range/v3/view/take.hpp>
 
namespace beluga {
 
template <template <class> class InternalContainer, class T>
class TupleContainer;
 
 
template <template <class> class InternalContainer, class... Types>
class TupleContainer<InternalContainer, std::tuple<Types...>> {
 public:
  using value_type = std::tuple<Types...>;
 
  using reference_type = ranges::common_tuple<Types&...>;
 
  using size_type = std::size_t;
 
  using difference_type = std::ptrdiff_t;
 
 
  using allocator_type = void;
 
  constexpr TupleContainer() = default;
 
 
  explicit constexpr TupleContainer(size_type count) : sequences_{((void)sizeof(Types), count)...} {}
 
  template <typename I, typename S>
  constexpr TupleContainer(I first, S last) {
    assign(first, last);
  }
 
  constexpr TupleContainer(std::initializer_list<value_type> init) { assign(init.begin(), init.end()); }
 
  [[nodiscard]] constexpr bool empty() const noexcept { return std::get<0>(sequences_).empty(); }
 
  [[nodiscard]] constexpr size_type size() const noexcept { return std::get<0>(sequences_).size(); }
 
  [[nodiscard]] constexpr size_type capacity() const noexcept { return std::get<0>(sequences_).capacity(); }
 
  constexpr void clear() noexcept {
    std::apply([](auto&&... containers) { (containers.clear(), ...); }, sequences_);
  }
 
 
  template <typename I, typename S>
  constexpr void assign(I first, S last) {
    auto range = ranges::make_subrange(first, last);
    static_assert(ranges::input_range<decltype(range)>);
    if constexpr (ranges::sized_range<decltype(range)>) {
      resize(ranges::size(range));
      ranges::copy(range, begin());
    } else {
      // Optimization to copy as much as we can before we start back inserting.
      // Back insertion time is severely punished by having multiple containers.
      //
      // There are two bad cases for this implementation:
      // - The capacity is too large compared to the size of the input range, so
      //   we allocate and default construct unnecessarily.
      // - The capacity is too low compared to the size of the input range, so
      //   there will be a lot of back inserting.
      //
      // If common guidelines of calling reserve with the expected size are followed,
      // then this is quite fast, even when we don't know the exact size of the range
      // in advance.
      resize(capacity());
      // Copy elements until we reach current capacity.
      auto limited_range = range | ranges::views::take(size());
      auto [last_in, last_out] = ranges::copy(limited_range, begin());
      const auto copied_size = static_cast<size_type>(ranges::distance(begin(), last_out));
      if (size() == copied_size) {
        // Back insert the remaining elements if any.
        ranges::copy(last_in.base(), last, ranges::back_inserter(*this));
      } else {
        // Remove extra elements by resizing to the correct size.
        resize(copied_size);
      }
    }
  }
 
  template <typename R>
  constexpr void assign_range(R&& range) {
    assign(ranges::begin(range), ranges::end(range));
  }
 
 
  constexpr void reserve(size_type new_cap) {
    std::apply([new_cap](auto&&... containers) { (containers.reserve(new_cap), ...); }, sequences_);
  }
 
 
  constexpr void resize(size_type count) {
    std::apply([count](auto&&... containers) { (containers.resize(count), ...); }, sequences_);
  }
 
 
  constexpr void push_back(const value_type& value) {
    push_back_impl(value, std::make_index_sequence<sizeof...(Types)>());
  }
 
  constexpr void push_back(value_type&& value) {
    push_back_impl(std::move(value), std::make_index_sequence<sizeof...(Types)>());
  }
 
  [[nodiscard]] constexpr auto begin() const { return all().begin(); }
 
  [[nodiscard]] constexpr auto end() const { return all().end(); }
 
  [[nodiscard]] constexpr auto begin() { return all().begin(); }
 
  [[nodiscard]] constexpr auto end() { return all().end(); }
 
 private:
  std::tuple<InternalContainer<Types>...> sequences_;
 
  template <typename T, std::size_t... Ids>
  constexpr void push_back_impl(T value, std::index_sequence<Ids...>) {
    (std::get<Ids>(sequences_).push_back(std::get<Ids>(value)), ...);
  }
 
  [[nodiscard]] constexpr auto all() const {
    return std::apply([](auto&... containers) { return beluga::views::zip(containers...); }, sequences_);
  }
 
  [[nodiscard]] constexpr auto all() {
    return std::apply([](auto&... containers) { return beluga::views::zip(containers...); }, sequences_);
  }
};
 
template <class T>
using Vector = std::vector<T, std::allocator<T>>;
 
 
template <class T>
class TupleVector : public TupleContainer<Vector, T> {
  using TupleContainer<Vector, T>::TupleContainer;
};
 
template <class I, class S, typename = std::enable_if_t<ranges::input_iterator<I> && ranges::input_iterator<S>>>
TupleVector(I, S) -> TupleVector<decay_tuple_like_t<ranges::iter_value_t<I>>>;
 
}  // namespace beluga
 
#endif