在使用自定义弱指针的一对多关系中清理nullptr [英] cleaning nullptr in one-to-many relation that use custom weak pointer

问题描述

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

I have a one-to-many map class - MyMap1N<WeakPtr_Parent,WeakPtr_Children>.
By design, it is supposed to store weak pointers of game-related instance.

粗略地讲，它就像:-

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太慢.
因此，我不得不寻找另一种方法来实现它.

By profiling, I found that std::unordered_map is too slow.
Thus, I had to find another way to implement it.

我决定在Room中创建一个数组(而不是unordered_map).
为了提高查询速度，我还注入了indexInArray来存储RigidBody的每个实例附近(请参见下图).

I decided to create an array (instead of unordered_map) in Room.
To increase speed of query, I also inject the indexInArray to store near every instance of RigidBody (see the below image).

使用此indexInArray，可以使操作add(room,body)和remove(room,body)获得O(1)，并保证Room::bodys的每个插槽都被占用.

With this indexInArray, it is possible to make operation add(room,body) and remove(room,body) get O(1), and guarantee that every slot of Room::bodys is occupied.

删除子级(RigidBody)的某些实例时会出现问题.
MyMap1N甚至都不知道.

A problem arises when some instances of child (RigidBody) are deleted.
MyMap1N cannot even know it.

在删除某些RigidBody实例时如何清洁MyMap1N?

How to clean the MyMap1N when some instances of RigidBody is deleted?

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

• 幸运的是，对于我来说，检查"WeakPtr<>是否为nullptr"的成本非常便宜.
• 每个实例都有自己的唯一int ID.
  ID针对每种类型运行，并且ID的值较低(因为我对其进行了回收).
• 我使用多线程.

• (澄清)在许多System-like类中都有很多MyMap1N<Something,Something>分散.
  因此，像这样硬编码是非常难以维持的:-

• In my case, fortunately, cost of checking "whether WeakPtr<> is nullptr" is very cheap.
• Every instance has its own unique int ID.
  The ID runs separating for each type and the ID's value is low (because I recycle it).
• I use multi-threading.

• (clarify) There are a lot of MyMap1N<Something,Something> that scatters around in many System-like class.
  Thus, it is very unmaintainable to hardcode like this :-

rigidBody->destroy() ===> {     
        SystemA::mapRoomBody::removeParent(rigidBody) ;
        SystemA::mapCatBody::removeParent(rigidBody) ;
        SystemB::mapBodyDog::removeAllChildren(rigidBody) ;
}  //: Cat and Dog denotes some arbitrary GameObject-type class

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

I register every instances of MyMap1N to a central location automatically.

如果删除了RigidBody，则中央系统将回调到每个相关的MyMap1N.

If a RigidBody is deleted, the central system will callback to every related MyMap1N.

(要确定MyMap1N是否相关，
我使用了MyMap1N::Type_Parent和MyMap1N::Type_Children之类的模板魔术.)

(To determine whether a MyMap1N is related,
I used some template magic like MyMap1N::Type_Parent and MyMap1N::Type_Children.)

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

它可以工作，但是非常慢.
我相信原因是缓存未命中(不确定).

It works, but very slow.
I believe cache miss is the cause (not sure).

每当用户要删除RigidBody时，只需对其进行标记.
在时间步结束时，请与解决方法1相同.
它更快.也许是因为计算机喜欢批处理. (例如，减少虚拟表格费用)
但是，它仍然使用大约整个游戏10-20％的CPU.

Whenever a user wants to delete a RigidBody, just marks it.
At the end of timestep, do same as workaround 1.
It is faster. Perhaps, it is because computer love batching. (e.g. less vtable cost)
However, it still uses CPU about 10-20% of the whole game.

如果删除了RigidBody，请勿执行任何操作.
但是，当我查询add(room,body)/remove(room,body)/getAllChildren(room)/getParent(body)时，我必须检查是否为WeakPtr<>==nullptr.

If a RigidBody is deleted, don't do anything.
However, when I query add(room,body)/remove(room,body)/getAllChildren(room)/getParent(body), I have to check whether WeakPtr<>==nullptr.

速度很快.删除时的成本为零，而且每个查询的速度也很快.

It is fast. There is zero cost at the deleting and every query is also fast.

缺点是数组Room::bodys永远增长
因为Room::Bodys逐渐用X(Occupied but the object was deleted)填充.
我的程序在第200个时间步抛出断言内存失败.

The disadvantage is that the array Room::bodys grows forever
because Room::Bodys gradually filled with X (Occupied but the object was deleted).
My program throws an assert-memory-fail at the 200th time-step.

我正在考虑使用解决方案3，
而且还创建了一个新功能MyMap1N::periodicCleanUp来删除所有X，即重新包装它.

I am considering using Solution 3,
but also creating a new function MyMap1N::periodicCleanUp to remove all the X i.e. repack it.

应该定期调用该函数，也许每10个时间步调用一次.
(就像一个大清洁日)

The function should be called periodically, perhaps once every 10 timesteps.
(like a big cleaning day)

我认为这是一个hack，它高度基于自定义调整(即主观调整).

I feel it is a hack and highly based on custom tuning (i.e. subjective adjustment).

推荐答案

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

From what has been gathered from the question and the comments, there appears to be a few viable solutions.

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

The first possible solution that others have been pointing out in the comments would be using a free index slot before appending to the array. This would involve each Room or object holding an array RigidBody to have a list of free indexes, std::forward_list or std::vector would be good for this. Then, you can add a RigidBody by first checking if there an available slot from the list. If there is, you pop off that index from the list, otherwise you append to the array. Removing a RigidBody simply involves pushing that freed up index to the list of available slots. Now, this solution would require that each RigidBody contains a list of parent and index pairs. That way, when the RigidBody is destroyed you simply notify each parent to free up the index the object was using.

• 实现起来可能有点奇怪.
• 添加和删除是O(1).
• 迭代速度通常很好.

• Could be a bit odd to implement.
• Adding and removing is O(1).
• Iteration speed is generally good.

• 使用大量内存.
• 阵列将不断增长.
• 必须为每个父母使用唯一的密钥.

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

There is also another similar type of solution that was discussed in the comments. However, instead of a RigidBody having multiple indexes for each parents, it has one unique ID that acts as an index. This unique ID should have a known range of minimum and maximum values. Then, each parent would allocate enough space to house the maximum amount of IDs and RigidBodies. The destruction and removal of a RigidBody is simple since you have to simply pass at ID/index to each registered parent. In addition, you could use a list to keep track of free ID's.

• 数组在运行时不会增长.
• 添加和删除是O(1).
• 缺少键和索引.
• 所有父母的键/索引都相同.
• 如果数组将要大部分被填充，那就太好了.

• Array will not be growing during runtime.
• Adding and removing is O(1).
• Less keys and indexes.
• Same key/index for all parents.
• Great if the array is going to be mostly filled.

• 占用大量内存.
• 如果数组大部分为空，则迭代效率很低.

您建议的定期清理想法可能会起作用.但是，一次清理所有阵列可能会花费大量时间.因此，可能的调整是在每个时间步结束时部分清除阵列.这种调整将需要您存储上次停止的位置的索引.为此，您将使用该索引继续清除数组的各个部分.完全清除阵列后，您可以将该索引重置为0并重新开始.仅当您要去除实体的速率通常大于添加实体的速率时，此解决方案和调整才有效.

The periodic cleanup idea you suggested could work. However, it is likely that cleaning up all of the arrays in one-go could cost a lot of time. Hence, a possible adjustment would be to partially clear the array at the end of every timestep. That adjustment would require you having to store an index of where you last left off. To which, you would use that index to continue clearing sections of the array. Once the array has been fully cleared you can reset that index to 0 and start over. This solution and adjustment would only work if the rate you are removing bodies is usually greater than the rate of adding bodies.

• 易于实施.
• 易于调整和调整.

• 可能会失败，具体取决于添加和删除项目的比率.
• 可能使用了不必要的内存.

另一种解决方案将涉及使用刚体的地址或ID来散列"或将其放入向量数组中.向量数组可以通过使用质数作为数组的大小来实现.然后，我们可以使用RigidBodies ID或地址，并使用数组的大小对其取模，以将其放入向量中.这使得擦除速度比普通矢量要快.此外，它比大量静态插槽阵列使用更少的内存.遍历此结构将涉及遍历每个存储桶/向量.或者，您可以创建一个自定义迭代器来为您执行此操作.

Another solution would involve using the address or ID of the rigid body to 'hash' or it into an array of vectors. This array of vectors could be accomplished by using a prime number to act as the size of the array. Then, we can use the RigidBodies ID or address and modulo that with the size of the array to place it into a vector. This makes erasing faster than a normal vector. In addition, it uses less memory than a massive static array of slots. Iterating over this structure would involve iterating over each bucket/vector. Or you can create a custom iterator that does this for you.

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 };
        }
    };
}

优势

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

Advantages

• Appending is O(1).
• Use's less memory than Solution 1 and 2.
• Can be used to quickly find out if a RigidBody belongs to a parent.
• Erasing is fast for the size of vector you are going to use.
• Iteration is faster than Solution's 1 and 2 if the array is more than 50% empty.
• 擦除速度很快，但不如解决方案的1和2快.
• 媒介将会增长.
• 如果阵列已满50％，迭代速度将比Solution的1和2慢.

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

You can use this program to test various inputs such as size and amount of values to remove to see the performance.

#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的迭代速度比预分配的数组略快.

On my machine, I found that the BucketVector was slightly faster to iterate over than a preallocated array when the preallocated array was 50% or more empty with a size of 1000.

这篇关于在使用自定义弱指针的一对多关系中清理nullptr的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！