fork download
  1. #include <iostream>
  2. #include <utility>
  3. #include <cassert>
  4. #include <stdexcept>
  5. #include <type_traits>
  6. #include <array>
  7.  
  8. #include <experimental/string_view>
  9.  
  10.  
  11.  
  12. // #define USE_TEMPLATES
  13.  
  14. namespace {
  15.  
  16. ////////////////////////////////////////////////////////////////////////////////
  17. /// I used this class in place of `std::runtime_error` because GCC has
  18. /// trouble inlining/evaluating constexpr code that uses `std::runtime_error`.
  19. ////////////////////////////////////////////////////////////////////////////////
  20. struct key_not_found_error : std::exception {
  21. auto what() const noexcept -> char const* override
  22. {
  23. return "Key not found.";
  24. }
  25. };
  26.  
  27.  
  28. template < class _Pair
  29. , class _Key
  30. , std::size_t _N
  31. , class _Pred
  32. >
  33. __attribute__((always_inline))
  34. inline
  35. constexpr
  36. auto ls_at_impl( _Pair const (&values) [_N]
  37. , _Key&& key
  38. , _Pred&& equal )
  39. {
  40. std::size_t i = 0;
  41. while (i < _N and not equal(values[i].first, key)) {
  42. ++i;
  43. }
  44. return i;
  45. }
  46.  
  47.  
  48. ////////////////////////////////////////////////////////////////////////////////
  49. /// LINEAR SEARCH.
  50. ////////////////////////////////////////////////////////////////////////////////
  51. template < class _Pair
  52. , class _Key
  53. , std::size_t _N
  54. , class _Pred
  55. >
  56. __attribute__((always_inline))
  57. inline
  58. constexpr
  59. // Notice the decltype(auto) -- we want to return a by reference rather than
  60. // by value.
  61. decltype(auto) ls_at( _Pair (&values) [_N]
  62. , _Key&& key
  63. , _Pred&& equal )
  64. {
  65. auto const i = ls_at_impl( values
  66. , std::forward<_Key>(key)
  67. , std::forward<_Pred>(equal) );
  68. return i != _N
  69. ? values[i].second
  70. : (throw key_not_found_error{}, values[0].second);
  71. }
  72.  
  73.  
  74. ////////////////////////////////////////////////////////////////////////////////
  75. /// ITERATORS
  76. ////////////////////////////////////////////////////////////////////////////////
  77. template < class _Key, class _Tp
  78. , std::size_t _N
  79. , bool _is_const // allows us to write a single struct for both
  80. // const and non-const iterators
  81. >
  82. struct map_iterator {
  83. using difference_type = std::ptrdiff_t;
  84. using value_type =
  85. std::conditional_t< _is_const
  86. , std::pair<_Key const, _Tp> const
  87. , std::pair<_Key const, _Tp> >;
  88. using pointer = std::add_pointer_t<value_type>;
  89. using reference = std::add_lvalue_reference_t<value_type>;
  90. using iterator_category = std::random_access_iterator_tag;
  91.  
  92. private:
  93. using _iterator = map_iterator<_Key, _Tp, _N, _is_const>;
  94. using _const_iterator = map_iterator<_Key, _Tp, _N, /*is_const = */ true>;
  95.  
  96. static constexpr std::size_t _size = _N;
  97.  
  98. // We store a pointer rather than a reference, because we need
  99. // map_iterator to be default constructible.
  100. value_type (*_vs)[_size];
  101. std::size_t _i;
  102.  
  103. public:
  104. constexpr
  105. map_iterator() noexcept
  106. : _vs{ nullptr }
  107. , _i{ 0 }
  108. {}
  109.  
  110. constexpr
  111. map_iterator( value_type (&values)[_size]
  112. , std::size_t const pos ) noexcept
  113. : _vs{ &values }
  114. , _i{ pos }
  115. {}
  116.  
  117. constexpr map_iterator(_iterator const& other) noexcept = default;
  118. constexpr _iterator& operator=(_iterator const& other) noexcept = default;
  119.  
  120. __attribute__((always_inline))
  121. constexpr auto operator*() const -> reference
  122. {
  123. return _vs != nullptr
  124. ? ( _i < _N
  125. ? (*_vs)[_i]
  126. : ( throw std::out_of_range{"Iterator not dereferenceable."}
  127. , (*_vs)[0] )
  128. )
  129. : ( throw std::invalid_argument{"Iterator not dereferenceable."}
  130. , (*_vs)[0] );
  131. }
  132.  
  133. constexpr auto operator->() const -> pointer
  134. { return &(*(*this)); }
  135.  
  136. __attribute__((always_inline))
  137. constexpr auto operator++() noexcept -> _iterator&
  138. { ++_i; return *this; }
  139.  
  140. __attribute__((always_inline))
  141. constexpr auto operator++(int) noexcept -> _iterator
  142. {
  143. _iterator saved{ *this };
  144. ++(*this);
  145. return saved;
  146. }
  147.  
  148. __attribute__((always_inline))
  149. constexpr
  150. auto operator-(_iterator const& other) const
  151. -> difference_type
  152. {
  153. return _vs == other._vs
  154. ? (_i - other._i)
  155. : ( throw std::invalid_argument{"Iterators not comparable."}
  156. , 0 );
  157. }
  158.  
  159. __attribute__((always_inline))
  160. constexpr auto operator==(_iterator const& other) const -> bool
  161. { return (_vs == other._vs) and (_i == other._i); }
  162.  
  163. __attribute__((always_inline))
  164. constexpr auto operator!=(_iterator const& other) const -> bool
  165. { return not (*this == other); }
  166.  
  167. __attribute__((always_inline))
  168. constexpr auto operator< (_iterator const& other) const -> bool
  169. { return (*this - other) < 0; }
  170.  
  171. __attribute__((always_inline))
  172. constexpr auto operator<=(_iterator const& other) const -> bool
  173. { return (*this - other) <= 0; }
  174.  
  175. __attribute__((always_inline))
  176. constexpr auto operator> (_iterator const& other) const -> bool
  177. { return (*this - other) > 0; }
  178.  
  179. __attribute__((always_inline))
  180. constexpr auto operator>=(_iterator const& other) const -> bool
  181. { return (*this - other) >= 0; }
  182.  
  183.  
  184. constexpr auto operator[](difference_type const n) const -> reference
  185. { return *(*this + n); }
  186.  
  187.  
  188. constexpr
  189. operator _const_iterator() const noexcept
  190. { return {_vs, _i}; }
  191.  
  192. friend
  193. constexpr auto swap(_iterator& lhs, _iterator& rhs) noexcept -> void
  194. {
  195. auto const _temp_idx = lhs._i;
  196. lhs._i = rhs._i;
  197. rhs._i = _temp_idx;
  198.  
  199. auto& _temp_values = lhs._vs;
  200. lhs._vs = rhs._vs;
  201. rhs._vs = _temp_values;
  202. }
  203.  
  204. friend
  205. constexpr auto operator+ ( _iterator const& x
  206. , difference_type const n ) noexcept -> _iterator
  207. { return _iterator{*(x._vs), x._i + n}; }
  208.  
  209. friend
  210. constexpr auto operator+ ( difference_type const n
  211. , _iterator const& x ) noexcept -> _iterator
  212. { return x + n; }
  213.  
  214. friend
  215. constexpr auto operator- ( _iterator const& x
  216. , difference_type const n ) noexcept -> _iterator
  217. { return _iterator{*(x._vs), x._i - n}; }
  218.  
  219. friend
  220. constexpr auto operator+=( _iterator & x
  221. , difference_type const n ) noexcept -> _iterator&
  222. { return x = x + n; }
  223.  
  224. friend
  225. constexpr auto operator-=( _iterator & x
  226. , difference_type const n ) noexcept -> _iterator&
  227. { return x = x - n; }
  228.  
  229.  
  230. };
  231.  
  232. template <class _Key, class _Tp, std::size_t _N, bool _is_const>
  233. constexpr std::size_t map_iterator<_Key, _Tp, _N, _is_const>::_size;
  234.  
  235.  
  236.  
  237. template <class _T, std::size_t _N, class = void>
  238. struct hash_c;
  239.  
  240.  
  241. template < class _T
  242. , std::size_t _N
  243. >
  244. struct hash_c<_T, _N, std::enable_if_t<std::is_integral<_T>::value>> {
  245. constexpr auto operator()(_T const x) const noexcept
  246. {
  247. return static_cast<std::size_t>(x) % _N;
  248. }
  249. };
  250.  
  251.  
  252.  
  253. template < class _RAIterator
  254. , class _Pred
  255. >
  256. __attribute__((always_inline))
  257. inline
  258. constexpr
  259. auto find_if_c( _RAIterator&& first, _RAIterator&& last
  260. , _Pred&& p ) noexcept
  261. {
  262. auto const _count = last - first;
  263. auto i = first;
  264. typename std::iterator_traits<_RAIterator>::difference_type n = 0;
  265.  
  266. while (n < _count and not p(*i)) {
  267. ++n; ++i;
  268. }
  269.  
  270. return n == _count ? last : i;
  271. }
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282. } // unnamed namespace
  283.  
  284.  
  285.  
  286.  
  287. ////////////////////////////////////////////////////////////////////////////////
  288. /// That is the actual static_map
  289. ////////////////////////////////////////////////////////////////////////////////
  290. template < class _Key
  291. , class _Tp
  292. , size_t _N
  293. , class _Pred = std::equal_to<_Key>
  294. , class _Hash = hash_c<_Key, _N>
  295. >
  296. class static_map {
  297.  
  298. public:
  299. using key_type = _Key;
  300. using mapped_type = _Tp;
  301. using key_equal = _Pred;
  302. using hasher = _Hash;
  303.  
  304. using value_type = std::pair<key_type const, mapped_type>;
  305. using reference = value_type &;
  306. using const_reference = value_type const&;
  307. using iterator = map_iterator< key_type
  308. , mapped_type
  309. , _N
  310. , /*is_const =*/ false >;
  311. using const_iterator = map_iterator< key_type
  312. , mapped_type
  313. , _N
  314. , /*is_const =*/ true >;
  315. using difference_type = typename std::iterator_traits<iterator>
  316. ::difference_type;
  317. using size_type = std::size_t;
  318.  
  319. private:
  320. key_equal const _eq;
  321. hasher const _hf;
  322. public:
  323. value_type _vs[_N];
  324. private:
  325.  
  326.  
  327. __attribute__((always_inline))
  328. constexpr
  329. auto _lookup(key_type const& k) const noexcept
  330. {
  331. auto const guess = _hf(k);
  332. auto i = guess;
  333.  
  334. while (i < _N and not _eq(_vs[i].first, k)) { ++i; }
  335.  
  336. if (i == _N) {
  337. i = 0;
  338. while (i < guess and not _eq(_vs[i].first, k)) { ++i; }
  339.  
  340. if (i == guess) return _N;
  341. }
  342.  
  343. return i;
  344. }
  345.  
  346.  
  347.  
  348. public:
  349. template <class... _K, class... _V>
  350. constexpr
  351. static_map(std::pair<_K, _V> const&... values)
  352. : _eq{}
  353. , _hf{}
  354. , _vs{ values... }
  355. {
  356. // bool initialised[_N] = {false};
  357. // _init_impl(initialised, values...);
  358. }
  359.  
  360. /*
  361. template <class... _K, class... _V>
  362. constexpr
  363. static_map( key_equal equal, hasher hash_function
  364. , std::pair<_K, _V> const&... values )
  365. : _vs{ values... }
  366. , _eq{ std::move(equal) }
  367. , _hf{ std::move(hash_function) }
  368. {
  369. }
  370. */
  371.  
  372. constexpr auto size() const noexcept -> size_type
  373. { return _N; }
  374.  
  375. constexpr auto begin() noexcept -> iterator
  376. { return {_vs, 0}; }
  377.  
  378. constexpr auto end() noexcept -> iterator
  379. { return {_vs, size()}; }
  380.  
  381. constexpr auto cbegin() const noexcept -> const_iterator
  382. { return {_vs, 0}; }
  383.  
  384. constexpr auto cend() const noexcept -> const_iterator
  385. { return {_vs, size()}; }
  386.  
  387. __attribute__((always_inline))
  388. constexpr
  389. auto find(key_type const& k) const noexcept -> const_iterator
  390. {
  391. auto i = _lookup(k);
  392. return i == _N
  393. ? cend()
  394. : const_iterator{_vs, i};
  395. /*
  396. struct local_equal {
  397. key_type const& _key;
  398. key_equal const& _eq;
  399.  
  400. constexpr
  401. local_equal( key_type const& key
  402. , key_equal const& equal )
  403. : _key{ key }
  404. , _eq{ equal }
  405. {}
  406.  
  407. __attribute__((always_inline))
  408. constexpr auto operator()(value_type const& i) const noexcept
  409. { return _eq(_key, i.first); }
  410. };
  411.  
  412. return find_if( cbegin(), cend()
  413. , local_equal{k, _equal} );
  414. */
  415. }
  416.  
  417. constexpr
  418. auto count(key_type const& k) const noexcept -> size_type
  419. { return find(k) == cend() ? 0 : 1; }
  420.  
  421.  
  422. __attribute__((always_inline))
  423. constexpr
  424. auto at(key_type const& k) const -> mapped_type const&
  425. {
  426. auto i = _lookup(k);
  427. return i != _N
  428. ? _vs[i].second
  429. : (throw key_not_found_error{}, _vs[0].second);
  430. // return ls_at(_vs, k, _eq);
  431. }
  432.  
  433. __attribute__((always_inline))
  434. constexpr
  435. auto at(key_type const& k) -> mapped_type&
  436. {
  437. auto i = _lookup(k);
  438. return i != _N
  439. ? _vs[i].second
  440. : (throw key_not_found_error{}, _vs[0].second);
  441. // return ls_at(_vs, k, _eq);
  442. }
  443.  
  444. __attribute__((always_inline))
  445. constexpr
  446. auto operator[](key_type const& k) const -> mapped_type const&
  447. { return at(k); }
  448.  
  449. };
  450.  
  451.  
  452.  
  453. namespace {
  454.  
  455. template < class _Key
  456. , class _Tp
  457. , size_t _N
  458. , size_t... _Is
  459. >
  460. inline
  461. constexpr auto static_map_from_array
  462. ( std::pair<const _Key, _Tp> const (&il)[_N]
  463. , std::index_sequence<_Is...> )
  464. {
  465. return static_map<_Key, _Tp, _N>{ il[_Is]...};
  466. }
  467.  
  468. /*
  469. template < class _Key
  470.   , class _Tp
  471.   , size_t _N
  472.   , size_t... _Is
  473. , class _Pred
  474.   >
  475. inline
  476. constexpr auto static_map_from_array
  477. ( std::pair<const _Key, _Tp> const (&il)[_N]
  478. , std::index_sequence<_Is...>
  479.   , _Pred&& equal )
  480. {
  481. return static_map<_Key, _Tp, _N, _Pred>
  482. { std::forward<_Pred>(equal)
  483. , il[_Is]... };
  484. }
  485. */
  486. } // unnamed namespace
  487.  
  488.  
  489.  
  490. template < class _Key
  491. , class _Tp
  492. , size_t _N
  493. >
  494. __attribute__((always_inline))
  495. inline
  496. constexpr auto make_static_map(std::pair<const _Key, _Tp> const (&il)[_N])
  497. -> static_map<_Key, _Tp, _N>
  498. {
  499. return static_map_from_array<_Key, _Tp, _N>
  500. (il, std::make_index_sequence<_N>{});
  501. }
  502.  
  503.  
  504. /*
  505. template < class _Key
  506.   , class _Tp
  507.   , size_t _N
  508. , class _Pred
  509.   >
  510. __attribute__((always_inline))
  511. inline
  512. constexpr auto make_static_map( std::pair<const _Key, _Tp> const (&il)[_N]
  513.   , _Pred&& equal )
  514. -> static_map<_Key, _Tp, _N, _Pred>
  515. {
  516. return static_map_from_array
  517. ( il
  518. , std::make_index_sequence<_N>{}
  519. , std::forward<_Pred>(equal) );
  520. }
  521. */
  522.  
  523. template <std::size_t _N>
  524. __attribute__((always_inline))
  525. inline
  526. constexpr
  527. auto _insert( std::size_t const index
  528. , std::size_t const guess
  529. , std::size_t (&indices)[_N] )
  530. {
  531. auto i = guess;
  532.  
  533. while (i < _N and indices[i] != _N) {
  534. ++i;
  535. }
  536.  
  537. if (i == _N) {
  538. i = 0;
  539. while (i < guess and indices[i] != _N) {
  540. ++i;
  541. }
  542. }
  543.  
  544. indices[i] = index;
  545. }
  546.  
  547.  
  548. template <std::size_t _N>
  549. __attribute__((always_inline))
  550. inline
  551. constexpr
  552. auto _init_impl( std::size_t (&indices)[_N]
  553. , std::pair<std::size_t, std::size_t> const& x )
  554. {
  555. _insert(x.first, x.second, indices);
  556. }
  557.  
  558. template <std::size_t _N, class... _I>
  559. __attribute__((always_inline))
  560. inline
  561. constexpr
  562. auto _init_impl( std::size_t (&indices)[_N]
  563. , std::pair<std::size_t, std::size_t> const& x
  564. , std::pair<_I, _I> const&... xs )
  565. {
  566. _insert(x.first, x.second, indices);
  567. _init_impl(indices, xs...);
  568. }
  569.  
  570.  
  571. template < class _K
  572. , class _V
  573. , std::size_t _N
  574. , std::size_t... _Is
  575. >
  576. __attribute__((always_inline))
  577. inline
  578. constexpr
  579. auto _initialise( std::pair<_K const, _V> const (&il)[_N]
  580. , std::index_sequence<_Is...> )
  581. {
  582. std::size_t indices[_N] = {((void)_Is, _N)...};
  583. hash_c<_K, _N> const hf;
  584.  
  585. _init_impl(indices, std::make_pair(_Is, hf(il[_Is].first))...);
  586.  
  587. return static_map<_K, _V, _N>{ il[indices[_Is]]...};
  588. }
  589.  
  590. template < class _K
  591. , class _V
  592. , std::size_t _N
  593. , std::size_t... _Is
  594. >
  595. __attribute__((always_inline))
  596. inline
  597. constexpr
  598. auto initialise(std::pair<_K const, _V> const (&il)[_N])
  599. {
  600. return _initialise(il, std::make_index_sequence<_N>{});
  601. }
  602.  
  603.  
  604.  
  605. enum class weekday { sunday, monday, tuesday, wednesday, thursday, friday, saturday };
  606.  
  607. #define STRING_VIEW(str) std::experimental::string_view{ str, sizeof(str)-1 }
  608. constexpr std::pair<const std::experimental::string_view, weekday>
  609. string_to_weekday[]
  610. { { STRING_VIEW("sunday"), weekday::sunday }
  611. , { STRING_VIEW("monday"), weekday::monday }
  612. , { STRING_VIEW("tuesday"), weekday::tuesday }
  613. , { STRING_VIEW("wednesday"), weekday::wednesday }
  614. , { STRING_VIEW("thursday"), weekday::thursday }
  615. , { STRING_VIEW("friday"), weekday::friday }
  616. , { STRING_VIEW("saturday"), weekday::saturday }
  617. };
  618.  
  619.  
  620. namespace {
  621. __attribute__((always_inline))
  622. inline
  623. constexpr
  624. auto cstrcmp(char const* a, char const* b) noexcept -> int
  625. {
  626. std::size_t i = 0;
  627. for (; a[i] != '\0' and b[i] != '\0'; ++i)
  628. {
  629. if (a[i] < b[i]) return -1;
  630. if (a[i] > b[i]) return 1;
  631. }
  632. if (a[i] == '\0' and b[i] != '\0') return -1;
  633. if (a[i] != '\0' and b[i] == '\0') return 1;
  634. return 0;
  635. }
  636. }
  637.  
  638.  
  639. struct equal_string_view {
  640. constexpr
  641. auto operator()( std::experimental::string_view const& a
  642. , std::experimental::string_view const& b ) const noexcept
  643. -> bool
  644. {
  645. return !cstrcmp(a.data(), b.data());
  646. }
  647. };
  648.  
  649.  
  650.  
  651.  
  652. // constexpr
  653. // static
  654. // auto cmap2 = cmap;
  655. // make_static_map(map_data);
  656. // constexpr auto to_weekday = make_static_map(string_to_weekday, equal_string_view{});
  657.  
  658.  
  659.  
  660. int main(void)
  661. {
  662. {
  663. // Compile-time stuff
  664. constexpr std::pair<int const, const char *> map_data[] =
  665. { { 5, "apple" }
  666. , { 8, "pear" }
  667. , { 0, "banana" }
  668. };
  669. constexpr auto cmap = initialise(map_data);
  670.  
  671. static_assert(cmap._vs[0].first == 8);
  672. static_assert(cmap._vs[1].first == 0);
  673. static_assert(cmap._vs[2].first == 5);
  674.  
  675. // Easy
  676. // No abort call in assembly
  677. if (!cmap.count(8)) abort();
  678.  
  679. // These operations use hashing
  680. static_assert(!cstrcmp(cmap[5], "apple"));
  681. static_assert(!cstrcmp(cmap[8], "pear"));
  682. static_assert(!cstrcmp(cmap[0], "banana"));
  683.  
  684. // This fails to compile -- as expected.
  685. // auto foo = cmap[-1];
  686.  
  687. // We need this because GCC does not support constexpr lambdas, yet.
  688. struct is_eight {
  689. constexpr auto operator()(std::pair<int, char const*> const& x)
  690. const noexcept
  691. { return x.first == 8; }
  692. };
  693. // Iterators
  694. static_assert( find_if_c(cmap.cbegin(), cmap.cend(), is_eight{})
  695. != cmap.cend() );
  696. }
  697.  
  698. {
  699. // Run-time stuff
  700. constexpr std::pair<int const, const char *> map_data[] =
  701. { { 5, "apple" }
  702. , { 8, "pear" }
  703. , { 0, "banana" }
  704. };
  705. auto cmap = initialise(map_data);
  706.  
  707. // No abort in assembly
  708. if (!cmap[8]) abort();
  709. if (!cmap.count(5)) abort();
  710.  
  711. // Values are mutable !!
  712. auto& i = cmap.at(8);
  713. i = "orange";
  714. // This one is nice!
  715. assert(!cstrcmp(cmap[8], "orange"));
  716.  
  717. // Iterators
  718. auto const it1 = cmap.find(8);
  719. assert(it1->first == 8);
  720. }
  721.  
  722. // auto& bar = cmap2.at(5);
  723. // bar = "orange";
  724.  
  725. // std::cout << foo << '\n';
  726.  
  727. // The following does not compile
  728. // constexpr auto b = cmap[-2];
  729. // cmap.at(5) = "orange";
  730.  
  731.  
  732. // constexpr auto
  733. // i = find_if( cmap.cbegin()
  734. // , cmap.cend()
  735. // , is_eight) + 1;
  736. // static_assert( !cstrcmp(((-1) + i)->second, "pear"), "" );
  737.  
  738. // std::cout << find_if( cmap.cbegin()
  739. // , cmap.cend()
  740. // , [](auto p) { return p.first == 8; } )->second
  741. // << '\n';
  742.  
  743. // std::cout << cmap.find(0)->second << '\n';
  744.  
  745.  
  746. // static_assert(to_weekday[STRING_VIEW("thursday")] == weekday::thursday, "");
  747. // auto tuesday = to_weekday[STRING_VIEW("tuesday")];
  748.  
  749. // std::cout << static_cast<int>(tuesday) << '\n';
  750. // return 0;
  751. }
  752.  
Success #stdin #stdout 0s 15240KB
stdin
Standard input is empty
stdout

Standard output is empty