Class semiorderedset

src/semiorderedset.h:33–396

template<typename T, typename T_KEY = T, bool MEMMOVE_SAFE = false>
class semiorderedset
{
    typedef compactvector<T, MEMMOVE_SAFE> vector_type;
    
    friend struct setiter;
    std::vector<CowPtr<vector_type>> m_data;
    size_t celem = 0;
    static const size_t bits_min = 8;
    size_t bits = bits_min;
    size_t idxRehash = (1ULL << bits_min); 
    int cfPauseRehash = 0;

    inline size_t targetElementsPerBucket()
    {
        // Aim for roughly 4 cache lines per bucket (determined by imperical testing)
        //  lower values are faster but use more memory
        if (g_semiOrderedSetTargetBucketSize == 0)
            return std::max((64/sizeof(T))*8, (size_t)2);
        else
            return g_semiOrderedSetTargetBucketSize;
    }

public:
    semiorderedset(size_t bitsStart = 0)
    {
        if (bitsStart < bits_min)
            bitsStart = bits_min;
        bits = bitsStart;
        m_data.resize((1ULL << bits));
    }

    struct setiter
    {
        semiorderedset *set;
        size_t idxPrimary = 0;
        size_t idxSecondary = 0;

        setiter(const semiorderedset *set)
        {
            this->set = (semiorderedset*)set;
        }

        bool operator==(const setiter &other) const
        {
            return (idxPrimary == other.idxPrimary) && (idxSecondary == other.idxSecondary);
        }

        bool operator!=(const setiter &other) const { return !operator==(other); }

        inline T &operator*() { return set->m_data[idxPrimary]->operator[](idxSecondary); }
        inline const T &operator*() const { return set->m_data[idxPrimary]->operator[](idxSecondary); }

        inline T *operator->() { return &set->m_data[idxPrimary]->operator[](idxSecondary); }
        inline const T *operator->() const { return &set->m_data[idxPrimary]->operator[](idxSecondary); }
    };

    setiter find(const T_KEY &key)
    {