使用自定义弱指针清除一对多关系中的nullptr

Question

我有一对多的地图类 - MyMap1N<WeakPtr_Parent,WeakPtr_Children>。根据设计，它应该存储与游戏相关的实例的弱指针。

粗略地说，它被称为： -

MyMap1N<WeakPtr<Room>,WeakPtr<RigidBody>> map;
WeakPtr<Room> room=create<Room>();
WeakPtr<RigidBody> body=create<RigidBody>();
map.add(room,body);
MyArray<WeakPtr<RigidBody>> bodys=map.getAllChildren(room);

通过剖析，我发现std::unordered_map太慢了。因此，我必须找到另一种方法来实现它。

我决定在unordered_map中创建一个数组（而不是Room）。为了提高查询速度，我还在indexInArray的每个实例附近注入RigidBody（见下图）。

有了这个indexInArray，有可能使add(room,body)和remove(room,body)操作得到O(1)，并保证Room::bodys的每个槽都被占用。

Question

当一些儿童（RigidBody）被删除时会出现问题。 MyMap1N甚至不知道它。

如果删除某些MyMap1N实例，如何清理RigidBody？

注意:(可用工具/限制）

在我的情况下，幸运的是，检查“WeakPtr<>是否是nullptr”的成本非常便宜。
每个实例都有自己独特的int ID。 ID为每种类型分开运行，ID的值很低（因为我回收它）。
我使用多线程。
（编辑：澄清）有很多MyMap1N<Something,Something>散布在许多System-like类。因此，像这样硬编码是非常难以维护的： - rigidBody->destroy() ===> { SystemA::mapRoomBody::removeParent(rigidBody) ; SystemA::mapCatBody::removeParent(rigidBody) ; SystemB::mapBodyDog::removeAllChildren(rigidBody) ; } //: Cat and Dog denotes some arbitrary GameObject-type class

My poor solution

解决方案1

我将MyMap1N的每个实例自动注册到一个中心位置。

如果删除RigidBody，中央系统将回调每个相关的MyMap1N。

（为了确定MyMap1N是否相关，我使用了像MyMap1N::Type_Parent和MyMap1N::Type_Children这样的模板魔法。）

rigidBody->destroy()   
    ===> central->kill(RigidBody*) 
        ===> MyMap1N<WeakPtr<Room>,WeakPtr<RigidBody>>::removeParent(RigidBody*) 
              ... and many other related instances of MyMap1N

它有效，但速度很慢。我相信缓存未命中是原因（不确定）。

解决方案2（我的旧版本）

每当用户想要删除RigidBody时，只需标记它。在时间步结束时，与解决方法1相同。它更快。或许，这是因为电脑爱打包。（例如较低的成本）但是，它仍然使用CPU约占整个游戏的10-20％。

解决方案3（目前使用）

如果删除RigidBody，请不要做任何事情。但是，当我查询add(room,body)/remove(room,body)/getAllChildren(room)/getParent(body)时，我必须检查是否WeakPtr<>==nullptr。

它很快。删除成本为零，每个查询也很快。

缺点是阵列Room::bodys永远增长因为Room::Bodys逐渐充满了X（Occupied but the object was deleted）。我的程序在第200个时间步骤抛出一个assert-memory-fail。

解决方案4

我正在考虑使用解决方案3，但也创建一个新的功能MyMap1N::periodicCleanUp删除所有X即重新包装它。

应该定期调用该函数，可能每10个步骤调用一次。（就像一个大清洁日）

我觉得这是一个黑客，高度基于自定义调整（即主观调整）。

Answer 1

从问题和评论中收集到的内容，似乎有一些可行的解决方案。

Solution 1

其他人在评论中指出的第一个可能的解决方案是在附加到数组之前使用自由索引槽。这将涉及每个Room或持有数组RigidBody的对象有一个自由索引列表，std::forward_list或std::vector将有利于此。然后，您可以通过首先检查列表中是否有可用插槽来添加RigidBody。如果有，则从列表中弹出该索引，否则追加到数组。删除RigidBody只需将释放的索引推送到可用插槽列表。现在，这个解决方案需要每个RigidBody包含父对和索引对的列表。这样，当RigidBody被销毁时，您只需通知每个父项释放该对象正在使用的索引。

Advantages

实施可能有点奇怪。
添加和删除是O(1)。
迭代速度一般都很好。

Disadvantages

使用相当数量的内存。
阵列将会增长。
每个父母必须使用一个唯一的密钥。

Solution 2

还有另一种类似的解决方案在评论中讨论过。但是，不是每个父节点都有多个索引的RigidBody，它有一个唯一的ID作为索引。此唯一ID应具有已知的最小值和最大值范围。然后，每个父母将分配足够的空间来容纳最大数量的ID和RigidBodies。破坏和删除RigidBody很简单，因为您只需将ID / index传递给每个注册的父级。此外，您可以使用列表来跟踪免费ID。

Advantages

数组在运行时不会增长。
添加和删除是O(1)。
更少的键和索引。
所有父母的密钥/索引相同。
很好，如果阵列将大部分填充。

Disadvantages

使用大量内存。
如果数组大部分为空，迭代将是低效的。

Solution 3

您建议的定期清理想法可以工作。但是，一次性清理所有阵列可能会耗费大量时间。因此，可能的调整是在每个时间步结束时部分清除阵列。这种调整需要你必须存储你最后离开的地方的索引。您可以使用该索引继续清除数组的各个部分。数组完全清除后，您可以将该索引重置为0并重新开始。只有当您移除物体的速率通常大于添加物体的速率时，此解决方案和调整才有效。

Advantages

易于实施。
易于调整和调整。

Disadvantages

可能会失败，具体取决于添加和删除项目的比率。
可以使用超过必要的内存。

Solution 4

另一种解决方案将涉及使用刚体的地址或ID来“散列”或将其转换为向量数组。这个向量数组可以通过使用素数作为数组的大小来完成。然后，我们可以使用RigidBodies ID或地址，并使用数组的大小来模拟它，将其放入向量中。这使得擦除比正常矢量更快。此外，它使用的内存少于大量静态插槽。迭代该结构将涉及迭代每个桶/向量。或者您可以创建一个自定义迭代器来为您执行此操作。

Basic Implementation of Structure

namespace {
    template<typename Int>
    constexpr bool isPrime(Int num, Int test = 2) {
        return (test * test > num ? true : (num % test == 0 ? false : isPrime(num, test + 1)));
    }
    //Buckets must be a size
    template<typename data_t, std::size_t PRIME_SIZE, typename = typename std::enable_if<isPrime(PRIME_SIZE)>::type>
    class BucketVector
    {
    public:
        constexpr static auto SIZE = PRIME_SIZE;
        template<bool is_const>
        using BucketIteratorBase = typename  std::iterator<std::bidirectional_iterator_tag, typename std::conditional<is_const, const data_t, data_t>::type>;
        using uint_t = std::uintptr_t;
        using BucketType = std::vector<data_t>;
        template<bool is_const>
        class BucketIterator : public BucketIteratorBase<is_const> {
        public:
            using Base = BucketIteratorBase<is_const>;
            using BucketOwner = BucketVector<data_t, PRIME_SIZE>;
            using typename Base::pointer;
            using typename Base::reference;
            using typename Base::value_type;
            friend class BucketIterator<!is_const>;
            std::size_t m_bucket;
            pointer m_value;
            BucketOwner* m_owner;
        public:
            BucketIterator(std::size_t bucket, pointer value, BucketOwner* owner)
                : m_bucket(bucket),
                m_value(value),
                m_owner(owner) {
                //validateIterator();
            }
            ~BucketIterator() {
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator(const BucketIterator<value>& iterator)
                : m_bucket(iterator.m_bucket),
                m_value(iterator.m_value),
                m_owner(iterator.m_owner) {
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator(BucketIterator<value>&& iterator)
                : m_bucket(std::move(iterator.m_bucket)),
                m_value(std::move(iterator.m_value)),
                m_owner(std::move(iterator.m_owner)) {
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator& operator=(BucketIterator<value>&& iterator) {
                m_bucket = std::move(iterator.m_bucket);
                m_value = std::move(iterator.m_value);
                m_owner = std::move(iterator.m_owner);
                return *this;
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator& operator=(const BucketIterator<value>& iterator) {
                m_bucket = iterator.m_bucket;
                m_value = iterator.m_value;
                m_owner = iterator.m_owner;
                return *this;
            }
            BucketIterator& operator++() {
                ++m_value;
                forwardValidate();
                return *this;
            }
            BucketIterator operator++(int) {
                BucketIterator copy(*this);
                ++(*this);
                return copy;
            }
            BucketIterator& operator--() {
                backwardValidate();
                --m_value;
                return *this;
            }
            BucketIterator operator--(int) {
                BucketIterator copy(*this);
                --(*this);
                return copy;
            }
            reference operator*() const {
                return *m_value;
            }
            pointer operator->() const {
                return m_value;
            }
            template<bool value>
            bool operator==(const BucketIterator<value>& iterator) const {
                return m_bucket == iterator.m_bucket && m_owner == iterator.m_owner && m_value == iterator.m_value;
            }
            template<bool value>
            bool operator!=(const BucketIterator<value>& iterator) const {
                return !(this->operator==(iterator));
            }
            BucketOwner* getSystem() const {
                return m_owner;
            }
            inline void backwardValidate() {
                while (m_value == m_owner->m_buckets[m_bucket].data() && m_bucket != 0) {
                    --m_bucket;
                    m_value = m_owner->m_buckets[m_bucket].data() + m_owner->m_buckets[m_bucket].size();
                }
            }
            inline void forwardValidate() {
                while (m_value == (m_owner->m_buckets[m_bucket].data() + m_owner->m_buckets[m_bucket].size()) && m_bucket != SIZE - 1) {
                    m_value = m_owner->m_buckets[++m_bucket].data();
                }
            }
        };
        using iterator = BucketIterator<false>;
        using const_iterator = BucketIterator<true>;
        friend class BucketIterator<false>;
        friend class BucketIterator<true>;
    private:
        std::array<BucketType, SIZE> m_buckets;
        std::size_t m_size;
    public:
        BucketVector()
            : m_size(0) {
        }
        ~BucketVector() {
        }
        BucketVector(const BucketVector&) = default;
        BucketVector(BucketVector&&) = default;
        BucketVector& operator=(const BucketVector&) = default;
        BucketVector& operator=(BucketVector&&) = default;
        data_t& operator[](std::size_t index) {
            const auto bucketIndex = findBucketIndex(index);
            return m_buckets[bucketIndex.first][bucketIndex.second];
        }
        const data_t& operator[](std::size_t index) const {
            return static_cast<BucketVector*>(this)->operator[](index);
        }
        data_t& at(std::size_t index) {
            if (index >= m_size) {
                throw std::out_of_range("BucketVector::at index out of range");
            }
            return this->operator[](index);
        }
        const data_t& at(std::size_t index) const {
            return static_cast<BucketVector*>(this)->at(index);
        }
        void erase(const_iterator iter) {
            auto& bucket = m_buckets[iter.m_bucket];
            std::size_t index = iter.m_value - bucket.data();
            bucket[index] = bucket.back();
            bucket.pop_back();
            --m_size;
        }
        void push_back(uint_t id, const data_t& data) {
            const auto slot = get_slot(id);
            m_buckets[slot].push_back(data);
            ++m_size;
        }
        void push_back(uint_t id, data_t&& data) {
            const auto slot = get_slot(id);
            m_buckets[slot].push_back(std::move(data));
            ++m_size;
        }
        template<typename... args>
        void emplace_back(uint_t id, args&&... parameters) {
            const auto slot = get_slot(id);
            m_buckets[slot].emplace_back(std::forward<args>(parameters)...);
            ++m_size;
        }

        void pop_back(uint_t index) {
            const auto slot = get_slot(index);
            m_buckets[slot].pop_back();
            --m_size;
        }
        void pop_front(uint_t index) {
            const auto slot = get_slot(index);
            m_buckets[slot].pop_front();
            --m_size;
        }
        void reserve(std::size_t size) {
            const std::size_t slotSize = size / SIZE + 1;
            for (auto& bucket : m_buckets) {
                bucket.reserve(slotSize);
            }
        }
        void clear() {
            for (auto& bucket : m_buckets) {
                bucket.clear();
            }
        }
        bool empty() const {
            return m_size != 0;
        }
        std::size_t size() const {
            return m_size;
        }
        iterator find(uint_t index, const data_t& value) {
            const std::size_t slot = get_slot(index);
            auto& bucket = m_buckets[slot];
            for (auto it = bucket.begin(), end = bucket.end(); it != end; ++it) {
                if (*it == value) {
                    return { slot, &(*it), this };
                }
            }
            return end();
        }
        template<typename fn_t>
        iterator find(uint_t index, const fn_t& fn) {
            const std::size_t slot = get_slot(index);
            auto& bucket = m_buckets[slot];
            for (auto it = bucket.begin(), end = bucket.end(); it != end; ++it) {
                if (fn(*it)) {
                    return { slot, &(*it), this };
                }
            }
            return end();
        }
        const_iterator find(uint_t index, const data_t& value) const {
            return cfind(index, value);
        }
        const_iterator cfind(uint_t index, const data_t& value) const {
            return static_cast<BucketVector*>(this)->find(index, value);
        }
        iterator begin(uint_t index = 0) {
            auto bucketIndex = findBucketIndex(index);
            iterator it{ bucketIndex.first, m_buckets[bucketIndex.first].data() + bucketIndex.second, this };
            it.forwardValidate();
            return it;
        }
        iterator end(uint_t index = 0) {
            iterator it{ SIZE - 1, m_buckets.back().data() + m_buckets.back().size(), this };
            return it;
        }
        const_iterator begin(uint_t index = 0) const {
            auto bucketIndex = findBucketIndex(index);
            const_iterator it{ bucketIndex.first, m_buckets[bucketIndex.first].data() + bucketIndex.second, this };
            it.forwardValidate();
            return it;
        }
        const_iterator end(uint_t index = 0) const {
            const_iterator it{ SIZE - 1, m_buckets.back().data() + m_buckets.back().size(), this };
            return it;
        }
        std::size_t get_slot(uint_t id) {
            return id % SIZE;
        }
    private:
        inline std::pair<std::size_t, std::size_t> findBucketIndex(std::size_t index) {
            std::size_t bucket = 0;
            std::size_t count = 0;
            while (index >= m_buckets[bucket].size() + count) {
                count += m_buckets[bucket].size();
                ++bucket;
            }
            return { bucket, index - count };
        }
    };
}

Advantages

附加是O(1)。
使用比解决方案1和2更少的内存。
可用于快速查明RigidBody是否属于父母。
对于要使用的矢量大小，擦除速度很快。
如果数组的空值超过50％，则迭代速度比解决方案1和2快。

Disadvantages

擦除速度快但不如解决方案1和2快。
矢量将增长。
如果阵列超过50％，则迭代速度比解决方案1和2慢。

Basic Benchmark Program

您可以使用此程序测试各种输入，例如要删除的值的大小和数量，以查看性能。

#include <chrono>
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <iomanip>
#include <unordered_set>
#include <array>
#include <vector>
#include <iterator>
#include <type_traits>


template<typename mclock_t = typename std::conditional<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>::type>
class Benchmarker {
public:
    using ClockType = mclock_t;
    using TimePoint = std::chrono::time_point<ClockType>;
private:
    TimePoint m_start;
    TimePoint m_end;
    bool m_running;
public:
    Benchmarker(bool run = false) {
        m_running = run;

        if (m_running) {
            start();
        }
    }

    Benchmarker& start() {
        m_start = ClockType::now();
        m_running = true;

        return *this;
    }

    Benchmarker& stop() {
        m_end = ClockType::now();
        m_running = false;

        return *this;
    }

    template<typename T = std::chrono::microseconds>
    Benchmarker& printDuration(std::ostream& out) {
        out << std::chrono::duration_cast<T>(m_end - m_start).count();

        return *this;
    }

    template<typename T = std::chrono::microseconds>
    long long getDurationCount() {
        return std::chrono::duration_cast<T>(m_end - m_start).count();
    }

    friend std::ostream& operator<<(std::ostream& out, Benchmarker& benchmarker) {
        out << std::chrono::duration_cast<std::chrono::microseconds>(benchmarker.m_end - benchmarker.m_start).count();

        return out;
    }

    TimePoint getDuration() {
        return m_end - m_start;
    }

    TimePoint getStartTime() {
        return m_start;
    }

    TimePoint getEndTime() {
        return m_end;
    }

    bool isRunning() {
        return m_running;
    }
};

namespace {
    template<typename Int>
    constexpr bool isPrime(Int num, Int test = 2) {
        return (test * test > num ? true : (num % test == 0 ? false : isPrime(num, test + 1)));
    }
    //Buckets must be a size
    template<typename data_t, std::size_t PRIME_SIZE, typename = typename std::enable_if<isPrime(PRIME_SIZE)>::type>
    class BucketVector
    {
    public:
        constexpr static auto SIZE = PRIME_SIZE;
        template<bool is_const>
        using BucketIteratorBase = typename  std::iterator<std::bidirectional_iterator_tag, typename std::conditional<is_const, const data_t, data_t>::type>;
        using uint_t = std::uintptr_t;
        using BucketType = std::vector<data_t>;
        template<bool is_const>
        class BucketIterator : public BucketIteratorBase<is_const> {
        public:
            using Base = BucketIteratorBase<is_const>;
            using BucketOwner = BucketVector<data_t, PRIME_SIZE>;
            using typename Base::pointer;
            using typename Base::reference;
            using typename Base::value_type;
            friend class BucketIterator<!is_const>;
            std::size_t m_bucket;
            pointer m_value;
            BucketOwner* m_owner;
        public:
            BucketIterator(std::size_t bucket, pointer value, BucketOwner* owner)
                : m_bucket(bucket),
                m_value(value),
                m_owner(owner) {
                //validateIterator();
            }
            ~BucketIterator() {
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator(const BucketIterator<value>& iterator)
                : m_bucket(iterator.m_bucket),
                m_value(iterator.m_value),
                m_owner(iterator.m_owner) {
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator(BucketIterator<value>&& iterator)
                : m_bucket(std::move(iterator.m_bucket)),
                m_value(std::move(iterator.m_value)),
                m_owner(std::move(iterator.m_owner)) {
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator& operator=(BucketIterator<value>&& iterator) {
                m_bucket = std::move(iterator.m_bucket);
                m_value = std::move(iterator.m_value);
                m_owner = std::move(iterator.m_owner);
                return *this;
            }
            template<bool value, typename = typename std::enable_if<!value || (value == is_const)>::type>
            BucketIterator& operator=(const BucketIterator<value>& iterator) {
                m_bucket = iterator.m_bucket;
                m_value = iterator.m_value;
                m_owner = iterator.m_owner;
                return *this;
            }
            BucketIterator& operator++() {
                ++m_value;
                forwardValidate();
                return *this;
            }
            BucketIterator operator++(int) {
                BucketIterator copy(*this);
                ++(*this);
                return copy;
            }
            BucketIterator& operator--() {
                backwardValidate();
                --m_value;
                return *this;
            }
            BucketIterator operator--(int) {
                BucketIterator copy(*this);
                --(*this);
                return copy;
            }
            reference operator*() const {
                return *m_value;
            }
            pointer operator->() const {
                return m_value;
            }
            template<bool value>
            bool operator==(const BucketIterator<value>& iterator) const {
                return m_bucket == iterator.m_bucket && m_owner == iterator.m_owner && m_value == iterator.m_value;
            }
            template<bool value>
            bool operator!=(const BucketIterator<value>& iterator) const {
                return !(this->operator==(iterator));
            }
            BucketOwner* getSystem() const {
                return m_owner;
            }
            inline void backwardValidate() {
                while (m_value == m_owner->m_buckets[m_bucket].data() && m_bucket != 0) {
                    --m_bucket;
                    m_value = m_owner->m_buckets[m_bucket].data() + m_owner->m_buckets[m_bucket].size();
                }
            }
            inline void forwardValidate() {
                while (m_value == (m_owner->m_buckets[m_bucket].data() + m_owner->m_buckets[m_bucket].size()) && m_bucket != SIZE - 1) {
                    m_value = m_owner->m_buckets[++m_bucket].data();
                }
            }
        };
        using iterator = BucketIterator<false>;
        using const_iterator = BucketIterator<true>;
        friend class BucketIterator<false>;
        friend class BucketIterator<true>;
    private:
        std::array<BucketType, SIZE> m_buckets;
        std::size_t m_size;
    public:
        BucketVector()
            : m_size(0) {
        }
        ~BucketVector() {
        }
        BucketVector(const BucketVector&) = default;
        BucketVector(BucketVector&&) = default;
        BucketVector& operator=(const BucketVector&) = default;
        BucketVector& operator=(BucketVector&&) = default;
        data_t& operator[](std::size_t index) {
            const auto bucketIndex = findBucketIndex(index);
            return m_buckets[bucketIndex.first][bucketIndex.second];
        }
        const data_t& operator[](std::size_t index) const {
            return static_cast<BucketVector*>(this)->operator[](index);
        }
        data_t& at(std::size_t index) {
            if (index >= m_size) {
                throw std::out_of_range("BucketVector::at index out of range");
            }
            return this->operator[](index);
        }
        const data_t& at(std::size_t index) const {
            return static_cast<BucketVector*>(this)->at(index);
        }
        void erase(const_iterator iter) {
            auto& bucket = m_buckets[iter.m_bucket];
            std::size_t index = iter.m_value - bucket.data();
            bucket[index] = bucket.back();
            bucket.pop_back();
            --m_size;
        }
        void push_back(uint_t id, const data_t& data) {
            const auto slot = get_slot(id);
            m_buckets[slot].push_back(data);
            ++m_size;
        }
        void push_back(uint_t id, data_t&& data) {
            const auto slot = get_slot(id);
            m_buckets[slot].push_back(std::move(data));
            ++m_size;
        }
        template<typename... args>
        void emplace_back(uint_t id, args&&... parameters) {
            const auto slot = get_slot(id);
            m_buckets[slot].emplace_back(std::forward<args>(parameters)...);
            ++m_size;
        }

        void pop_back(uint_t index) {
            const auto slot = get_slot(index);
            m_buckets[slot].pop_back();
            --m_size;
        }
        void pop_front(uint_t index) {
            const auto slot = get_slot(index);
            m_buckets[slot].pop_front();
            --m_size;
        }
        void reserve(std::size_t size) {
            const std::size_t slotSize = size / SIZE + 1;
            for (auto& bucket : m_buckets) {
                bucket.reserve(slotSize);
            }
        }
        void clear() {
            for (auto& bucket : m_buckets) {
                bucket.clear();
            }
        }
        bool empty() const {
            return m_size != 0;
        }
        std::size_t size() const {
            return m_size;
        }
        iterator find(uint_t index, const data_t& value) {
            const std::size_t slot = get_slot(index);
            auto& bucket = m_buckets[slot];
            for (auto it = bucket.begin(), end = bucket.end(); it != end; ++it) {
                if (*it == value) {
                    return { slot, &(*it), this };
                }
            }
            return end();
        }
        template<typename fn_t>
        iterator find(uint_t index, const fn_t& fn) {
            const std::size_t slot = get_slot(index);
            auto& bucket = m_buckets[slot];
            for (auto it = bucket.begin(), end = bucket.end(); it != end; ++it) {
                if (fn(*it)) {
                    return { slot, &(*it), this };
                }
            }
            return end();
        }
        const_iterator find(uint_t index, const data_t& value) const {
            return cfind(index, value);
        }
        const_iterator cfind(uint_t index, const data_t& value) const {
            return static_cast<BucketVector*>(this)->find(index, value);
        }
        iterator begin(uint_t index = 0) {
            auto bucketIndex = findBucketIndex(index);
            iterator it{ bucketIndex.first, m_buckets[bucketIndex.first].data() + bucketIndex.second, this };
            it.forwardValidate();
            return it;
        }
        iterator end(uint_t index = 0) {
            iterator it{ SIZE - 1, m_buckets.back().data() + m_buckets.back().size(), this };
            return it;
        }
        const_iterator begin(uint_t index = 0) const {
            auto bucketIndex = findBucketIndex(index);
            const_iterator it{ bucketIndex.first, m_buckets[bucketIndex.first].data() + bucketIndex.second, this };
            it.forwardValidate();
            return it;
        }
        const_iterator end(uint_t index = 0) const {
            const_iterator it{ SIZE - 1, m_buckets.back().data() + m_buckets.back().size(), this };
            return it;
        }
        std::size_t get_slot(uint_t id) {
            return id % SIZE;
        }
    private:
        inline std::pair<std::size_t, std::size_t> findBucketIndex(std::size_t index) {
            std::size_t bucket = 0;
            std::size_t count = 0;
            while (index >= m_buckets[bucket].size() + count) {
                count += m_buckets[bucket].size();
                ++bucket;
            }
            return { bucket, index - count };
        }
    };
}

constexpr std::size_t SIZE = 1'000;
constexpr std::size_t INDEXES = 400;
constexpr std::size_t SPACING = 26;

void vectorFindErase(std::vector<int>& values, int value) {
    const auto end = values.end();
    for (auto it = values.begin(); it != end; ++it) {
        if (*it == value) {
            values.erase(it);
            break;
        }
    }
}
void vectorEraseSorted(std::vector<int>& values, int value) {
    auto it = std::lower_bound(values.begin(), values.end(), value);
    if (it != values.end() && !(value < *it)) {
        values.erase(it);
    }
}

void setErase(std::unordered_set<int>& values, int value) {
    values.erase(value);
}
int main() {
    std::mt19937 rng;
    rng.seed(std::random_device()());


    std::vector<int> values(SIZE);
    std::generate_n(values.begin(), SIZE, []() {
        static int index = 0;
        return index++;
    });
    auto sorted = values;
    auto preallocate = values;
    auto vnf = values;

    std::random_shuffle(vnf.begin(), vnf.end(), [&](auto i) {
        return rng() % i;
    });
    std::vector<int> indexes(INDEXES);
    std::generate(indexes.begin(), indexes.end(), [&]() {
        return rng() % SIZE;
    });

    //APPEND VALUES TO BUCKET VECTOR, USE VALUE AS IT'S OWN KEY
    BucketVector<int, 23> bucket;
    for (auto& value : values) {
        bucket.push_back(value, value);
    }



    Benchmarker<> bench(true);

    //NAIVE FIND AND ERASE
    for (auto& index : indexes) {
        vectorFindErase(vnf, index);
    }
    std::cout << std::left;
    std::cout << std::setw(SPACING) << "Naive Find and Erase: " << bench.stop() << '\n';

    //SORTED ERASE
    bench.start();
    for (auto& index : indexes) {
        vectorEraseSorted(sorted, index);
    }
    std::cout << std::setw(SPACING) << "Sorted erase: " << bench.stop() << '\n';

    //PRELLOCATED ERASE
    bench.start();
    for (auto& index : indexes) {
        preallocate[index] = std::numeric_limits<int>::min();
    }
    std::cout << std::setw(SPACING) << "Prellocated erase: " << bench.stop() << '\n';

    //BUCKETVECTOR ERASE
    bench.start();
    for (auto& index : indexes) {
        auto it = bucket.find(index, index);
        if (it == bucket.end()) {
            continue;
        }
        bucket.erase(it);
    }

    std::cout << std::setw(SPACING) << "BucketVector erase: " << bench.stop() << '\n';

    //BUCKET SUM/ITERATE
    bench.start();
    long long bucketSum = 0;
    for (std::size_t index = 0; index != 10'000; ++index) {
        for (auto& val : bucket) {
            bucketSum += val;
        }
    }
    std::cout << std::setw(SPACING) << "Bucket Sum/Iterate: " << bench.stop() << ' ' << bucketSum << '\n';


    //PREALLOCATE SUM/ITERATE
    bench.start();
    long long vfsum = 0;
    for (std::size_t index = 0; index != 10'000; ++index) {
        for (auto& val : preallocate) {
            if (val != std::numeric_limits<int>::min()) {
                vfsum += val;
            }
        }
    }

    std::cout << std::setw(SPACING) << "Preallocate sum/Iterate: " << bench.stop() << ' ' << vfsum << '\n';
    std::cin.get();

    return 0;
}

在我的机器上，我发现当预分配的数组为50％或更多空，大小为1000时，BucketVector的迭代速度比预分配的数组快一些。

使用自定义弱指针清除一对多关系中的nullptr

问题描述投票：7回答：1

Question

My poor solution

解决方案1

解决方案2（我的旧版本）

解决方案3（目前使用）

解决方案4

1个回答

Solution 1

Advantages

Disadvantages

Solution 2

Advantages

Disadvantages

Solution 3

Advantages

Disadvantages

Solution 4

Basic Implementation of Structure

Advantages

Disadvantages

Basic Benchmark Program

最新问题

使用自定义弱指针清除一对多关系中的nullptr

问题描述 投票：7回答：1

Question

My poor solution

解决方案1

解决方案2（我的旧版本）

解决方案3（目前使用）

解决方案4

1个回答

Solution 1

Advantages

Disadvantages

Solution 2

Advantages

Disadvantages

Solution 3

Advantages

Disadvantages

Solution 4

Basic Implementation of Structure

Advantages

Disadvantages

Basic Benchmark Program

最新问题

问题描述投票：7回答：1