qminimalflatset_p.h

Go to the documentation of this file.

// Copyright (C) 2022 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#ifndef QTCORE_QMINIMALFLATSET_P_H
#define QTCORE_QMINIMALFLATSET_P_H
 
//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
 
#include <QtCore/qcontainerfwd.h>
#include <QtCore/qfunctionaltools_impl.h> // CompactStorage
#include <QtCore/private/qglobal_p.h>
 
//#define QMINIMAL_FLAT_SET_DEBUG
#ifdef QMINIMAL_FLAT_SET_DEBUG
# include <QtCore/qscopeguard.h>
# include <QtCore/qdebug.h>
# define QMINIMAL_FLAT_SET_PRINT_AT_END \
    const auto sg = qScopeGuard([&] { qDebug() << this << *this; });
#else
# define QMINIMAL_FLAT_SET_PRINT_AT_END
#endif
 
#include <algorithm> // for std::lower_bound
#include <functional> // for std::less, std::ref
 
QT_BEGIN_NAMESPACE
 
/*
    This is a minimal version of a QFlatSet, the std::set version of QFlatMap.
    Like QFlatMap, it has linear insertion and removal, not logarithmic, like
    real QMap and std::set, so it's only a good container if you either have
    very few entries or lots, but with separate setup and lookup stages.
    Because a full QFlatSet would be 10x the work on writing this minimal one,
    we keep it here for now. When more users pop up and the class has matured a
    bit, we can consider moving it as QFlatSet alongside QFlatMap.
*/
 
template <typename T, typename Container = QList<T>, typename Compare = std::less<T>>
class QMinimalFlatSet : QtPrivate::CompactStorage<Compare>
{
    Container c;
    using CompareStorage = QtPrivate::CompactStorage<Compare>;
public:
    QMinimalFlatSet() = default;
    explicit QMinimalFlatSet(const Compare &cmp) : CompareStorage{cmp} {}
    // Rule Of Zero applies
 
    using const_iterator = typename Container::const_iterator;
    using iterator = const_iterator;
    using const_reverse_iterator = typename Container::const_reverse_iterator;
    using reverse_iterator = const_reverse_iterator;
    using value_type = T;
    using key_compare = Compare;
    using value_compare = Compare;
 
    key_compare key_comp() const { return this->object(); }
    value_compare value_comp() const { return key_comp(); }
 
    iterator begin() const { return c.cbegin(); }
    iterator end() const { return c.cend(); }
    iterator cbegin() const { return begin(); }
    iterator cend() const { return cend(); }
 
    reverse_iterator rbegin() const { return c.crbegin(); }
    reverse_iterator rend() const { return c.crend(); }
    reverse_iterator crbegin() const { return rbegin(); }
    reverse_iterator crend() const { return rend(); }
 
    void clear() {
        QMINIMAL_FLAT_SET_PRINT_AT_END
        c.clear();
    }
    auto size() const { return c.size(); }
    auto count() const { return size(); }
    bool isEmpty() const { return size() == 0; }
 
    std::pair<iterator, bool> insert(value_type &&v)
    {
        QMINIMAL_FLAT_SET_PRINT_AT_END
        const auto r = lookup(v);
        if (r.exists)
            return {r.it, false};
        else
            return {c.insert(r.it, std::move(v)), true};
    }
 
    std::pair<iterator, bool> insert(const value_type &v)
    {
        QMINIMAL_FLAT_SET_PRINT_AT_END
        const auto r = lookup(v);
        if (r.exists)
            return {r.it, false};
        else
            return {c.insert(r.it, v), true};
    }
 
    void erase(const value_type &v)
    {
        QMINIMAL_FLAT_SET_PRINT_AT_END
        const auto r = lookup(v);
        if (r.exists)
            c.erase(r.it);
    }
    void remove(const value_type &v) { erase(v); }
 
    bool contains(const value_type &v) const
    {
        return lookup(v).exists;
    }
 
    const Container &values() const & { return c; }
    Container values() && { return std::move(c); }
 
private:
    auto lookup(const value_type &v) const
    {
        struct R {
            iterator it;
            bool exists;
        };
 
        auto cmp = std::ref(this->object()); // don't let std::lower_bound copy it
 
        const auto it = std::lower_bound(c.cbegin(), c.cend(), v, cmp);
        return R{it, it != c.cend() && !cmp(v, *it)};
    }
 
#ifdef QMINIMAL_FLAT_SET_DEBUG
    friend QDebug operator<<(QDebug dbg, const QMinimalFlatSet &set)
    {
        const QDebugStateSaver saver(dbg);
        dbg.nospace() << "QMinimalFlatSet{";
        for (auto &e : set)
            dbg << e << ", ";
        return dbg << "}";
    }
#endif
};
 
#undef QMINIMAL_FLAT_SET_PRINT_AT_END
 
template <typename T, qsizetype N = QVarLengthArrayDefaultPrealloc>
using QMinimalVarLengthFlatSet = QMinimalFlatSet<T, QVarLengthArray<T, N>>;
 
QT_END_NAMESPACE
 
#endif // QTCORE_QMINIMALFLATSET_P_H