首页 > 系统相关 >支持外部内存功能的STL容器使用方法分享

支持外部内存功能的STL容器使用方法分享

时间:2024-09-17 17:46:50浏览次数:10  
标签:容器 STL 元素 数据类型 使用 内存 CUnordered

一、分享简介

       C++的STL支持了多种容器供开发者操作,然而这些容器使用的是系统内存,使用者无法直接管理。边缘端的嵌入式设备通常会要求对使用的内存进行管理,因此封装出支持外部内存功能的STL容器就显得十分必要。本案例针对被封装容器的使用方法进行了经验分享,具体涉及3种顺序容器(CVector/CList/CString),以及7种关联容器(CSet/CMultiset/CUnordered_set/CMap/CMultimap/CUnordered_map/CUnordered_multimap)。

二、封装容器使用方法

2.1 CVector容器

// 使用示例
using VectorContainer = CVector<int, MyAlloc::CAllocator<int, MEM_TYPE, nullptr>>;

       使用CVector容器时,需要依次指定容器的元素类型、内存分配器的数据类型、内存类型和内存池句柄,其中后三个参数属于内存分配器的内容,可以省略,但此时封装容器不再支持外部内存,将使用STL标准容器的内存分配器分配系统内存。在上述代码示例中,元素类型为int,内存分配器的数据类型为int,内存类型为MEM_TYPE,内存池句柄为空。

       为了方便使用,建议使用using关键字为CVector容器取一个新的别名,如VectorContainer。封装后的CVector容器支持的操作包括(若无特别声明,使用方法与STL标准容器中vector的相应操作一致):

  • Constructor:无参构造一个容器;拷贝构造一个容器;移动构造一个容器;赋值构造一个容器(operator"=");构造含有n个元素,每个元素的值均为value的一个容器;构造元素范围为[first, last]的一个容器。
  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Capacity:size();resize();capacity();empty();reserve()。
  • Element access:front();back();data();operator"[]"。
  • Modifiers:push_back();emplace_back();pop_back();erase();insert();clear();assign()。
  • Non-member function overloads:swap()。

       CVector容器在内存操作上同STL中的vector,底层是一段内存连续的数组,当内存不够时会申请2倍大小的内存(不同编译器申请的内存不同)扩容,并将数组的内容拷贝至新内存中。在清除元素时,被清除元素的内存空间并不会被释放,只是改变了容器的size(),并没有改变容器的capacity(),因此整个容器的内存大小只增不减,若希望释放空间的内存,可以通过swap()方法将原容器与一个临时的匿名容器交换的方式实现,当交换之后,临时容器被销毁时,其内存也会被释放。

       CVector容器支持随机存取,但对中间元素进行添加或删除时,需要移动内存,且可能会执行构造和析构的操作,进而影响性能,适用于元素结构简单,需要经常进行随机访问,且不需要经常对中间元素执行添加或删除操作的场景。

2.2 CList容器

// 使用示例
using ListContainer = CList<int, MyAlloc::CAllocator<int, MEM_TYPE, nullptr>>;

       CList容器的使用方法同CVector容器的使用方法一致。为了方便使用,建议使用using关键字为CList容器取一个新的别名,如ListContainer。封装后的CList容器支持的操作包括(若无特别声明,使用方法与STL标准容器中list的相应操作一致):

  • Constructor:无参构造一个容器;拷贝构造一个容器;移动构造一个容器;赋值构造一个容器(operator"=");构造含有n个元素,每个元素的值均为value的一个容器;构造元素范围为[first, last]的一个容器。
  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Element access:front();back()。
  • Modifiers:push_back();pop_back();push_front();pop_front();erase();insert();clear()。
  • Capacity:size()。
  • Operations:remove()。

       CList容器的begin()迭代器和end()迭代器不是随机访问迭代器,均属于双向迭代器,它们不能执行加减整数的运算,所以修改本容器迭代器的唯一方法是使用自增或自减运算。

       CList容器的底层为双向链表,内存空间可以不连续,通过指针来访问数据,每分配一个元素都会从内存中分配存储空间,每删除一个元素都会释放它占用的内存。CList容器在随机存取元素时执行效率低,占用内存较多,但可以高效的支持在任意地方删除和插入元素,适用于需要经常执行快速插入或删除中间元素的场景。

2.3 CString容器

// 使用示例
using StringContainer = CString<MyAlloc::CAllocator<char, MEM_TYPE, nullptr>>;

       Cstring容器是基于容器类模板std::basic_string封装而成的,该类模版管理的对象是标准的C++字符串序列,而标准C++字符串类是一个容器,所以可以基于std::basic_string封装容器。常用的std::string其实是形参为char的basic_string类模版的一个别名,它使用了std::basic_string默认的迭代器类型,不能支持外部内存,所以不能基于std::string封装CString容器。

       由于希望把CString容器当作std::string使用,所以在封装时已经为std::basic_string指定了字符串中单个字符的数据类型为char型,因此在使用本容器时,仅需要指定内存分配器的数据类型、内存类型和内存池句柄,这三个参数均属于内存分配器的内容,可以省略,但此时封装容器不再支持外部内存,将使用STL标准容器的内存分配器分配系统内存。在上述代码中,内存分配器的数据类型为char,内存类型为MEM_TYPE,内存池句柄为空。

       为了方便使用,建议使用using关键字为CString容器取一个新的别名,如StringContainer。封装后的CString容器支持的操作包括(若无特别声明,使用方法与STL标准容器中basic_string的相应操作一致):

  • Constructor:无参构造一个容器;拷贝构造一个容器(标准C++字符串/字符串数组);移动构造一个容器;赋值构造一个容器(operator"=")。
  • Operator overloads:"<";"=="。
  • Element access:operator"[]"。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:operator"+=";push_back();append();erase()。
  • String operations:find();rfind();compare();substr()。
  • Capacity:size();resize()。
  • Non-member function overloads:operator"<<";operator">>"。

       CString容器存储了可变长度的字符序列,虽然不用考虑字符越界的问题,但操作效率较低,适用于操作未知长度的字符串。当在字符串中执行查找操作时,若没有匹配到查找位置,此时操作结果会返回一个常数std::string::npos,它用来表示一个不存在的位置,可以保证大于任何有效的下标值,该常数具体为2的64次方-1,即64位机的最大值18446744073709551615。

2.4 CSet容器

// 使用示例
using SetContainer = CSet<int, MyAlloc::CAllocator<int, MEM_TYPE, nullptr>>;

       CSet容器的使用方法同CVector容器的使用方法一致。为了方便使用,建议使用using关键字为CSet容器取一个新的别名,如SetContainer。封装后的CSet容器支持的操作包括(若无特别声明,使用方法与STL标准容器中set的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ()。
  • Operations:count();find()。
  • Capacity:size()。

       CSet容器基于红黑树(RB Tree)实现,其内部元素依照规则自动排序,每个元素是唯一的,无重复的,且是有序的,其插入、删除、搜索等操作的效率稳定且较高,时间复杂度均为O(log n),但不能直接改变元素值,要改变元素值必须先删除旧元素,再插入新元素,整个容器的内存消耗较高。CSet容器适用于存储有排序要求的无重复元素,且要求经常快速查找或删除的场景。

       CSet容器会对元素进行比较和排序,当CString等封装容器作为CSet容器的元素时,相当于CSet容器存储了自定义类型的元素,需要重载CString等封装容器的比较运算符"<",其他自定义的数据类型如类、结构体也需要在数据类型内部重载比较运算符,给自定义的数据一个比较准则,而CSet容器对内置的基本数据类型则有默认的比较准则std::less<T>。

2.5 CMultiset容器

// 使用示例
using MultiSetContainer = CMultiset<int, MyAlloc::CAllocator<int, MEM_TYPE, nullptr>>;

       CMultiset容器的使用方法同CSet容器的使用方法一致。为了方便使用,建议使用using关键字为CMultiset容器取一个新的别名,如MultiSetContainer。封装后的CMultiset容器支持的操作包括(若无特别声明,使用方法与STL标准容器中multiset的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ()。

       CMultiset容器基于红黑树(RB Tree)实现,其内部元素依照规则自动排序,允许有重复的元素。本容器插入、删除、搜索等操作的效率稳定且较高,时间复杂度均为O(log n),但和CSet容器一样,不能直接改变元素值,要改变元素值必须先删除旧元素,再插入新元素,整个容器的内存消耗较高。CMultiset容器适用于存储有排序要求的元素,且要求经常快速查找或删除的场景。

       CMultiset容器会对元素进行比较和排序,所以和CSet容器一样,当CString等封装容器以及其他自定义的数据类型如类、结构体作为CMultiset容器的元素时,需要重载关于它们的比较运算符"<",给自定义的数据一个比较准则,同时本容器对内置的基本数据类型也有默认的比较准则std::less<T>。

2.6 CUnordered_set容器

// 使用示例,元素为内置基本数据类型
using UnordSetContainer = CUnordered_set<int, MyAlloc::CAllocator<int, MEM_TYPE, nullptr>>;
// 使用示例,元素为自定义数据类型,如CString
using UnordSetContainer = CUnordered_set<StringContainer, MyAlloc::CAllocator<StringContainer, MEM_TYPE, nullptr>, CString_Hash>;

       当内置的基本数据类型作为CUnordered_set容器的元素时,本容器的使用方法同CSet容器的使用方法一致;当CString等封装容器以及其他自定义的数据类型作为CUnordered_set容器的元素时,本容器还需要额外指定一个特例化的哈希函数,如CString_Hash。需要注意的是,哈希函数只是一个称谓(便于理解),其本体并不是普通的函数形式,而是一个函数对象类。

       为了方便使用,建议使用using关键字为CUnordered_set容器取一个新的别名,如UnordSetContainer。封装后的CUnordered_set容器支持的操作包括(若无特别声明,使用方法与STL标准容器中unordered_set的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ()。
  • Element lookup:find()。

       CUnordered_set容器基于哈希表实现,其元素无序且唯一,容器通过元素值的哈希值将元素分组放置到各个槽。本容器可以高效地访问各个元素,时间复杂度为O(1),但消耗较多的内存,且可能会遇到哈希冲突,适用于元素无序,但需要快速访问的场景。

       当内置的基本数据类型作为CUnordered_set容器的元素时,容器内部会使用默认的哈希函数模板std::hash<T>来获取哈希值,而当CString等封装容器以及其他自定义的数据类型作为本容器的元素时,本容器则要求以函数对象类的方式,通过定义一个一元操作符operator()来特例化实现哈希函数,如CString_Hash:

// 关于StringContainer容器的哈希函数
class CString_Hash
{
public:
    std::size_t operator()(const StringContainer &str) const
    {
        return std::hash<std::size_t>()(str.size() *2024);
    }
};

       由于容器底层基于哈希表,需要解决哈希碰撞的问题,因此必须判断两个对象是否相等。当基本数据类型作为CUnordered_set容器的元素时,容器内部会使用默认的判等函数模板std::equal_to<T>来指定容器内的元素是否相等,对于这种判等规则,其在底层实现过程中,直接用"=="运算符判断容器中任意两个元素是否相等,这意味着如果容器中存储的元素类型,支持直接用"=="运算符判断是否相等,则CUnordered_set等无序容器可以使用默认的std::equal_to<T>,反之就不可以使用。因此,当自定义的数据类型作为CUnordered_set容器的元素时,容器要求在元素内部重载"=="运算符,使得std::equal_to<T>判等规则中使用的"=="运算符变得合法。

       std::equal_to<T>在本质也是一个函数对象类,因此当自定义的数据类型作为CUnordered_set容器的元素时,也可以完全舍弃std::equal_to<T>,使用函数对象类的方式自定义一个判等规则,类似于特例化哈希函数的做法。

2.7 CMap容器

// 使用示例
using MapContainer = CMap<int, int, MyAlloc::CAllocator<std::pair<const int, int>, MEM_TYPE, nullptr>>;

       使用CMap容器时,需要依次指定容器内元素的键(key)类型、元素的值(value)类型、内存分配器的键-值对类型、内存类型和内存池句柄,其中后三个参数属于内存分配器的内容,可以省略,但此时封装容器不再支持外部内存,将使用STL标准容器的内存分配器分配系统内存。在上述图例中,元素的键类型为int,元素的值类型也为int,内存分配器的键-值对类型为std::pair<const int, int>,内存类型为MEM_TYPE,内存池句柄为空。

       为了方便使用,建议使用using关键字为CMap容器取一个新的别名,如MapContainer。封装后的CMap容器支持的操作包括(若无特别声明,使用方法与STL标准容器中map的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ();clear()。
  • Capacity:size()。
  • Operations:count();find()。

       CMap容器基于红黑树实现,不允许key重复,且元素根据元素的key自动排序。本容器内元素的key不能被修改,但是元素的value可以被修改,其插入、查找操作的效率较高,时间复杂度均为O(log n),同时整个容器的内存消耗也较高。CMap容器的性能稳定,适用于需要快速处理一对一关系的数据场景。

       和其它基于RB Tree的容器一样,CMap容器也会对元素进行比较和排序,所以当CString等封装容器以及其他自定义的数据类型作为CMap容器内元素的键(key)时,需要重载关于它们的比较运算符"<",给自定义的数据一个比较准则,同时本容器对内置的基本数据类型也有默认的比较准则std::less<T>。

2.8 CMultimap容器

// 使用示例
using MultiMapContainer = CMultimap<int, int, MyAlloc::CAllocator<std::pair<const int, int>, MEM_TYPE, nullptr>>;

       CMultimap容器的使用方法同CMap容器的使用方法一致。为了方便使用,建议使用using关键字为CMultimap容器取一个新的别名,如MultiMapContainer。封装后的CMultimap容器支持的操作包括(若无特别声明,使用方法与STL标准容器中multimap的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ()。

       CMultimap容器基于红黑树实现,元素是有序的,容器内可包含多个键(key)相同的元素,即允许一键(key)对应多值(value),但内存消耗高。本容器性能稳定,其插入操作的时间复杂度为O(log n),适用于需要快速处理一对多关系的数据场景。

       CMultimap容器会对元素进行比较和排序,所以和CMap容器一样,当自定义的数据类型作为本容器元素的键(key)时, 需要重载关于它们的比较运算符"<",给自定义的数据一个比较准则,同时CMultimap容器对内置的基本数据类型也有默认的比较准则std::less<T>。

2.9 CUnordered_map容器

// 使用示例,元素为内置基本数据类型
using UnordMapContainer = CUnordered_map<int, int, MyAlloc::CAllocator<std::pair<const int, int>, MEM_TYPE, nullptr> >;
// 使用示例,元素为自定义数据类型,如CString
using UnordMapContainer = CUnordered_map<StringContainer, int, MyAlloc::CAllocator<std::pair<const StringContainer, int>, MEM_TYPE, nullptr>, CString_Hash>;

       当CUnordered_map容器内元素的键(key)为内置的基本数据类型时,本容器的使用方法同CMap容器的使用方法一致;当CUnordered_map容器内元素的键(key)为自定义的数据类型时,本容器还需要额外指定一个特例化的哈希函数,如CString_Hash。

       为了方便使用,建议使用using关键字为CUnordered_map容器取一个新的别名,如UnordMapContainer。封装后的CUnordered_map容器支持的操作包括(若无特别声明,使用方法与STL标准容器中unordered_map的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ();clear()。
  • Element lookup:count();find()。
  • Capacity:size();empty()。
  • Hash policy:reserve()。

       CUnordered_map容器基于哈希表实现,当哈希映射位置的数据量在8以内时使用链表来存储数据,当该位置的数据量大于8时则自动转换为红黑树结构存储数据,容器内元素的键(key)是唯一的,本容器的查询速度快,其时间复杂度为O(1),但查询性能不稳定,且内存消耗高。在对数据不要求有序的情况下,建议尽量使用CUnordered_map而不是CMap。

       同CUnordered_set容器类似,当内置的基本数据类型作为CUnordered_map容器内元素的键(key)时,容器内部会使用默认的哈希函数模板std::hash<T>来获取哈希值,而当CString等封装容器以及其他自定义的数据类型作为本容器内元素的键(key)时,本容器则要求以函数对象类的方式,通过定义一个一元操作符operator()来特例化实现哈希函数,如CString_Hash。

       同CUnordered_set容器类似,当内置的基本数据类型作为CUnordered_map容器内元素的键(key)时,容器内部会使用默认的判等函数模板std::equal_to<T>来指定容器内的元素是否相等,当自定义的数据类型作为CUnordered_map容器内元素的键(key)时,容器要求在元素内部重载"=="运算符,使得std::equal_to<T>判等规则中使用的"=="运算符变得合法。除此之外,当自定义的数据类型作为本容器内元素的键(key)时,也可以完全舍弃std::equal_to<T>,使用函数对象类的方式自定义一个判等规则,类似于特例化哈希函数的做法。

2.10 CUnordered_multimap容器

// 使用示例,元素为内置基本数据类型
using UnordMultiMapContainer = CUnordered_multimap<int, int, MyAlloc::CAllocator<std::pair<const int, int>, MEM_TYPE, nullptr>>;
// 使用示例,元素为自定义数据类型,如CString
using UnordMultiMapContainer = CUnordered_multimap<StringContainer, int, MyAlloc::CAllocator<std::pair<const StringContainer, int>, MEM_TYPE, nullptr>, CString_Hash>;

       CUnordered_multimap容器的使用方法同CUnordered_map容器的使用方法一致。为了方便使用,建议使用using关键字为本容器取一个新的别名,如UnordMultiMapContainer。封装后的CUnordered_multimap容器支持的操作包括(若无特别声明,使用方法与STL标准容器中unordered_multimap的相应操作一致):

  • Operator overloads:"<";"=="。
  • Iterators:begin();end();cbegin();cend()。
  • Modifiers:insert ()。

       CUnordered_multimap容器基于哈希表结构实现,可以存储多个键(key)相等的元素,且这些键相等的元素会被哈希到同一个桶中存储,但这也导致无法直接访问元素。本容器适用于需要快速处理多对多关系的数据场景。

       同CUnordered_map容器类似,当内置的基本数据类型作为CUnordered_multimap容器内元素的键(key)时,容器内部会使用默认的哈希函数模板std::hash<T>来获取哈希值,而当CString等封装容器以及其他自定义的数据类型作为本容器内元素的键(key)时,本容器则要求以函数对象类的方式,通过定义一个一元操作符operator()来特例化实现哈希函数,如CString_Hash。

       同CUnordered_map容器类似,当内置的基本数据类型作为CUnordered_multimap容器内元素的键(key)时,容器内部会使用默认的判等函数模板std::equal_to<T>来指定容器内的元素是否相等,当自定义的数据类型作为CUnordered_multimap容器内元素的键(key)时,容器要求在元素内部重载"=="运算符,使得std::equal_to<T>判等规则中使用的"=="运算符变得合法。除此之外,当自定义的数据类型作为本容器内元素的键(key)时,也可以完全舍弃std::equal_to<T>,使用函数对象类的方式自定义一个判等规则,类似于特例化哈希函数的做法。

标签:容器,STL,元素,数据类型,使用,内存,CUnordered
From: https://www.cnblogs.com/kongzimengzixiaozhuzi/p/18417308

相关文章

  • C++内存管理详解:各类变量的存储区域
      在C++中,变量的存储位置取决于它们的类型和生命周期。那么不同的各个变量究竟存储在哪个区域呢?1.不同类型的变量我们首先从变量类型的不同来说明:1.全局变量和静态变量 -存储区:全局/静态区(静态区)-说明:全局变量(包括文件级和函数级的)和使用`static`关键字声明的变......
  • 容器目录清理
    过程分析在异常节点后台使用“df-h|grepdev”命令查看磁盘使用率,发现/var/lib/docker/目录所在磁盘分区达到了70%以上。而后通过cdvar/lib/docker下执行du-sh*|grepG查看当前路径下子目录的大小,发现containers目录的占用极大。该情况下的资源利用率异常应该是日志占......
  • JVM内存结构
    JVM内存结构JVM在执行程序的过程中会将内存划分为五个不同的数据区域:虚拟机栈、本地方法栈、方法区、堆、程序计数器。JVM五个区中虚拟机栈、本地方法栈、程序计数器为线程私有,方法区和堆为线程共享区。JVM不同区域的占用内存大小不同,一般情况下堆最大,用来存放”对象“,程......
  • 图文深入理解Oracle体系结构之内存篇
    前面在Oracle体系结构概述篇中总体介绍了Oracle的体系结构,接下来分别详细深入介绍其组成部分的各个模块的功能与作用,本篇先深入内存部分。一.先上图:OracleDB内存结构图OracleDB实例的两大基本内存结构(也有的说三大:SGA/PGA/UGA,但是UGA基本包含于SGA(共享服务器模式)或......
  • 关于数据在内存中如何存储
    1.整数在内存中的存储在讲解操作符的时候,我们就讲过了下⾯的内容:整数的2进制表⽰⽅法有三种,即原码、反码和补码有符号的整数,三种表⽰⽅法均有符号位和数值位两部分,符号位都是⽤0表⽰“正”,⽤1表⽰“负”,最⾼位的⼀位是被当做符号位,剩余的都是数值位。 正整数的原、反、......
  • 内存函数的
    1.memcpy使⽤和模拟实现 void*memcpy(void*destination,constvoid*source,size_tnum);•函数memcpy从source的位置开始向后复制num个字节的数据到destination指向的内存位置。•这个函数在遇到'\0'的时候并不会停下来。•如果source和destination有任......
  • 范围 for,new 内存动态分配,nullptr
    范围for,new内存动态分配,nullptr范围forintmain(){intarr[]={11,12,13,14,15};for(autox:arr){//问题所在:需要将arr中的每一个都拷贝到x中去===>节省拷贝的方法:使用指针,提升效率cout<<x<<endl;}cout<<"============......
  • AUTOSAR -- SHE 内存槽更新
    AUTOSAR--SHE内存槽更新引言AUTOSAR(AUTomotiveOpenSystemARchitecture)是一个开放的、标准化的汽车软件架构,旨在为汽车电子系统提供一个统一的软件平台。在AUTOSAR中,安全硬件扩展(SecureHardwareExtension,SHE)是一个关键组件,用于保护汽车电子控制单元(ECU)中的敏感数据和代码。S......
  • 容器化部署LDAP
    容器化部署LDAP和PHP-LDAP-Admin可以帮助你在Docker环境中快速搭建和管理LDAP服务。1.部署OpenLDAP容器password='123456'dockerrun\-d-p389:389-p636:636\--nameopenldap\--restart=always\--hostnameopenldap\-v/data/docker_tmp/openldap......
  • 数据的容器 列表 scratch 20240916_155811
    什么是列表列表是数据的容器创建列表列表添加内容清空内容查找数据根据位置查找数据修改数据删除数据根据下标删除数据遍历所有数据让主角依次把所有的数据都说一遍......