hashSet.h

#pragma once
#include<vector>
#include<unordered_map>
#include<algorithm>
 
namespace Aire {
    template<class T>
    class HashSet {
    public:
        struct Iterator {
        public:
            Iterator(HashSet<T>* owner, int i): owner(owner), i(i) {}
 
            Iterator& operator++() {
                ++i;
                return *this;
            }
 
            Iterator operator++(int) {
                ++i;
                return *this;
            }
 
            T& operator*() {
                return owner->elements[i];
            }
 
            T* operator->() {
                return owner->elements.data()+i;
            }
 
            bool operator==(const Iterator& it) const {
                return i==it.i;
            }
 
            bool operator!=(const Iterator& it) const {
                return i!=it.i;
            }
        private:
            HashSet<T>* owner;
            int i;//< index in the array
        };
 
        struct ConstIterator {
        public:
            ConstIterator(const HashSet<T>* owner, int i): owner(owner), i(i) {}
 
            ConstIterator& operator++() {
                ++i;
                return *this;
            }
 
            ConstIterator operator++(int) {
                ++i;
                return *this;
            }
 
            const T& operator*() {
                return owner->elements[i];
            }
 
            const T* operator->() {
                return owner->elements.data()+i;
            }
 
            bool operator==(const ConstIterator& it) const {
                return i==it.i;
            }
 
            bool operator!=(const ConstIterator& it) const {
                return i!=it.i;
            }
        private:
            const HashSet<T>* owner;
            int i;//< index in the array
        };
 
        HashSet(int sizeHint = 10) {
            elements.reserve(sizeHint);
            idxMap.reserve(sizeHint);
        }
 
        bool insert(const T& newElement) {
            // Dynamically grow the array to avoid re-allocation on every insertion.
            // The capacity of the array is doubled.
            if (elements.size()==elements.capacity()) {
                size_t newSize = std::max(elements.size(), size_t(1)) * 2;
                elements.reserve(newSize);
                idxMap.reserve(newSize);
            }
 
            // If the element does not exist already, insert in the hash map and in the array.
            // Map the element to the index it is going to take in the array.
            auto insertSuccess = idxMap.insert({ newElement, int(elements.size()) }).second;
            if (insertSuccess) {
                elements.push_back(newElement);
            }
            return insertSuccess;
        }
 
        void erase(const T& element) {
            auto it = idxMap.find(element);
            if (it != idxMap.end()) {
                // For constant-time deletion, swap with the last element of the array.
                // Make sure to update the indices in the hash map.
 
                // Fetch the hash map entry corresponding to the last element in the array
                auto itLast = idxMap.find(elements.back());
 
                // Swap the element with the last element in the array and then pop
                std::swap(elements[itLast->second], elements[it->second]);
                elements.pop_back();
 
                // Update the hash map entry of the swapped entry to store its new index
                (itLast->second) = (it->second);
 
                // Delete the hash map entry of the deleted element
                idxMap.erase(it);
            }
        }
 
        void clear() {
            idxMap.clear();
            elements.clear();
        }
 
        void freeMem() {
            std::vector<T> elementsEmpty;
            std::unordered_map<T, int> idxMapEmpty;
 
            std::swap(elements, elementsEmpty);
            std::swap(idxMap, idxMapEmpty);
        }
 
        void reserve(size_t count) {
            idxMap.reserve(count);
            elements.reserve(count);
        }
 
        Iterator find(const T& element) {
            auto it = idxMap.find(element);
            if (it != idxMap.end()) {
                return Iterator(this, it->second);
            } else {
                return end();
            }
        }
 
        ConstIterator find(const T& newElement) const {
            auto it = idxMap.find(newElement);
            if (it != idxMap.end()) {
                return ConstIterator(this, it->second);
            } else {
                return end();
            }
        }
 
        bool empty() const {
            return elements.empty();
        }
 
        size_t size() const {
            return elements.size();
        }
 
        size_t capacity() const {
            return elements.capacity();
        }
 
        Iterator begin() {
            return Iterator(this, 0);
        }
 
        ConstIterator begin() const {
            return ConstIterator(this, 0);
        }
 
        Iterator end() {
            return Iterator(this, int(elements.size()));
        }
 
        ConstIterator end() const {
            return ConstIterator(this, int(elements.size()));
        }
 
    private:
        // Use a vector to ensure fast traversal of elements
        std::vector<T> elements;
 
        // Use a hash map to ensure uniqueness and to speed up search for an element
        std::unordered_map<T, int> idxMap;
    };
}