C++ 区域分配

2025 年 5 月 10 日 | 阅读 10 分钟

引言

Arena 分配，也称为区域内存管理，是一种内存管理技术，它从预先分配的“arena”或“池”中批量分配内存，然后进行细分以满足较小的分配请求。关键思想是预先分配一大块连续内存，并在该块内有效地管理较小的分配。它在内存分配和释放频繁且性能至关重要的场景中特别有用。

程序

 
#include <iostream>
#include <stdexcept>
#include <cstddef>
#include <new>
class ArenaAllocator {
private:
    char* arena;         // Pointer to the start of the memory pool
    char* current;       // Pointer to the next available memory location
    size_t totalSize;    // Total size of the arena
    size_t usedSize;     // Amount of memory currently used
    // Helper function for alignment
    void* alignPointer(size_t alignment) {
        uintptr_t ptr = reinterpret_cast<uintptr_t>(current);
        size_t offset = (alignment - (ptr % alignment)) % alignment;
        if (usedSize + offset > totalSize) {
            throw std::bad_alloc(); // Not enough memory for alignment
        }
        current += offset;
        usedSize += offset;
        return current;
    }
public:
    // Constructor to initialize the arena
    explicit ArenaAllocator(size_t size) : totalSize(size), usedSize(0) {
        arena = new char[size];
        current = arena;
    }
    // Allocate memory from the arena
    void* allocate(size_t size, size_t alignment = alignof(std::max_align_t)) {
        if (size == 0) {
            throw std::invalid_argument("Allocation size must be greater than 0");
        }
        // Ensure proper alignment
        alignPointer(alignment);
        if (usedSize + size > totalSize) {
            throw std::bad_alloc(); // Not enough memory
        }
        void* allocated = current;
        current += size;
        usedSize += size;
        return allocated;
    }
    // Reset the arena (free all memory at once)
    void reset() {
        current = arena;
        usedSize = 0;
    }
    // Destructor to free the memory pool
    ~ArenaAllocator() {
        delete[] arena;
    }
    // Getters for diagnostic purposes
    size_t getUsedSize() const { return usedSize; }
    size_t getRemainingSize() const { return totalSize - usedSize; }
};
int main() {
    try {
        constexpr size_t ARENA_SIZE = 1024; // 1 KB memory pool
        ArenaAllocator arena(ARENA_SIZE);
        // Allocate an integer
        int* intPtr = static_cast<int*>(arena.allocate(sizeof(int)));
        *intPtr = 42;
        std::cout << "Integer allocated: " << *intPtr << "\n";
        // Allocate a double with alignment
        double* doublePtr = static_cast<double*>(arena.allocate(sizeof(double), alignof(double)));
        *doublePtr = 3.14159;
        std::cout << "Double allocated: " << *doublePtr << "\n";
        // Allocate an array of characters
        char* charArray = static_cast<char*>(arena.allocate(20));
        std::fill(charArray, charArray + 20, 'A');
        charArray[19] = '\0';
        std::cout << "Char array allocated: " << charArray << "\n";
        // Display arena usage
        std::cout << "Used memory: " << arena.getUsedSize() << " bytes\n";
        std::cout << "Remaining memory: " << arena.getRemainingSize() << " bytes\n";
        // Reset the arena
        arena.reset();
        std::cout << "Arena reset. Remaining memory: " << arena.getRemainingSize() << " bytes\n";
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << "\n";
    }
    return 0;
}   

输出

 
Integer allocated: 42
Double allocated: 3.14159
Char array allocated: AAAAAAAAAAAAAAAAAAA
Used memory: 36 bytes
Remaining memory: 988 bytes
Arena reset. Remaining memory: 1024 bytes

说明

1. 设置 Arena

程序开始时会创建一个名为“arena”的内存池。这是一个预先分配的大块内存，将作为所有内存请求的来源。使用指针（current）来跟踪 arena 内下一个可访问的位置。另一个变量跟踪已使用的内存量。

2. 分配内存

当请求内存时，分配器会检查 arena 中是否还有足够的空间来满足该请求。如果内存足够

调整 current 指针以确保内存正确对齐（基于数据类型的大小或任何特定对齐要求）。
通过简单地返回 current 指针的位置，然后将指针向前移动请求分配的大小来“分配”内存。

如果请求超过了 arena 中剩余的空间，程序将抛出错误以指示分配无法完成。

3. 处理对齐

对于某些类型的数据（例如双精度浮点数或其他具有严格对齐规则的类型），分配器会确保内存地址满足对齐要求。它会计算对齐 current 指针所需的偏移量，并在分配内存之前相应地调整它。这确保了内存对于系统来说是有效且高效的。

4. 重置 Arena

与标准内存分配不同，arena 分配器不允许释放单个分配。相反，可以通过将 current 指针重置回块的开头来一次性释放 arena 中的所有内存。这使其对于临时数据或范围内的任务非常高效，其中所有对象都会一起被丢弃。

5. 错误处理

程序包含保护措施

如果请求的大小为零或超过可用内存，它将抛出错误。
如果由于内存不足而无法满足对齐要求，它也将发出错误信号。

这确保了分配器是健壮的，并且不会损坏内存。

6. 内存诊断

为了更好地进行调试，程序提供了有关内存使用情况的详细信息

它可以显示到目前为止已分配了多少内存（usedSize）。
它可以显示还有多少内存可用（remainingSize）。

这些指标有助于程序员有效跟踪和管理内存使用情况。

7. 使用示例

该程序演示了为不同数据类型分配内存，包括

一个整数。
一个具有特定对齐方式的浮点数。
一个字符数组。

每次分配后，它都会显示 arena 如何调整以适应新内存。所有任务完成后，arena 将被重置，所有内存将再次可用。

8. 高效内存管理

arena 分配器通过使用简单的指针调整而不是复杂的系统级内存管理来避免碎片并加快分配速度。这使其非常适合游戏、编译器或具有相似生命周期的对象一起创建和销毁的系统等应用程序。

复杂度分析

时间复杂度

内存分配

分配涉及将指针向前移动请求内存的大小，并确保适当的对齐。这两种操作都是常数时间操作。
时间复杂度：每次分配 O(1)。

重置操作

重置 arena 只需将指针移回内存块的开头。
时间复杂度：O(1)。

整体效率

分配器避免了传统内存分配器的复杂簿记，确保所有操作保持快速且可预测。
迭代分配和重置操作保持一致的 O(1) 性能，与分配数量无关。

空间复杂度

内存块

分配器使用的空间是预分配内存块的大小，它是固定的，并在初始化时确定。
额外的空间用于几个指针和大小变量，与块大小相比微不足道。
空间复杂度：O(n)，其中 n 是预分配内存块的大小。

对齐开销

可能会浪费一些内存以确保数据的正确对齐，但这很小，并且取决于分配类型的对齐要求。

未使用的内存

如果请求的总内存量远小于 arena 大小，则剩余的未使用的空间仍然占用内存，但保持未被利用。

方法 1：基于块的 Arena 分配器

这种方法通过将 arena 分为固定大小的块来提高灵活性，这些块可以有效地处理多个分配。当内存请求大小不同时，它效果很好，避免了因对齐问题造成的内存浪费。

程序

 
#include <iostream>
#include <vector>
#include <cstddef>
#include <stdexcept>
#include <new>
class ChunkBasedArenaAllocator {
private:
    struct Chunk {
        char* data;         // Pointer to the memory block
        size_t capacity;    // Capacity of the chunk
        size_t offset;      // Current offset within the chunk
        Chunk(size_t size) : capacity(size), offset(0) {
            data = new char[size];
        }
        ~Chunk() {
            delete[] data;
        }
        // Allocate memory from the chunk
        void* allocate(size_t size, size_t alignment) {
            uintptr_t currentPtr = reinterpret_cast<uintptr_t>(data + offset);
            size_t padding = (alignment - (currentPtr % alignment)) % alignment;
            if (offset + padding + size > capacity) {
                return nullptr; // Not enough space
            }
            offset += padding; // Adjust for alignment
            void* allocation = data + offset;
            offset += size;
            return allocation;
        }
    };
    std::vector<Chunk*> chunks; // List of allocated chunks
    size_t chunkSize;           // Size of each chunk
public:
    explicit ChunkBasedArenaAllocator(size_t initialChunkSize) : chunkSize(initialChunkSize) {
        chunks.push_back(new Chunk(chunkSize));
    }
    void* allocate(size_t size, size_t alignment = alignof(std::max_align_t)) {
        if (size > chunkSize) {
            throw std::bad_alloc(); // Request exceeds maximum chunk size
        }
        for (auto& chunk : chunks) {
            void* allocation = chunk->allocate(size, alignment);
            if (allocation != nullptr) {
                return allocation;
            }
        }
        // If no space in existing chunks, create a new chunk
        Chunk* newChunk = new Chunk(chunkSize);
        chunks.push_back(newChunk);
        return newChunk->allocate(size, alignment);
    }
    void reset() {
        for (auto& chunk : chunks) {
            chunk->offset = 0; // Reset offset in each chunk
        }
    }
    ~ChunkBasedArenaAllocator() {
        for (auto& chunk : chunks) {
            delete chunk;
        }
    }
};
int main() {
    try {
        constexpr size_t CHUNK_SIZE = 256; // Each chunk has 256 bytes
        ChunkBasedArenaAllocator allocator(CHUNK_SIZE);
        // Allocate an integer
        int* intPtr = static_cast<int*>(allocator.allocate(sizeof(int)));
        *intPtr = 123;
        std::cout << "Integer: " << *intPtr << "\n";
        // Allocate a double
        double* doublePtr = static_cast<double*>(allocator.allocate(sizeof(double)));
        *doublePtr = 45.67;
        std::cout << "Double: " << *doublePtr << "\n";
        // Allocate a character array
        char* charArray = static_cast<char*>(allocator.allocate(50));
        std::fill(charArray, charArray + 50, 'X');
        charArray[49] = '\0';
        std::cout << "Char Array: " << charArray << "\n";
        // Reset the allocator
        allocator.reset();
        std::cout << "Allocator reset. Memory can be reused.\n";
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << "\n";
    }
    return 0;
}   

输出

 
Integer: 123
Double: 45.67
Char Array: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Allocator reset. Memory can be reused.

说明

1. Arena 的结构

在基于块的 arena 分配器中，arena 被划分为较小的块，每个块都是固定大小的内存块。这种设计允许更灵活的内存管理，因为它可以在不同块之间容纳多个分配，从而减少内存池内浪费空间的可能性。

分配器从一个初始块开始，如果需要，可以动态创建新块。这避免了如果所有内容都从一个大块分配可能发生的内存碎片问题。

2. 分配过程

当请求内存时

分配器首先检查现有块中是否有足够的可用空间来满足请求。每个块都有一定量的内存，并且一个指针（offset）跟踪下一个分配可以从块内的哪个位置开始。
为了确保数据类型的正确对齐，分配器可能会在块内的内存分配之间添加一些填充。
如果请求的大小适合当前块，则通过调整偏移量使其指向下一个可用位置来分配内存。如果当前块没有足够的空间，分配器将检查下一个块，重复此过程。
如果现有块中没有足够的空间来容纳新分配，分配器将创建一个新的内存块，并在那里继续分配过程。

3. 处理对齐

每种数据类型通常都有特定的内存对齐要求（例如，双精度浮点数可能需要在 8 字节边界上对齐）。基于块的分配器确保任何分配都尊重这些对齐要求。如果需要，它会调整指针以确保每个分配都从正确的内存地址开始。

4. Arena 的动态增长

基于块的 arena 分配器从一个块开始，但可以随着需要更多内存而通过创建新块来动态增长。

这使得分配器能够有效地处理不同大小的内存请求，因为当现有块用完时，可以添加新块。

5. 重置 Arena

当程序完成分配后，可以重置 arena。分配器不释放单个内存块，而是将每个块的偏移量重置为 0。这有效地一步“释放”了所有内存，使 arena 可用于新分配。

此重置过程非常高效，因为它只需要重置几个指针，而不是遍历整个内存块来单独取消分配每个项目。

6. 内存清理

一旦分配器不再需要，它会通过删除块及其关联的内存来清理。这可以防止内存泄漏，确保分配器超出范围时所有内存都已释放。

7. 此方法的优点

高效内存管理：通过将 arena 分为块，分配器可以更有效地处理不同大小的分配，从而最大程度地减少浪费的空间。
动态增长：arena 可以根据需要增长，确保大请求不会耗尽内存。
简单的重置：重置功能很快，不需要单独释放分配，非常适合短暂的对象或任务。
对齐处理：正确的对齐可确保分配的内存适用于不同的数据类型，避免对齐问题。

复杂度分析

时间复杂度

内存分配

分配过程包括检查每个块的可用空间、调整指针和对齐内存。这是每个块的常数时间操作。由于每个块足够大以处理多个分配，因此从块中分配内存所需的时间为 O(1)。
如果一个块已满，则会创建一个新块，该过程也需要 O(1) 时间。
分配的总体时间复杂度：每次分配 O(1)，假设分配适合当前块或已成功分配给新块。

重置 Arena

重置分配器只需重置每个块的偏移量，这是一个 O(1) 操作。
重置的总体时间复杂度：O(k)，其中 k 是块的数量（因为每个块的偏移量都会被重置）。

空间复杂度

分配器使用的空间与创建的块的大小成正比。每个块都是一个连续的内存块，并且根据需要动态分配新块。
空间复杂度：O(n)，其中 n 是所有块的总内存量。随着创建更多块来满足内存请求，它会增长。

下一个主题C++ 中最小化给定数组之间对应索引处不相等元素的计数

← 上一篇下一个 →

C++ 区域分配

引言

程序

说明

复杂度分析

方法 1：基于块的 Arena 分配器

程序

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 区域分配

引言

程序

说明

复杂度分析

方法 1：基于块的 Arena 分配器

程序

说明

复杂度分析

相关帖子

C++ 中的 std::views::cartesian_product

C++ 中的卡塔德罗姆数

如何在 C++ 中的 std::unordered_map 中为用户定义类型实现自定义哈希函数

C++ std::chrono::nonexistent_local_time

C++ 虚函数与内联函数的区别

C++ 中所有蚂蚁从木板上掉落前的最后一刻

C++ 中的超图实现

C++ 中惰性求值与急切求值的区别

C++ 中的 std::codecvt::out 和 do_out

C++ 宝石和石头

订阅 Tpoint Tech

联系信息