PerfectHashMap.h

Go to the documentation of this file.

/*
 * MIT License
 *
 * Copyright (c) 2025 nfx
 *
 * 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.
 */

 
#pragma once
 
#include <nfx/Hashing.h>
 
#include <cstdint>
#include <cstddef>
#include <functional>
#include <iterator>
#include <optional>
#include <string>
#include <string_view>
#include <type_traits>
#include <vector>
 
namespace nfx::containers
{
    //=====================================================================
    // PerfectHashMap class
    //=====================================================================

    template <typename TKey,
        typename TValue,
        hashing::Hash32or64 HashType = uint32_t,
        HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ),
        typename Hasher = hashing::Hasher<HashType, Seed>,
        typename KeyEqual = std::equal_to<>>
    class PerfectHashMap final
    {
    public:
        //----------------------------------------------
        // Forward declarations for iterator support
        //----------------------------------------------
 
        class Iterator;
 
        //----------------------------------------------
        // Type aliases
        //----------------------------------------------

        using key_type = TKey;

        using mapped_type = TValue;

        using value_type = std::pair<TKey, TValue>;

        using hasher = Hasher;

        using key_equal = KeyEqual;

        using hash_type = HashType;

        using seed_type = std::make_signed_t<hash_type>;

        using size_type = size_t;

        using difference_type = std::ptrdiff_t;

        using iterator = Iterator;

        using const_iterator = Iterator;

        using ConstIterator = Iterator;
 
        //----------------------------------------------
        // Construction
        //----------------------------------------------

        inline explicit PerfectHashMap( std::vector<std::pair<TKey, TValue>>&& items );

        PerfectHashMap() = default;

        PerfectHashMap( const PerfectHashMap& ) = default;

        PerfectHashMap( PerfectHashMap&& ) noexcept = default;
 
        //----------------------------------------------
        // Destruction
        //----------------------------------------------

        ~PerfectHashMap() = default;
 
        //----------------------------------------------
        // Assignment
        //----------------------------------------------

        PerfectHashMap& operator=( const PerfectHashMap& ) = default;

        PerfectHashMap& operator=( PerfectHashMap&& ) noexcept = default;
 
        //----------------------------------------------
        // Comparison
        //----------------------------------------------

        [[nodiscard]] inline bool operator==( const PerfectHashMap& other ) const noexcept;

        [[nodiscard]] inline bool operator!=( const PerfectHashMap& other ) const noexcept;
 
        //----------------------------------------------
        // Element access
        //----------------------------------------------

        template <typename K>
        inline const TValue& at( const K& key ) const;
 
        //----------------------------------------------
        // Lookup
        //----------------------------------------------

        template <typename K>
        [[nodiscard]] inline bool contains( const K& key ) const noexcept;

        template <typename K>
        [[nodiscard]] inline const TValue* find( const K& key ) const noexcept;
 
        //----------------------------------------------
        // Capacity
        //----------------------------------------------

        [[nodiscard]] inline size_type size() const noexcept;

        [[nodiscard]] inline size_type count() const noexcept;

        [[nodiscard]] inline bool isEmpty() const noexcept;
 
        //----------------------------------------------
        // Iterators
        //----------------------------------------------

        [[nodiscard]] inline Iterator begin() const noexcept;

        [[nodiscard]] inline Iterator end() const noexcept;

        [[nodiscard]] inline ConstIterator cbegin() const noexcept;

        [[nodiscard]] inline ConstIterator cend() const noexcept;
 
        //----------------------------------------------
        // Hash policy
        //----------------------------------------------

        inline hasher hash_function() const;

        inline key_equal key_eq() const;
 
        //----------------------------------------------
        // PerfectHashMap::Iterator class
        //----------------------------------------------

        class Iterator final
        {
        public:
            using iterator_category = std::forward_iterator_tag;

            using value_type = std::pair<TKey, TValue>;

            using difference_type = std::ptrdiff_t;

            using pointer = const value_type*;

            using reference = const value_type&;
 
            //---------------------------
            // Construction
            //---------------------------

            inline Iterator( const std::vector<std::optional<std::pair<TKey, TValue>>>* table, size_t index );
 
            //---------------------------
            // Operations
            //---------------------------

            inline reference operator*() const;

            inline pointer operator->() const;

            inline Iterator& operator++();

            inline Iterator operator++( int );
 
            //---------------------------
            // Comparison
            //---------------------------

            inline bool operator==( const Iterator& other ) const;

            inline bool operator!=( const Iterator& other ) const;
 
        private:
            //---------------------------
            // Private methods
            //---------------------------

            inline void skipEmpty();
 
            //---------------------------
            // Private members
            //---------------------------
 
            const std::vector<std::optional<std::pair<TKey, TValue>>>* m_table; 
            size_t m_index;                                                     
        };
 
    private:
        size_t m_itemCount = 0;                                      
        std::vector<std::optional<std::pair<TKey, TValue>>> m_table; 
        std::vector<seed_type> m_seeds;                              
        hasher m_hasher;                                             
        KeyEqual m_keyEqual;                                         
    };
} // namespace nfx::containers
 
#include "nfx/detail/containers/PerfectHashMap.inl"