Binary Search C++11 C++17

Question

Any way I can optimize this further with C++11 or C++17 features?

Would also like feedback on my variable naming, memory management, edge case handling (in this someone calling my function with an nullptr or int overflow with my rearranged equation to calculate the mid), and coding style. If there are other data structures I can use to implement this instead of basic arrays and raw pointers I’d like some feedback there too.

For my return type on the binary_search function, does it matter if I return a bool versus an int?

Code

#include <cassert> #include <iostream>  bool binary_search(int* data, int num_elements, int target) {     int low = 0;     int high = num_elements - 1;     int mid;      if(data == nullptr) { throw std::exception(); }      while(low <= high) {         mid = low + (high - low) / 2;         if(data[mid] == target) {             return 1;         } else if(data[mid] > target) {             high = mid - 1;         } else {             low = mid + 1;         }     }      return 0; }  int main() {     int num_elements = 6;      int data[] = { 5, 8, 10, 15, 26, 30 };     int target[] = { 5, 4, 12, 15, 35, 30 };     int expected[] = { 1, 0, 0, 1, 0, 1 };      for(int i=0; i < num_elements; ++i) {         try {             assert(expected[i] == binary_search(data, num_elements, target[i]));             std::cout << expected[i] << " returned for search on " << target[i] << '\n';         } catch(std::exception& e) {             std::cout << "Exception " << e.what() << '\n';         }     }      return 0; } 

C++17 Result implementation

This is a C++17 Either implementation.

Left and Right are helper structs for avoid additional bool usage in Result.

to_left(…) and to_right(…) helper functions for specified side if both types are same in Result.

namespace marklar::result { // Helper template<typename Type> struct Left;  template<typename Type> struct Right;  template<typename> struct is_left : std::false_type {};  template<typename Type> struct is_left<Left<Type>> : std::true_type {};  template<typename Type> inline constexpr bool is_left_v = is_left<Type>::value;  template<typename> struct is_right : std::false_type {};  template<typename Type> struct is_right<Right<Type>> : std::true_type {};  template<typename Type> inline constexpr bool is_right_v = is_right<Type>::value;  template<typename Type> struct Left {     Type const value_;      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Left<Type>, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && std::is_convertible_v<ParamType &&, Type>                  , bool> = true>     constexpr Left(ParamType && value)         : value_ { std::forward<ParamType>(value) }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Left<Type>, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && !std::is_convertible_v<ParamType &&, Type>                  , bool> = false>     constexpr explicit Left(ParamType && value)         : value_ { std::forward<ParamType>(value) }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Type, ParamType>                      && std::is_constructible_v<Type, ParamType const &>                      && !std::is_convertible_v<ParamType const &, Type>                  , bool> = false>     explicit constexpr Left(Left<ParamType> const & other)         : value_ { other.value_ }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Type, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && std::is_convertible_v<ParamType &&, Type>                  , bool> = true>     constexpr Left(Left<ParamType> && other)         : value_ { std::move(other).value_ }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Type, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && !std::is_convertible_v<ParamType &&, Type>                  , bool> = false>     explicit constexpr Left(Left<ParamType> && other)         : value_ { std::move(other).value_ }     {} };  template<typename Type> struct Right {     Type const value_;      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Right<Type>, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && std::is_convertible_v<ParamType &&, Type>                  , bool> = true>     constexpr Right(ParamType && value)         : value_ { std::forward<ParamType>(value) }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Right<Type>, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && !std::is_convertible_v<ParamType &&, Type>                  , bool> = false>     constexpr explicit Right(ParamType && value)         : value_ { std::forward<ParamType>(value) }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Type, ParamType>                  && std::is_constructible_v<Type, ParamType const &>                  && !std::is_convertible_v<ParamType const &, Type>                  , bool> = false>     explicit constexpr Right(Right<ParamType> const & other)         : value_ { other.value_ }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Type, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && std::is_convertible_v<ParamType &&, Type>                  , bool> = true>     constexpr Right(Right<ParamType> && other)         : value_ { std::move(other).value_ }     {}      template <typename ParamType = Type,               typename std::enable_if_t<                  !std::is_same_v<Type, ParamType>                  && std::is_constructible_v<Type, ParamType &&>                  && !std::is_convertible_v<ParamType &&, Type>                  , bool> = false>     explicit constexpr Right(Right<ParamType> && other)         : value_ { std::move(other).value_ }     {} };  template<typename Type> inline constexpr Left<Type> to_left(Type const & value) {     return Left<Type>{ value }; }  template<typename Type, typename std::enable_if_t<!std::is_move_constructible_v<Type>, bool> = true> inline constexpr Left<Type> to_left(Type && value) {     return Left<Type>{ std::forward<Type>(value) }; }  template<typename Type> inline constexpr Right<Type> to_right(Type const & value) {     return Right<Type>{ value }; }  template<typename Type, typename std::enable_if_t<!std::is_move_constructible_v<Type>, bool> = true> inline constexpr Right<Type> to_right(Type && value) {     return Right<Type>{ std::forward<Type>(value) }; }  template<typename LeftType, typename RightType> struct Result {     static_assert(!(std::is_reference_v<LeftType> || std::is_reference_v<RightType>)                       , "Result must have no reference alternative");     static_assert(!(std::is_void_v<LeftType> || std::is_void_v<RightType>)                       , "Result must have no void alternative");      using LeftValue = Left<LeftType>;     using RightValue = Right<RightType>;      static constexpr size_t index_left_ = 0;     static constexpr size_t index_right_ = 1;      const std::variant<const LeftValue, const RightValue> variant_;      constexpr explicit Result(Result<LeftType, RightType> && other)         : variant_ { std::forward<Result<LeftType, RightType>>( other ).variant_ }     {}      template<typename ParamType>     constexpr explicit Result(ParamType const & value)         : variant_ {             []() -> auto {                 if constexpr (std::is_same_v<LeftType, ParamType> || is_left_v<ParamType>) {                     return std::in_place_index<index_left_>;                 } else if constexpr (std::is_same_v<RightType, ParamType> || is_right_v<ParamType>) {                     return std::in_place_index<index_right_>;                 }             }()             , [](ParamType const & value) -> auto {                 if constexpr (std::is_same_v<LeftType, ParamType>) {                     return to_left(value);                 } else if constexpr (std::is_same_v<RightType, ParamType>) {                     return to_right(value);                 } else if constexpr (is_left_v<ParamType> || is_right_v<ParamType>) {                     return value;                 }             }(value)         }     {         static_assert((is_left_v<ParamType> || is_right_v<ParamType> || std::is_same_v<LeftType, ParamType> || std::is_same_v<RightType, ParamType>)                       , "Result only setted alternatives can use");          if constexpr (!(is_left_v<ParamType> || is_right_v<ParamType>)) {             static_assert(!std::is_same_v<LeftType, RightType>                           , "Result must have distinguish between alternatives");         }     }      template<typename ParamType>     constexpr explicit Result(ParamType && value) noexcept         : variant_ {             []() -> auto {                 if constexpr (std::is_same_v<LeftType, ParamType> || is_left_v<ParamType>) {                     return std::in_place_index<index_left_>;                 } else if constexpr (std::is_same_v<RightType, ParamType> || is_right_v<ParamType>) {                     return std::in_place_index<index_right_>;                 }             }()             , [](ParamType && value) -> auto {                 if constexpr (std::is_same_v<LeftType, ParamType>) {                     return to_left(std::forward<ParamType>(value));                 } else if constexpr (std::is_same_v<RightType, ParamType>) {                     return to_right(std::forward<ParamType>(value));                 } else if constexpr (is_left_v<ParamType> || is_right_v<ParamType>) {                     return std::forward<ParamType>(value);                 }             }(std::forward<ParamType>(value))         }     {         static_assert((is_left_v<ParamType> || is_right_v<ParamType> || std::is_same_v<LeftType, ParamType> || std::is_same_v<RightType, ParamType>)                           , "Result only setted alternatives can use");          if constexpr (!(is_left_v<ParamType> || is_right_v<ParamType>)) {             static_assert(!std::is_same_v<LeftType, RightType>                           , "Result must have distinguish between alternatives");         }     }      template<typename TempType = LeftType>     inline constexpr TempType const &     left() const &     {         static_assert(std::is_convertible_v<TempType, LeftType>);          return std::get<index_left_>(variant_).value_;     }      template<typename TempType = LeftType>     constexpr TempType &&     left() &&     {         static_assert(std::is_convertible_v<TempType &&, LeftType>);          return std::move(std::get<index_left_>(variant_).value_);     }      template<typename TempType = LeftType>     constexpr LeftType     left_or(TempType && substitute) const &     {         static_assert(std::is_convertible_v<TempType &&, LeftType>);          return std::holds_alternative<const LeftValue>(variant_)                    ? this->left()                    : static_cast<LeftType>(std::forward<TempType>(substitute));     }      template<typename TempType = LeftType>     constexpr LeftType &&     left_or(TempType && substitute) &&     {         static_assert(std::is_convertible_v<TempType &&, LeftType>);          return std::holds_alternative<const LeftValue>(variant_)                    ? std::move(this->left())                    : static_cast<LeftType>(std::forward<TempType>(substitute));     }      template<typename TempType = RightType>     inline constexpr TempType const &     right() const &     {         static_assert(std::is_convertible_v<TempType, RightType>);          return std::get<index_right_>(variant_).value_;     }      template<typename TempType = RightType>     constexpr TempType &&     right() &&     {         static_assert(std::is_convertible_v<TempType &&, RightType>);          return std::move(std::get<index_right_>(variant_).value_);     }      template<typename TempType = RightType>     constexpr RightType     right_or(TempType && substitute) const &     {         static_assert(std::is_convertible_v<TempType &&, RightType>);          return std::holds_alternative<const LeftValue>(variant_)                    ? static_cast<RightType>(std::forward<TempType>(substitute))                    : this->right();     }      template<typename TempType = RightType>     constexpr RightType &&     right_or(TempType && substitute) &&     {         static_assert(std::is_convertible_v<TempType &&, RightType>);          return std::holds_alternative<const LeftValue>(variant_)                    ? static_cast<RightType>(std::forward<TempType>(substitute))                    : std::move(this->right());     }      template<typename Function>     inline constexpr auto left_map(Function const & function) &&         -> Result<decltype(function(std::get<index_left_>(variant_).value_)), RightType>     {         return std::holds_alternative<const LeftValue>(variant_)                    ? Result{ to_left(function(this->left())) }                    : Result{ std::get<index_right_>(variant_) };     }      template<typename Function>     inline constexpr auto     right_map(Function const & function) const         -> Result<LeftType, decltype(function(std::get<index_right_>(variant_).value_))>     {         return std::holds_alternative<const LeftValue>(variant_)                    ? Result{ std::get<index_left_>(variant_) }                    : Result{ to_right(function(this->right())) };     }      template<typename LeftLocal = LeftType, typename RightLocal = RightType>     inline constexpr auto     join() const         -> std::common_type_t<const LeftLocal, const RightLocal>     {         return std::holds_alternative<const LeftValue>(variant_)                    ? this->left()                    : this->right();     }      inline constexpr operator bool() const noexcept     {         return std::holds_alternative<const LeftValue>(variant_);     } };  } // namespace marklar::result 

An working example

  • Any suggestion for better implementation?
  • Is the perfect forwarding correctly used?

C++17 pointer_traits implementation

pointer_traits is a lightweight trait that provides a uniform interface to builtin pointers and user-defined fancy pointers. That said, things like element_type require template metaprogramming techniques to determine. This makes pointer_traits a good exercise.

Here’s my re-implementation under the name my_std::pointer_traits, put in a separate header pointer_traits.hpp because <memory> is way too comprehensive:

// C++17 pointer_traits implementation  #ifndef INC_POINTER_TRAITS_HPP_60HzB0lbek #define INC_POINTER_TRAITS_HPP_60HzB0lbek  #include <cstddef>     // for std::ptrdiff_t #include <memory>      // for std::addressof #include <type_traits> // for std::add_lvalue_reference  namespace my_std {    template <class Ptr>   struct pointer_traits;    namespace pt_detail {      template <class Tmpl>     struct get_first_param { };     template <template <class, class...> class Tmpl, class T, class... Args>     struct get_first_param<Tmpl<T, Args...>> {       using type = T;     };     template <class Tmpl>     using get_first_param_t = typename get_first_param<Tmpl>::type;      template <class Tmpl, class U>     struct rebind_first_param { };     template <template <class, class...> class Tmpl, class T, class... Args, class U>     struct rebind_first_param<Tmpl<T, Args...>, U> {       using type = Tmpl<U, Args...>;     };     template <class Tmpl, class U>     using rebind_first_param_t = typename rebind_first_param<Tmpl, U>::type;      template <class Ptr>     auto element(int) -> typename Ptr::element_type;     template <class Ptr>     auto element(long) -> get_first_param_t<Ptr>;      template <class Ptr>     auto diff(int) -> typename Ptr::difference_type;     template <class Ptr>     auto diff(long) -> std::ptrdiff_t;      template <class Ptr, class U>     auto rebind(int) -> typename Ptr::template rebind<U>;     template <class Ptr, class U>     auto rebind(long) -> rebind_first_param_t<Ptr, U>;    }    template <class Ptr>   struct pointer_traits {     using pointer = Ptr;     using element_type = decltype(pt_detail::element<Ptr>(0));     using difference_type = decltype(pt_detail::diff<Ptr>(0));      template <class U>     using rebind = decltype(pt_detail::rebind<Ptr, U>(0));      static pointer pointer_to(std::add_lvalue_reference<element_type> r)     {       return Ptr::pointer_to(r);     }   };    template <class T>   struct pointer_traits<T*> {     using pointer = T*;     using element_type = T;     using difference_type = std::ptrdiff_t;      template <class U>     using rebind = U*;      static pointer pointer_to(std::add_lvalue_reference<element_type> r)     {       return std::addressof(r);     }   };  }  #endif 

I used N4659 as a reference.

C++17 allocator_traits implementation

Inspired by my earlier question C++17 pointer_traits implementation, I re-implemented allocator_traits under the name my_std::allocator_traits, put in a separate header allocator_traits.hpp because <memory> is way too comprehensive:

// C++17 allocator_traits implementation  #ifndef INC_ALLOCATOR_TRAITS_HPP_D6XSISB6AD #define INC_ALLOCATOR_TRAITS_HPP_D6XSISB6AD  #include <limits>      // for std::numeric_limits #include <memory>      // for std::pointer_traits #include <type_traits> // for std::false_type, etc. #include <utility>     // for std::forward  namespace my_std {    template <class Alloc>   struct allocator_traits;    namespace at_detail {      template <class Tmpl, class U>     struct rebind_first_param { };     template <template <class, class...> class Tmpl, class T, class... Args, class U>     struct rebind_first_param<Tmpl<T, Args...>, U> {       using type = Tmpl<U, Args...>;     };     template <class Tmpl, class U>     using rebind_first_param_t = typename rebind_first_param<Tmpl, U>::type;      template <class Alloc, class T>     auto pointer(int) -> typename Alloc::pointer;     template <class Alloc, class T>     auto pointer(long) -> T*;      template <class Alloc, class T, class Ptr>     auto const_pointer(int) -> typename Alloc::const_pointer;     template <class Alloc, class T, class Ptr>     auto const_pointer(long) -> typename std::pointer_traits<Ptr>::template rebind<const T>;      template <class Alloc, class Ptr>     auto void_pointer(int) -> typename Alloc::void_pointer;     template <class Alloc, class Ptr>     auto void_pointer(long) -> typename std::pointer_traits<Ptr>::template rebind<void>;      template <class Alloc, class Ptr>     auto const_void_pointer(int) -> typename Alloc::const_void_pointer;     template <class Alloc, class Ptr>     auto const_void_pointer(long) -> typename std::pointer_traits<Ptr>::template rebind<const void>;      template <class Alloc, class Ptr>     auto difference_type(int) -> typename Alloc::difference_type;     template <class Alloc, class Ptr>     auto difference_type(long) -> typename std::pointer_traits<Ptr>::difference_type;      template <class Alloc, class Diff>     auto size_type(int) -> typename Alloc::size_type;     template <class Alloc, class Diff>     auto size_type(long) -> std::make_unsigned_t<Diff>;      template <class Alloc>     auto pocca(int) -> typename Alloc::鈥媝ropagate_on_container_copy_assignment;     template <class Alloc>     auto pocca(long) -> std::false_type;      template <class Alloc>     auto pocma(int) -> typename Alloc::propagate_on_container_move_assignment;     template <class Alloc>     auto pocma(long) -> std::false_type;      template <class Alloc>     auto pocw(int) -> typename Alloc::propagate_on_container_swap;     template <class Alloc>     auto pocw(long) -> std::false_type;      template <class Alloc>     auto iae(int) -> typename Alloc::is_always_equal;     template <class Alloc>     auto iae(long) -> std::is_empty<Alloc>::type;      template <class Alloc, class T>     auto rebind_alloc(int) -> typename Alloc::rebind<T>::other;     template <class Alloc, class T>     auto rebind_alloc(long) -> rebind_first_param_t<Alloc, T>;    }    template <class Alloc>   struct allocator_traits {     using allocator_type = Alloc;     using value_type = typename Alloc::value_type;      using pointer = decltype(at_detail::pointer<Alloc, value_type>(0));     using const_pointer = decltype(at_detail::const_pointer<Alloc, value_type, pointer>(0));     using void_pointer = decltype(at_detail::void_pointer<Alloc, pointer>(0));     using const_void_pointer = decltype(at_detail::const_void_pointer<Alloc, pointer>(0));      using difference_type = decltype(at_detail::difference_type<Alloc, pointer>(0));     using size_type = decltype(at_detail::size_type<Alloc, difference_type>(0));      using propagate_on_container_copy_assignment = decltype(at_detail::pocca<Alloc>(0));     using propagate_on_container_move_assignment = decltype(at_detail::pocma<Alloc>(0));     using propagate_on_container_swap = decltype(at_detail::pocw<Alloc>(0));     using is_always_equal = decltype(at_detail::iae<Alloc>(0));      template <class T>     using rebind_alloc = decltype(at_detail::rebind_alloc<Alloc, T>(0));      static pointer allocate(Alloc& a, size_type n)     {       return a.allocate(n);     }     static pointer allocate(Alloc& a, size_type n, const_void_pointer hint)     {       return allocate_(a, n, hint, 0);     }      static void deallocate(Alloc& a, pointer p, size_type n)     {       a.deallocate(p, n);     }      template <class T, class... Args>     static void construct(Alloc& a, T* p, Args&&... args)     {       construct_(a, p, 0, std::forward<Args>(args)...);     }      template <class T>     static void destroy(Alloc& a, T* p)     {       destroy_(a, p, 0);     }      static size_type max_size(const Alloc& a) noexcept     {       return max_size_(a, 0);     }      static Alloc select_on_container_copy_construction(const Alloc& rhs)     {       return soccc(rhs, 0);     }    private:     static auto allocate_(Alloc& a, size_type n, const_void_pointer hint, int)       -> decltype(a.allocate(n, hint), void(), std::declval<pointer>())     {       return a.allocate(n, hint);     }     static auto allocate_(Alloc& a, size_type n, const_void_pointer, long)       -> pointer     {       return a.allocate(n);     }      template <class T, class... Args>     static auto construct_(Alloc& a, T* p, int, Args&&... args)       -> decltype(a.construct(p, std::forward<Args>(args)...), void())     {       a.construct(p, std::forward<Args>(args)...);     }     template <class T, class... Args>     static void construct_(Alloc&, T* p, long, Args&&... args)     {       ::new(static_cast<void*>(p)) T(std::forward<Args>(args)...);     }      template <class T>     static auto destroy_(Alloc& a, T* p, int)       -> decltype(a.destroy(p), void())     {       a.destroy(p);     }     template <class T>     static void destroy_(Alloc&, T* p, long)     {       p->~T();     }      static auto max_size_(const Alloc& a, int) noexcept       -> decltype(a.max_size(), std::declval<size_type>())     {       return a.max_size();     }     static auto max_size_(const Alloc&, long) noexcept       -> size_type     {       return std::numeric_limits<size_type>::max() / sizeof(value_type);     }      static auto soccc(const Alloc& rhs, int)       -> decltype(rhs.select_on_container_copy_construction(), std::declval<Alloc>())     {       return rhs.select_on_container_copy_construction();     }     static auto soccc(const Alloc& rhs, long)       -> Alloc     {       return rhs;     }   };  }  #endif 

I have to say that allocator_traits is mainly boilerplate code and I almost “synthesized” it automatically according to the standard …

Merge Sort C++11 C++17

Question

Any way I can optimize this further using new C++11 or C++17 features? Would also like feedback on my variable naming, memory management, and style (notice my placement of varible_name++ in some areas), and how I’ve abstracted the sort into a recursive_merge_sort function and a merge function.

Code

#include <iostream>  void merge(int* data, int low, int mid, int high) {     int low_copy = low;     int mid_copy = mid;      int size = high - low;     int* sorted = new int[size];     int i = 0;      while(low_copy < mid && mid_copy < high) {         if(data[low_copy] < data[mid_copy]) {             sorted[i] = data[low_copy++];         }         else {             sorted[i] = data[mid_copy++];         }         ++i;     }      while(low_copy < mid) {         sorted[i++] = data[low_copy++];     }     while(mid_copy < high) {         sorted[i++] = data[mid_copy++];     }      for(i = 0; i < size; ++i) {         data[low + i] = sorted[i];     } }  void recursive_merge_sort(int* data, int low, int high) {     if(low >= high - 1) { return; }      int mid = (high + low) / 2;     recursive_merge_sort(data, low, mid);     recursive_merge_sort(data, mid, high);      merge(data, low, mid, high); }  void merge_sort(int* data, int num_elements) {     recursive_merge_sort(data, 0, num_elements); }  int main() {     int data[] = { 5, 1, 4, 3, 65, 6, 128, 9, 0 };     int num_elements = 9;      std::cout << "unsorted\n";     for(int i=0; i < num_elements; ++i) {         std::cout << data[i] << " ";     }      merge_sort(data, num_elements);      std::cout << "\nsorted\n";     for(int i=0; i < num_elements; ++i) {         std::cout << data[i] << " ";     }      return 0; } 

C++17 implementation

C++20 added the span library under the header <span>. As voluntary exercise (not homework!), I spent approximately 1.5 hours implement it under C++17. Please tell me if I used stuff that is not available under C++17.

Most stuff is in the namespace ::my_std, but tuple_size, etc. are in the namespace ::std, otherwise they are useless. The ::my_std::span_detail namespace contains implementation details that are not to be exposed.

I used the C++ standard draft, HTML version as a reference.

Here is my code, within 400 lines:

// a C++17 implementation of <span>  #ifndef INC_SPAN_HPP_c2GLAK6Onz #define INC_SPAN_HPP_c2GLAK6Onz  #include <array>       // for std::array, etc. #include <cassert>     // for assert #include <cstddef>     // for std::size_t, etc. #include <iterator>    // for std::reverse_iterator, etc. #include <type_traits> // for std::enable_if, etc.  #define CONSTRAINT(...) \   std::enable_if_t<(__VA_ARGS__), int> = 0 #define EXPECTS(...) \   assert((__VA_ARGS__))  namespace my_std {    // constants    // equivalent to std::numeric_limits<std::size_t>::max()   inline constexpr std::size_t dynamic_extent = -1;    // class template span    template <class T, std::size_t N = dynamic_extent>   class span;    namespace span_detail {      // detect specializations of span      template <class T>     struct is_span :std::false_type {};      template <class T, std::size_t N>     struct is_span<span<T, N>> :std::true_type {};      template <class T>     inline constexpr bool is_span_v = is_span<T>::value;      // detect specializations of std::array      template <class T>     struct is_array :std::false_type {};      template <class T, std::size_t N>     struct is_array<std::array<T, N>> :std::true_type {};      template <class T>     inline constexpr bool is_array_v = is_array<T>::value;      // ADL-aware data() and size()      using std::data;     using std::size;      template <class C>     constexpr decltype(auto) my_data(C& c)     {       return data(c);     }      template <class C>     constexpr decltype(auto) my_size(C& c)     {       return size(c);     }      // detect container      template <class C, class = void>     struct is_cont :std::false_type {};      template <class C>     struct is_cont<C,       std::void_t<     std::enable_if_t<!is_span_v<C>>,     std::enable_if_t<!is_array_v<C>>,     std::enable_if_t<!std::is_array_v<C>>,     decltype(data(std::declval<C>())),         decltype(size(std::declval<C>()))     >> :std::true_type {};      template <class C>     inline constexpr bool is_cont_v = is_cont<C>::value;   }    template <class T, std::size_t N>   class span {   public:         // constants and types      using element_type = T;     using value_type = std::remove_cv_t<T>;     using index_type = std::size_t;     using difference_type = std::ptrdiff_t;      using pointer = T*;     using const_pointer = const T*;     using reference = T&;     using const_reference = const T&;      using iterator = T*;     using const_iterator = const T*;     using reverse_iterator = std::reverse_iterator<iterator>;     using const_reverse_iterator = std::reverse_iterator<const_iterator>;      static constexpr index_type extent = N;      // constructors, copy, and assignment      // LWG 3198 applied     constexpr span() noexcept       : size_{0}, data_{nullptr}     {       static_assert(N == dynamic_extent || N == 0);     }      constexpr span(T* ptr, index_type n)       : size_{n}, data_{ptr}     {       EXPECTS(N == dynamic_extent || N == n);     }      constexpr span(T* first, T* last)       : size_{last - first}, data_{first}     {       EXPECTS(N == dynamic_extent || last - first = N);     }      template <std::size_t M,           CONSTRAINT(N == dynamic_extent || N == M              && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<T(&)[M]>()))>(*)[], T(*)[]>)>     constexpr span(T (&arr)[M]) noexcept       : size_{M}, data_{arr}     {     }      template <std::size_t M,               CONSTRAINT(N == dynamic_extent || N == M                  && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<T(&)[M]>()))>(*)[], T(*)[]>)>     constexpr span(std::array<value_type, M>& arr) noexcept       : size_{M}, data_{arr.data()}     {     }      template <std::size_t M,               CONSTRAINT(N == dynamic_extent || N == M                  && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<T(&)[M]>()))>(*)[], T(*)[]>)>     constexpr span(const std::array<value_type, M>& arr) noexcept       : size_{M}, data_{arr.data()}     {     }      template <class Cont,           CONSTRAINT(N == dynamic_extent              && span_detail::is_cont_v<Cont>              && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<Cont>()))>(*)[], T(*)[]>)>     constexpr span(Cont& c)       : size_{span_detail::my_size(c)},         data_{span_detail::my_data(c)}     {     }      template <class Cont,           CONSTRAINT(N == dynamic_extent              && span_detail::is_cont_v<Cont>              && std::is_convertible_v<std::remove_pointer_t<decltype(span_detail::my_data(std::declval<Cont>()))>(*)[], T(*)[]>)>     constexpr span(const Cont& c)       : size_{span_detail::my_size(c)},         data_{span_detail::my_data(c)}     {     }      constexpr span(const span& other) noexcept = default;      template <class U, std::size_t M,           CONSTRAINT(N == dynamic_extent || N == M              && std::is_convertible_v<U(*)[], T(*)[]>)>     constexpr span(const span<U, M>& s) noexcept       : size_{s.size()}, data_{s.data()}     {           }      ~span() noexcept = default;      constexpr span& operator=(const span& other) noexcept = default;      // subviews      template <std::size_t Cnt>     constexpr span<T, Cnt> first() const     {       EXPECTS(Cnt <= size());       return {data(), Cnt};     }      template <std::size_t Cnt>     constexpr span<T, Cnt> last() const     {       EXPECTS(Cnt <= size());       return {data() + (size() - Cnt), Cnt};     }      template <std::size_t Off, std::size_t Cnt = dynamic_extent>     constexpr auto subspan() const     {       EXPECTS(Off <= size() && (Cnt == dynamic_extent || Off + Cnt <= size()));       if constexpr (Cnt != dynamic_extent)         return span<T, Cnt>{data() + Off, Cnt};       else if constexpr (N != dynamic_extent)         return span<T, N - Off>{data() + Off, size() - Off};       else     return span<T, dynamic_extent>{data() + Off, size() - Off};     }      constexpr span<T, dynamic_extent> first(index_type cnt) const     {       EXPECTS(cnt <= size());       return {data(), cnt};     }      constexpr span<T, dynamic_extent> last(index_type cnt) const     {       EXPECTS(cnt <= size());       return {data() + (size() - cnt), cnt};     }      constexpr span<T, dynamic_extent> subspan(index_type off,                           index_type cnt = dynamic_extent) const     {       EXPECTS(off <= size() && (cnt == dynamic_extent || off + cnt <= size()));       return {data() + off, cnt == dynamic_extent ? size() - off : cnt};     }      // observers      constexpr index_type size() const noexcept     {       return size_;     }      constexpr index_type size_bytes() const noexcept     {       return size() * sizeof(T);     }      [[nodiscard]] constexpr bool empty() const noexcept     {       return size() == 0;     }      // element access      constexpr reference operator[](index_type idx) const     {       EXPECTS(idx < size());       return *(data() + idx);     }      constexpr reference front() const     {       EXPECTS(!empty());       return *data();     }      constexpr reference back() const     {       EXPECTS(!empty());       return *(data() + (size() - 1));     }      constexpr pointer data() const noexcept     {       return data_;     }      // iterator support      constexpr iterator begin() const noexcept     {       return data();     }      constexpr iterator end() const noexcept     {       return data() + size();     }      constexpr const_iterator cbegin() const noexcept     {       return data();     }      constexpr const_iterator cend() const noexcept     {       return data() + size();     }      constexpr reverse_iterator rbegin() const noexcept     {       return reverse_iterator{end()};     }      constexpr reverse_iterator rend() const noexcept     {       return reverse_iterator{begin()};     }      constexpr const_reverse_iterator crbegin() const noexcept     {       return reverse_iterator{cend()};     }      constexpr const_reverse_iterator crend() const noexcept     {       return reverse_iterator{cbegin()};     }      friend constexpr iterator begin(span s) noexcept     {       return s.begin();     }      friend constexpr iterator end(span s) noexcept     {       return s.end();     }    private:     pointer data_;     index_type size_;   };    // deduction guide    template <class T, std::size_t N>   span(T (&)[N]) -> span<T, N>;    template <class T, std::size_t N>   span(std::array<T, N>&) -> span<T, N>;    template <class T, std::size_t N>   span(const std::array<T, N>&) -> span<const T, N>;    template <class Cont>   span(Cont&) -> span<typename Cont::value_type>;    template <class Cont>   span(const Cont&) -> span<const typename Cont::value_type>;    // views of objects representation    template <class T, std::size_t N>   auto as_bytes(span<T, N> s) noexcept     -> span<const std::byte,         N == dynamic_extent ? dynamic_extent : sizeof(T) * N>   {     return {reinterpret_cast<const std::byte*>(s.data()), s.size_bytes()};   }    template <class T, std::size_t N,         CONSTRAINT(!std::is_const_v<T>)>   auto as_writable_bytes(span<T, N> s) noexcept     -> span<std::byte,         N == dynamic_extent ? dynamic_extent : sizeof(T) * N>   {     return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};   }  }  namespace std {    // tuple interface   // the primary template declarations are included in <array>    template <class T, std::size_t N>   struct tuple_size<my_std::span<T, N>>     : std::integral_constant<std::size_t, N> {};    // not defined   template <class T>   struct tuple_size<my_std::span<T, my_std::dynamic_extent>>;    template <std::size_t I, class T, std::size_t N>   struct tuple_element<I, my_std::span<T, N>> {     static_assert(N != my_std::dynamic_extent && I < N);     using type = T;   };    template <std::size_t I, class T, std::size_t N>   constexpr T& get(my_std::span<T, N> s) noexcept   {     static_assert(N != my_std::dynamic_extent && I < N);     return s[I];   }  }  #undef CONSTRAINT #undef EXPECTS  #endif 

Constructive criticism is highly appreciated!

A C++17 `std::allocator` implementation

This is an implementation of C++17 std::allocator under the name my_std::allocator, with deprecated stuff omitted for simplicity.

// A implementation of C++17 std::allocator // with deprecated members omitted  #include <cstddef> #include <new> #include <type_traits>  namespace my_std {    template <typename T>   class allocator {   public:     using value_type = T;     using propagate_on_container_move_assignment = std::true_type;     using is_always_equal = std::true_type;      allocator() noexcept = default;     allocator(const allocator&) noexcept = default;     ~allocator() = default;      template <class U>     allocator(const allocator<U>&) noexcept     {     }      T* allocate(std::size_t n)     {       if constexpr (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)         return static_cast<T*>(           ::operator new(n * sizeof(T), static_cast<std::align_val_t>(alignof(T)))         );       else         return static_cast<T*>(           ::operator new(n * sizeof(T))         );     }      void deallocate(T* p, std::size_t n)     {       if constexpr (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)         return ::operator delete(p, n * sizeof(T),                                  static_cast<std::align_val_t>(alignof(T)));       else         return ::operator delete(p, n * sizeof(T));           }   };    template <class T, class U>   bool operator==(const allocator<T>&, const allocator<U>&) noexcept   {     return true;   }    template <class T, class U>   bool operator!=(const allocator<T>&, const allocator<U>&) noexcept   {     return false;   }  } 

I have tested it like this:

int main() {   std::set<std::string, std::less<std::string>,        my_std::allocator<std::string>> words;    for (std::string w; std::cin >> w;)     words.insert(std::move(w));    for (const auto& w : words)     std::cout << w << "\n"; } 

And currently no bug is discovered.

A cartesian product of tuples in C++17

I would like to write a function that computes a cartesian product of two tuples in C++17 (the tuples can be of type std::tuple or std::pair, or any other type that can be used with std::apply). The tuples can be of different types and sizes, and the resulting std::tuple has to contain all std::pairs of elements, where the first element of a pair is from the first tuple, and the second element is from the second tuple. The function must be suitable for use in a constexpr context.

My approach is to use std::apply to effectively convert a tuple to a parameter pack, and then to recursively apply a generic lambda to it to build the result. Because a lambda cannot be explicitly recursive, I pass a reference to it to itself as an additional parameter self.

#include <functional> #include <tuple> #include <utility>  template<class X, class Y> constexpr auto cartesian_product(const X& tx, const Y& ty) {     return std::apply([&](const auto& ... ys) {         return std::apply([&](const auto& ... xs) {             const auto recursive = [&](                 const auto& self,                 const auto& arg, const auto& ... args)              {                 if constexpr (sizeof...(args) == 0)                     return std::make_tuple(std::make_pair(arg, ys)...);                 else                      return std::tuple_cat(                         std::make_tuple(std::make_pair(arg, ys)...),                          self(self, args...));             };             if constexpr (sizeof...(xs) == 0) return std::make_tuple();             else return recursive(recursive, xs...);         }, tx);     }, ty); }   // Test constexpr auto x = std::make_tuple('a', 2); constexpr auto y = std::make_tuple(true, std::optional<long>{}); constexpr auto result = cartesian_product(x, y);  static_assert(result == std::make_tuple(     std::make_pair('a', true),     std::make_pair('a', std::optional<long>{}),     std::make_pair(2,   true),     std::make_pair(2,   std::optional<long>{}))); 

I would appreciate any comments or suggestions how to simplify or improve this code.

Min function accepting varying number of arguments in C++17

Come across this problem once again in the book The Modern C++ Challenge (problem 18). Wonder how simple and elegant the implementation could be using C++17. Following is my solution. Ideas? ^_^

#include <algorithm>  template <typename Less, typename T, typename... Ts> constexpr const T& min(Less less, const T& a, const T& b, const Ts&... rems) {   if constexpr (sizeof...(rems)) {     return min(less, std::min(a, b, less), rems...);   }   else {     return std::min(a, b, less);   } } 

2D counterpart of std::array in C++17

I implemented a 2D counterpart of std::array named array2d in C++17. It is an aggregate like std::array, and provides similar interface. The goal is that if you know how to use std::array, then you will find yourself at home using array2d. Any comments are welcome 🙂 For better viewing experience with highlighting, you can refer to this GitHub page.

#include <cstddef> #include <array> #include <iterator>  template <typename T, std::size_t N0, std::size_t N1> struct array2d {   using row_t = std::array<T, N1>;   inline static constexpr std::array sizes{ N0, N1 };    static constexpr std::size_t size() noexcept { return N0 * N1; }   static constexpr bool empty() noexcept { return !size(); }    T& at(std::size_t i, std::size_t j) { return data_.at(i).at(j); }   const T& at(std::size_t i, std::size_t j) const { return data_.at(i).at(j); }    row_t& operator[](std::size_t i) noexcept { return data_[i]; }   const row_t& operator[](std::size_t i) const noexcept { return data_[i]; }    T& front() { return data_.front().front(); }   const T& front() const { return data_.front().front(); }    T& back() { return data_.back().back(); }   const T& back() const { return data_.back().back(); }    T* data() noexcept { return data_.data()->data(); }   const T* data() const noexcept { return data_.data()->data(); }    T* begin() noexcept { return data(); }   const T* begin() const noexcept { return data(); }    T* end() noexcept { return data() + size(); }   const T* end() const noexcept { return data() + size(); }    auto rbegin() noexcept { return std::make_reverse_iterator(end()); }   auto rbegin() const noexcept { return std::make_reverse_iterator(end()); }    auto rend() noexcept { return std::make_reverse_iterator(begin()); }   auto rend() const noexcept { return std::make_reverse_iterator(begin()); }    void fill(const T& v) {     for (auto& row : data_) {       row.fill(v);     }   }    friend void swap(array2d& a, array2d& b) { a.data_.swap(b.data_); }    std::array<row_t, N0> data_; };