一、分享简介
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