proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: Extend std::hash (tools/extend_hash.hpp) 

namespace std {
  template <class T1, class T2>
  struct hash<std::pair<T1, T2>> {
    std::size_t operator()(const std::pair<T1, T2>& key) const;
  };

  template <class... Args>
  struct hash<std::tuple<Args...>> {
    std::size_t operator()(const std::tuple<Args...>& key) const;
  };
}

It adds some specializations of std::hash. Hereby, it gets possible to compile std::hash<std::pair<T1, T2>> and std::hash<std::tuple<Args...>>.

Warning

This file adds partial specializations for classes in std namespace, for convenience. Strictly speaking, it is not allowed in C++. It makes the program ill-formed to include this file, and may cause undefined behavior.

Constraints

Time Complexity

License

Author

Depends on

Required by

Verified with

Code

#ifndef TOOLS_EXTEND_HASH_HPP
#define TOOLS_EXTEND_HASH_HPP

// WARNING:
// This file adds partial specializations for classes in std namespace, for convenience.
// Strictly speaking, it is not allowed in C++.
// It makes the program ill-formed to include this file, and may cause undefined behavior.

#include <cstddef>
#include <functional>
#include <tuple>
#include <utility>
#include "tools/tuple_hash.hpp"

namespace std {
  template <class T1, class T2>
  struct hash<::std::pair<T1, T2>> {
    ::std::size_t operator()(const ::std::pair<T1, T2>& key) const {
      static const ::tools::tuple_hash<T1, T2> hasher;
      return hasher(::std::make_tuple(key.first, key.second));
    }
  };

  template <class... Args>
  struct hash<::std::tuple<Args...>> {
    ::std::size_t operator()(const ::std::tuple<Args...>& key) const {
      static const ::tools::tuple_hash<Args...> hasher;
      return hasher(key);
    }
  };
}

#endif

#line 1 "tools/extend_hash.hpp"



// WARNING:
// This file adds partial specializations for classes in std namespace, for convenience.
// Strictly speaking, it is not allowed in C++.
// It makes the program ill-formed to include this file, and may cause undefined behavior.

#include <cstddef>
#include <functional>
#include <tuple>
#include <utility>
#line 1 "tools/tuple_hash.hpp"



#line 6 "tools/tuple_hash.hpp"
#include <limits>
#line 1 "tools/now.hpp"



#include <chrono>

namespace tools {
  inline long long now() {
    return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
  }
}


#line 1 "tools/hash_combine.hpp"



#line 6 "tools/hash_combine.hpp"

// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.

// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

namespace tools {
  template <typename T>
  void hash_combine(::std::size_t& seed, const T& v) {
    static const ::std::hash<T> hasher;
    static constexpr ::std::size_t k_mul = 0x9ddfea08eb382d69ULL;
    ::std::size_t a = (hasher(v) ^ seed) * k_mul;
    a ^= (a >> 47);
    ::std::size_t b = (seed ^ a) * k_mul;
    b ^= (b >> 47);
    seed = b * k_mul;
  }
}


#line 11 "tools/tuple_hash.hpp"

namespace tools {
  template <typename... Ts>
  struct tuple_hash {
    template <::std::size_t I = sizeof...(Ts) - 1>
    ::std::size_t operator()(const ::std::tuple<Ts...>& key) const {
      if constexpr (I == ::std::numeric_limits<::std::size_t>::max()) {
        static const ::std::size_t seed = ::tools::now();
        return seed;
      } else {
        ::std::size_t seed = this->operator()<I - 1>(key);
        ::tools::hash_combine(seed, ::std::get<I>(key));
        return seed;
      }
    }
  };
}


#line 14 "tools/extend_hash.hpp"

namespace std {
  template <class T1, class T2>
  struct hash<::std::pair<T1, T2>> {
    ::std::size_t operator()(const ::std::pair<T1, T2>& key) const {
      static const ::tools::tuple_hash<T1, T2> hasher;
      return hasher(::std::make_tuple(key.first, key.second));
    }
  };

  template <class... Args>
  struct hash<::std::tuple<Args...>> {
    ::std::size_t operator()(const ::std::tuple<Args...>& key) const {
      static const ::tools::tuple_hash<Args...> hasher;
      return hasher(key);
    }
  };
}
Back to top page