OrderedHashSet.h

Go to the documentation of this file.

/*
 * MIT License
 *
 * Copyright (c) 2026 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/detail/containers/CompilerSupport.h"
 
#include <nfx/Hashing.h>
 
#include <algorithm>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace nfx::containers
{
    //=====================================================================
    // OrderedHashSet class
    //=====================================================================

    template <typename TKey,
        hashing::Hash32or64 HashType = uint32_t,
        HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ),
        typename THasher = hashing::Hasher<HashType, Seed>,
        typename KeyEqual = std::equal_to<>>
    class OrderedHashSet final
    {
        //----------------------------------------------
        // Compile-time type constraints
        //----------------------------------------------
 
        static_assert( std::is_same_v<HashType, uint32_t> || std::is_same_v<HashType, uint64_t>,
            "HashType must be uint32_t or uint64_t" );
 
        static_assert( std::is_invocable_r_v<HashType, THasher, TKey>,
            "THasher must be callable with TKey and return HashType" );
 
        static_assert( std::is_invocable_r_v<bool, KeyEqual, TKey, TKey>,
            "KeyEqual must be callable with two TKey arguments and return bool" );
 
    public:
        //----------------------------------------------
        // Forward declarations for iterator support
        //----------------------------------------------
 
        class Iterator;
        class ConstIterator;
 
        //----------------------------------------------
        // STL-compatible type aliases
        //----------------------------------------------

        using key_type = TKey;

        using value_type = TKey;

        using hasher = THasher;

        using key_equal = KeyEqual;

        using hash_type = HashType;

        using size_type = size_t;

        using difference_type = std::ptrdiff_t;

        using iterator = Iterator;

        using const_iterator = ConstIterator;
 
        //----------------------------------------------
        // Construction
        //----------------------------------------------

        inline OrderedHashSet();

        inline OrderedHashSet( std::initializer_list<TKey> init );

        template <typename InputIt>
        inline OrderedHashSet( InputIt first, InputIt last );

        inline explicit OrderedHashSet( size_t initialCapacity );

        OrderedHashSet( OrderedHashSet&& other ) noexcept;

        OrderedHashSet& operator=( OrderedHashSet&& other ) noexcept;

        OrderedHashSet( const OrderedHashSet& other );

        OrderedHashSet& operator=( const OrderedHashSet& other );

        ~OrderedHashSet();
 
        //----------------------------------------------
        // Core operations
        //----------------------------------------------

        template <typename KeyType = TKey>
        [[nodiscard]] inline const TKey* find( const KeyType& key ) const noexcept;

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

        template <typename KeyType = TKey>
        inline const TKey& at( const KeyType& key ) const;
 
        //----------------------------------------------
        // Insertion
        //----------------------------------------------

        inline bool insert( const TKey& key );

        inline bool insert( TKey&& key );
 
        //----------------------------------------------
        // Emplace operations
        //----------------------------------------------

        template <typename... Args>
        inline bool emplace( Args&&... args );

        template <typename... Args>
        inline std::pair<Iterator, bool> tryEmplace( Args&&... args );
 
        //----------------------------------------------
        // Capacity and memory management
        //----------------------------------------------

        inline void reserve( size_t minCapacity );

        template <typename KeyType = TKey>
        inline bool erase( const KeyType& key ) noexcept;

        inline Iterator erase( ConstIterator pos ) noexcept;

        inline Iterator erase( ConstIterator first, ConstIterator last ) noexcept;

        inline void clear() noexcept;

        template <typename KeyType = TKey>
        [[nodiscard]] inline std::optional<TKey> extract( const KeyType& key );

        inline void merge( OrderedHashSet& other );

        inline void merge( OrderedHashSet&& other );
 
        //----------------------------------------------
        // State inspection
        //----------------------------------------------

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

        [[nodiscard]] inline size_t capacity() const noexcept;

        [[nodiscard]] inline bool isEmpty() const noexcept;

        inline void swap( OrderedHashSet& other ) noexcept;
 
        //----------------------------------------------
        // STL-compatible iteration support (insertion order)
        //----------------------------------------------

        [[nodiscard]] Iterator begin() noexcept;

        [[nodiscard]] ConstIterator begin() const noexcept;

        [[nodiscard]] Iterator end() noexcept;

        [[nodiscard]] ConstIterator end() const noexcept;

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

        [[nodiscard]] ConstIterator cend() const noexcept;

        [[nodiscard]] bool operator==( const OrderedHashSet& other ) const noexcept;
 
    private:
        //----------------------------------------------
        // Node structure for doubly-linked list
        //----------------------------------------------

        struct Node
        {
            TKey data;       
            Node* prev{};    
            Node* next{};    
            HashType hash{}; 
        };
 
        //----------------------------------------------
        // Robin Hood Hashing bucket structure
        //----------------------------------------------

        struct Bucket
        {
            Node* node{};        
            HashType hash{};     
            uint32_t distance{}; 
            bool occupied{};     
        };

        static constexpr size_t INITIAL_CAPACITY = 32;

        static constexpr size_t MAX_LOAD_FACTOR_PERCENT = 75;

        std::vector<Bucket> m_buckets;
 
        Node* m_head{};                        
        Node* m_tail{};                        
        size_t m_size{};                       
        size_t m_capacity{ INITIAL_CAPACITY }; 
        size_t m_mask{ INITIAL_CAPACITY - 1 }; 

        NFX_CONTAINERS_NO_UNIQUE_ADDRESS hasher m_hasher;

        NFX_CONTAINERS_NO_UNIQUE_ADDRESS KeyEqual m_keyEqual;
 
        //----------------------------------------------
        // Internal implementation
        //----------------------------------------------

        inline bool insertInternal( const TKey& key );

        inline bool insertInternal( TKey&& key );

        inline bool shouldResize() const noexcept;

        inline void resize();

        inline void eraseAtPosition( size_t pos ) noexcept;

        inline void unlinkNode( Node* node ) noexcept;

        inline void appendNode( Node* node ) noexcept;

        template <typename KeyType1, typename KeyType2>
        inline bool keysEqual( const KeyType1& k1, const KeyType2& k2 ) const noexcept;
 
    public:
        //----------------------------------------------
        // OrderedHashSet::Iterator class
        //----------------------------------------------

        class Iterator
        {
            friend class ConstIterator;
            friend class OrderedHashSet;
 
        public:
            using iterator_category = std::bidirectional_iterator_tag;

            using value_type = const TKey;

            using difference_type = std::ptrdiff_t;

            using pointer = const TKey*;

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

            Iterator() = default;

            inline explicit Iterator( Node* node );
 
            //---------------------------
            // Operations
            //---------------------------

            inline reference operator*() const;

            inline pointer operator->() const;

            inline Iterator& operator++();

            inline Iterator operator++( int );

            inline Iterator& operator--();

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

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

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

            inline Iterator( Node* node, const OrderedHashSet* container );
 
            Node* m_node = nullptr;
            const OrderedHashSet* m_container = nullptr;
        };
 
        //----------------------------------------------
        // OrderedHashSet::ConstIterator class
        //----------------------------------------------

        class ConstIterator
        {
            friend class OrderedHashSet;
 
        public:
            using iterator_category = std::bidirectional_iterator_tag;

            using value_type = const TKey;

            using difference_type = std::ptrdiff_t;

            using pointer = const TKey*;

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

            ConstIterator() = default;

            inline explicit ConstIterator( const Node* node );

            inline ConstIterator( const Iterator& it );
 
            //---------------------------
            // Operations
            //---------------------------

            inline reference operator*() const;

            inline pointer operator->() const;

            inline ConstIterator& operator++();

            inline ConstIterator operator++( int );

            inline ConstIterator& operator--();

            inline ConstIterator operator--( int );
 
            //---------------------------
            // Comparison
            //---------------------------

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

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

            inline ConstIterator( const Node* node, const OrderedHashSet* container );
 
            const Node* m_node = nullptr;
            const OrderedHashSet* m_container = nullptr;
        };
    };
} // namespace nfx::containers
 
#include "nfx/detail/containers/OrderedHashSet.inl"