c++ - 如何确保给定类型的每 100 个对象都分配在连续内存中？

Question

我有一个类型。我在我的应用程序的不同部分实例化它，但我在某个地方顺序地迭代所有它们。不知道最后会有多少。我如何创建一个分配器来存储 100 个对象的 block 并按需提供指针？

我已经在一个简单的类固醇工厂中尝试过这种方法，但它 goes over 5 seconds :

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <thread>
#include <mutex>

using namespace std;

template<class T>
struct Item {
    T data;
    bool alive = true;
    int id = 0;
};

template<class T>
class ItemFactory {
    vector<Item<T>> items;
    unordered_map<int, int> item_ids;
    unsigned int lastCounter=0;
    int removedCounter=0;
    mutex m;

    public:
    int CreateItem() {
        lock_guard<mutex> l(m);
        auto result = lastCounter++;
        Item<T> item;
        item.id = result;
        items.push_back(item);
        item_ids[result] = items.size()-1;
        return result;
    }

    T& GetItem(int id) {
        lock_guard<mutex> l(m);
        return items[item_ids[id]].data;
    }

    void RemoveItem(int id) {
        lock_guard<mutex> l(m);
        items[item_ids[id]].alive = false;
        removedCounter++;

        if(removedCounter>=1000) {
            removedCounter = 0;
            auto end = remove_if(items.begin(), items.end(), [](const Item<T>& item){
                return !item.alive;
            });
            items.erase(end, items.end());
            auto size = items.size();
            item_ids.clear();
            for(auto i = 0; i < size; i++) {
                item_ids[items[i].id]=i;
            }
        }
    }

};

struct demo {
    string bla;
    float arr[256];
};

int main() {
    ItemFactory<demo> f;
    for(int i = 0; i < 50000; i++) {
        auto id = f.CreateItem();
        auto id2 = f.CreateItem();
        auto & i1 = f.GetItem(id);
        auto & i2 = f.GetItem(id2);
        i1.bla = "abra kadabra bum";
        i2.bla = "bla bla bla";
        f.RemoveItem(id);
    }
    cout << "!!!" << endl;
    for(int i = 0; i < 25000; i++) {
        auto id = i + i*2;
        auto & i1 = f.GetItem(id);
        i1.bla = "abra kadabra bum";
        f.RemoveItem(id);
    }
    return 0;
}

有没有办法获得连续的内存块，同时在插入/移除时更有效？

Answer 1

我会查找如何编写内存池分配器，或使用许多可用的分配器之一，例如 Boost Pool:http://www.boost.org/doc/libs/1_59_0/libs/pool/doc/html/index.html

C++11 memory pool design pattern?

通常，您会分配大块内存并在需要时分发指针；如果您知道永远不会释放内存，则可以对其进行优化。如果您真的一直需要连续的内存，即使您偶尔释放内存，您唯一能做的就是重新分配内存和重新排列对象，如果经常这样做，代价会非常高。