Iterator.h

Go to the documentation of this file.

/*
 * Copyright 2017-present Facebook, 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.
 */

#pragma once

#include <functional>
#include <iterator>
#include <memory>
#include <tuple>
#include <type_traits>
#include <utility>

#include <folly/Utility.h>
#include <folly/lang/RValueReferenceWrapper.h>

namespace folly {

template <typename... Args>
struct emplace_args : public std::tuple<std::decay_t<Args>...> {
  using storage_type = std::tuple<std::decay_t<Args>...>;
  using storage_type::storage_type;
};

template <typename... Args>
emplace_args<Args...> make_emplace_args(Args&&... args) noexcept(
    noexcept(emplace_args<Args...>(std::forward<Args>(args)...))) {
  return emplace_args<Args...>(std::forward<Args>(args)...);
}

namespace detail {
template <typename Arg>
decltype(auto) unwrap_emplace_arg(Arg&& arg) noexcept {
  return std::forward<Arg>(arg);
}
template <typename Arg>
decltype(auto) unwrap_emplace_arg(std::reference_wrapper<Arg> arg) noexcept {
  return arg.get();
}
template <typename Arg>
decltype(auto) unwrap_emplace_arg(
    folly::rvalue_reference_wrapper<Arg> arg) noexcept {
  return std::move(arg).get();
}
} // namespace detail

template <size_t I, typename... Args>
decltype(auto) get_emplace_arg(emplace_args<Args...>&& args) noexcept {
  using Out = std::tuple<Args...>;
  return detail::unwrap_emplace_arg(
      std::forward<std::tuple_element_t<I, Out>>(std::get<I>(args)));
}
template <size_t I, typename... Args>
decltype(auto) get_emplace_arg(emplace_args<Args...>& args) noexcept {
  return detail::unwrap_emplace_arg(std::get<I>(args));
}
template <size_t I, typename... Args>
decltype(auto) get_emplace_arg(const emplace_args<Args...>& args) noexcept {
  return detail::unwrap_emplace_arg(std::get<I>(args));
}
template <size_t I, typename Args>
decltype(auto) get_emplace_arg(Args&& args) noexcept {
  return std::get<I>(std::move(args));
}
template <size_t I, typename Args>
decltype(auto) get_emplace_arg(Args& args) noexcept {
  return std::get<I>(args);
}
template <size_t I, typename Args>
decltype(auto) get_emplace_arg(const Args& args) noexcept {
  return std::get<I>(args);
}

namespace detail {
template <typename Container>
struct Emplace {
  Emplace(Container& c, typename Container::iterator i)
      : container(std::addressof(c)), iter(std::move(i)) {}
  template <typename... Args>
  void emplace(Args&&... args) {
    iter = container->emplace(iter, std::forward<Args>(args)...);
    ++iter;
  }
  Container* container;
  typename Container::iterator iter;
};

template <typename Container>
struct EmplaceHint {
  EmplaceHint(Container& c, typename Container::iterator i)
      : container(std::addressof(c)), iter(std::move(i)) {}
  template <typename... Args>
  void emplace(Args&&... args) {
    iter = container->emplace_hint(iter, std::forward<Args>(args)...);
    ++iter;
  }
  Container* container;
  typename Container::iterator iter;
};

template <typename Container>
struct EmplaceFront {
  explicit EmplaceFront(Container& c) : container(std::addressof(c)) {}
  template <typename... Args>
  void emplace(Args&&... args) {
    container->emplace_front(std::forward<Args>(args)...);
  }
  Container* container;
};

template <typename Container>
struct EmplaceBack {
  explicit EmplaceBack(Container& c) : container(std::addressof(c)) {}
  template <typename... Args>
  void emplace(Args&&... args) {
    container->emplace_back(std::forward<Args>(args)...);
  }
  Container* container;
};

template <typename Derived, typename EmplaceImpl, bool implicit_unpack>
class emplace_iterator_base;

template <typename Derived, typename EmplaceImpl>
class emplace_iterator_base<Derived, EmplaceImpl, false>
    : protected EmplaceImpl /* protected implementation inheritance */ {
 public:
  // Iterator traits.
  using iterator_category = std::output_iterator_tag;
  using value_type = void;
  using difference_type = void;
  using pointer = void;
  using reference = void;
  using container_type =
      std::remove_reference_t<decltype(*EmplaceImpl::container)>;

  using EmplaceImpl::EmplaceImpl;

  template <typename T>
  Derived& operator=(T&& arg) {
    this->emplace(std::forward<T>(arg));
    return static_cast<Derived&>(*this);
  }

  template <typename... Args>
  Derived& operator=(emplace_args<Args...>& args) {
    return unpackAndEmplace(args, index_sequence_for<Args...>{});
  }
  template <typename... Args>
  Derived& operator=(const emplace_args<Args...>& args) {
    return unpackAndEmplace(args, index_sequence_for<Args...>{});
  }
  template <typename... Args>
  Derived& operator=(emplace_args<Args...>&& args) {
    return unpackAndEmplace(std::move(args), index_sequence_for<Args...>{});
  }

  // No-ops.
  Derived& operator*() {
    return static_cast<Derived&>(*this);
  }
  Derived& operator++() {
    return static_cast<Derived&>(*this);
  }
  Derived& operator++(int) {
    return static_cast<Derived&>(*this);
  }

  // We need all of these explicit defaults because the custom operator=
  // overloads disable implicit generation of these functions.
  emplace_iterator_base(const emplace_iterator_base&) = default;
  emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
  emplace_iterator_base& operator=(emplace_iterator_base&) = default;
  emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
  emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;

 protected:
  template <typename Args, std::size_t... I>
  Derived& unpackAndEmplace(Args& args, index_sequence<I...>) {
    this->emplace(get_emplace_arg<I>(args)...);
    return static_cast<Derived&>(*this);
  }
  template <typename Args, std::size_t... I>
  Derived& unpackAndEmplace(const Args& args, index_sequence<I...>) {
    this->emplace(get_emplace_arg<I>(args)...);
    return static_cast<Derived&>(*this);
  }
  template <typename Args, std::size_t... I>
  Derived& unpackAndEmplace(Args&& args, index_sequence<I...>) {
    this->emplace(get_emplace_arg<I>(std::move(args))...);
    return static_cast<Derived&>(*this);
  }
};

template <typename Derived, typename EmplaceImpl>
class emplace_iterator_base<Derived, EmplaceImpl, true>
    : public emplace_iterator_base<Derived, EmplaceImpl, false> {
 private:
  using Base = emplace_iterator_base<Derived, EmplaceImpl, false>;

 public:
  using Base::Base;
  using Base::operator=;

  template <typename... Args>
  Derived& operator=(std::pair<Args...>& args) {
    return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
  }
  template <typename... Args>
  Derived& operator=(const std::pair<Args...>& args) {
    return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
  }
  template <typename... Args>
  Derived& operator=(std::pair<Args...>&& args) {
    return this->unpackAndEmplace(
        std::move(args), index_sequence_for<Args...>{});
  }

  template <typename... Args>
  Derived& operator=(std::tuple<Args...>& args) {
    return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
  }
  template <typename... Args>
  Derived& operator=(const std::tuple<Args...>& args) {
    return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
  }
  template <typename... Args>
  Derived& operator=(std::tuple<Args...>&& args) {
    return this->unpackAndEmplace(
        std::move(args), index_sequence_for<Args...>{});
  }

  // We need all of these explicit defaults because the custom operator=
  // overloads disable implicit generation of these functions.
  emplace_iterator_base(const emplace_iterator_base&) = default;
  emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
  emplace_iterator_base& operator=(emplace_iterator_base&) = default;
  emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
  emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
};

template <
    template <typename> class EmplaceImplT,
    typename Container,
    bool implicit_unpack>
class emplace_iterator_impl
    : public emplace_iterator_base<
          emplace_iterator_impl<EmplaceImplT, Container, implicit_unpack>,
          EmplaceImplT<Container>,
          implicit_unpack> {
 private:
  using Base = emplace_iterator_base<
      emplace_iterator_impl,
      EmplaceImplT<Container>,
      implicit_unpack>;

 public:
  using Base::Base;
  using Base::operator=;

  // We need all of these explicit defaults because the custom operator=
  // overloads disable implicit generation of these functions.
  emplace_iterator_impl(const emplace_iterator_impl&) = default;
  emplace_iterator_impl(emplace_iterator_impl&&) noexcept = default;
  emplace_iterator_impl& operator=(emplace_iterator_impl&) = default;
  emplace_iterator_impl& operator=(const emplace_iterator_impl&) = default;
  emplace_iterator_impl& operator=(emplace_iterator_impl&&) noexcept = default;
};
} // namespace detail

template <typename Container, bool implicit_unpack = true>
using emplace_iterator =
    detail::emplace_iterator_impl<detail::Emplace, Container, implicit_unpack>;

template <typename Container, bool implicit_unpack = true>
using hint_emplace_iterator = detail::
    emplace_iterator_impl<detail::EmplaceHint, Container, implicit_unpack>;

template <typename Container, bool implicit_unpack = true>
using front_emplace_iterator = detail::
    emplace_iterator_impl<detail::EmplaceFront, Container, implicit_unpack>;

template <typename Container, bool implicit_unpack = true>
using back_emplace_iterator = detail::
    emplace_iterator_impl<detail::EmplaceBack, Container, implicit_unpack>;

template <bool implicit_unpack = true, typename Container>
emplace_iterator<Container, implicit_unpack> emplacer(
    Container& c,
    typename Container::iterator i) {
  return emplace_iterator<Container, implicit_unpack>(c, std::move(i));
}

template <bool implicit_unpack = true, typename Container>
hint_emplace_iterator<Container, implicit_unpack> hint_emplacer(
    Container& c,
    typename Container::iterator i) {
  return hint_emplace_iterator<Container, implicit_unpack>(c, std::move(i));
}

template <bool implicit_unpack = true, typename Container>
front_emplace_iterator<Container, implicit_unpack> front_emplacer(
    Container& c) {
  return front_emplace_iterator<Container, implicit_unpack>(c);
}

template <bool implicit_unpack = true, typename Container>
back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
  return back_emplace_iterator<Container, implicit_unpack>(c);
}
} // namespace folly