个人网站建站申请,免费网站根目录,湖南网站优化代运营,品牌网上做推广C的标准容器及其应用 数组#xff08;array#xff09;数组的特征应用实列 前向列表#xff08;forward_list#xff09;前向列表的特征应用实列 列表#xff08;list#xff09;列表的特征应用实列 有序映射#xff08;map#xff09;有序映射的特征应用实列 队列的标准容器及其应用 数组array数组的特征应用实列 前向列表forward_list前向列表的特征应用实列 列表list列表的特征应用实列 有序映射map有序映射的特征应用实列 队列queue队列的特征应用实列priority_queue应用实列 集合set集合的特征应用实列 堆栈stack堆栈的特征应用实列 无序映射unordered_map无序映射的特征应用实列 无序集合unordered_set无序集合的特征应用实列 向量vector向量的特征应用实列 数组array
数组的特征
数组是固定大小的序列容器它按严格线性序列保存排序的特定数量的元素。
在内部数组除了它包含的元素之外不保留任何数据甚至不保留其大小这是一个模板参数在编译时固定。就存储大小而言它与使用语言的括号语法 ([]) 声明的普通数组一样高效。这个类只是添加了一层成员函数和全局函数这样数组就可以作为标准容器使用了。
与其他标准容器不同数组具有固定大小并且不能通过分配器管理其元素的分配它们是封装固定大小元素数组的聚合类型。因此它们不能动态扩展或收缩。
零大小的数组是有效的但不能调用它的成员函数比如front, back和data。
与标准库中的其他容器不同交换两个数组容器是一种线性操作涉及单独交换范围中的所有元素这通常是效率相当低的操作。另一方面这允许两个容器中的元素的迭代器保持其原始容器关联。
数组容器的另一个独特功能是它们可以被视为元组tuple对象 array 能重载 get 函数以访问数组的元素就好像它是元组一样拥有专门的 tuple_size 和 tuple_element 类型。
应用实列
成员函数size()。
#include iostream
#include arrayusing namespace std;int main ()
{arrayint,5 arr_int {0};cout size of arr_int: arr_int.size() endl;cout sizeof(arr_int): sizeof(arr_int) endl;return 0;
}size of arr_int: 5
sizeof(arr_int): 20成员函数data()。
#include iostream
#include cstring
#include arrayusing namespace std;int main ()
{const char* cstr Test string;arraychar,12 charr;memcpy (charr.data(),cstr,12);cout charr.data() \n;return 0;
}
// output
Test string前向列表forward_list
前向列表的特征
前向列表是序列容器可以用不变的时间在序列中任何位置进行插入和删除。
前向列表作为单链表实现单链表可以将它们包含的每个元素存储在不同且不相关的存储位置。通过与序列中下一个元素的链接的每个元素的关联来保持顺序。
forward_list 容器和列表容器之间的主要设计区别在于第一个容器仅在内部保留到下一个元素的链接而后者为每个元素保留两个链接一个指向下一个元素一个指向前一个元素从而实现高效双向迭代但每个元素消耗额外的存储空间并且插入和删除元素的时间开销稍高。因此forward_list 对象比 list 对象更有效尽管它们只能向前迭代。
与其他基本标准序列容器数组、向量和双向队列相比在容器内任何位置插入、提取和移动元素forward_list 通常表现更好因此在密集使用这些元素的算法如排序算法中也表现得更好。
与其他序列容器相比forward_lists 和list的主要缺点是它们无法通过位置直接访问元素例如要访问forward_list中的第六个元素必须从开头迭代到该位置这需要这些元素之间的距离呈线性时间。它们还消耗一些额外的内存来保存与每个元素关联的链接信息这对于小型元素的大型列表可能是一个重要因素。
forward_list 类模板在设计时就考虑到了效率根据设计它与简单的手写 C 风格单链表一样高效事实上它是唯一出于效率考虑,而故意缺少 size 成员函数的标准容器由于其作为链表的性质具有需要恒定时间的大小成员将需要它为其大小保留一个内部计数器如列表那样。这会消耗一些额外的存储空间并使插入和删除操作的效率稍微降低。如果需要获取forward_list对象的大小可以使用距离算法加上开始和结束参数这需要线性操作时间。
应用实列
插入元素
#include iostream
#include forward_listusing namespace std;int main ()
{forward_listint mylist;forward_listint::iterator it;it mylist.insert_after ( mylist.before_begin(), 10 );it mylist.insert_after ( it, 2, 20 ); it mylist.begin(); it mylist.insert_after ( it, {1,5,3} ); cout mylist contains:;for (auto x: mylist) cout x;cout endl;return 0;
}
// output
mylist contains: 10 1 5 3 20 20列表list
列表的特征
list是序列容器在list中的任何位置进行插入和擦除操作只需要恒定时间。list可以双向迭代。
list容器是用双向链表实现的双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置。通过与每个元素的关联在内部保持顺序。
它们与forward_list非常相似主要区别在于forward_list对象是单向链表因此它们只能向前迭代以换取更小和更高效的代价。
与其他基本标准序列容器数组、向量和双端队列相比list在已获得迭代器的容器内的任何位置插入、提取和移动元素方面通常表现更好因此经常出现在密集使用元素操作的算法中例如排序算法。
与其他序列容器相比list和前向列表的主要缺点是它们无法通过位置直接访问元素例如要访问列表中的第六个元素必须从已知位置例如开头或结尾迭代到该位置这需要这些位置之间的距离呈线性时间。它们还消耗一些额外的内存来保存与每个元素关联的链接信息。
应用实列
在表头插入操作
#include iostream
#include listusing namespace std;int main ()
{listint mylist {2,100}; // two ints with a value of 100mylist.push_front (200);mylist.push_front (300);cout mylist contains:;for (listint::iterator itmylist.begin(); it!mylist.end(); it)std::cout *it;cout \n;return 0;
}
// output
mylist contains: 300 200 2 100有序映射map
有序映射的特征
map是关联容器它按照特定的顺序存储由键值和映射值组合形成的元素。
在map中键值通常用于对元素进行排序和唯一标识而映射值则存储与该键关联的内容。键和映射值的类型可能不同按照成员类型 value_type组合在一起。
typedef pairconst Key, T value_type;在内部map 中的元素始终按其键排序遵循其内部比较对象Compare 类型指示的特定严格弱排序标准。
通过键访问各个元素时map 容器通常比 unordered_map 容器慢但它们允许根据子集的顺序直接迭代。
可以使用括号运算符 ((operator[]) 通过相应的键直接访问映射中的映射值。
通常使用二叉搜索树实现map 。
应用实列
使用key_comp排序。
#include iostream
#include map
#include string
#include functional
#include algorithmusing namespace std;void print_map(const mapstring, int, greaterstring m)
{for (const auto v : m)std::cout [ v.first ] v.second ; ;std::cout \n;
}int main()
{mapstring, int, greaterstring m{{CPU, 10}, {GPU, 15}, {RAM, 20}};print_map(m);m[CPU] 25; m[SSD] 30;print_map(m);m.erase(GPU);print_map( m);
}
// output
[RAM] 20; [GPU] 15; [CPU] 10;
[SSD] 30; [RAM] 20; [GPU] 15; [CPU] 25;
[SSD] 30; [RAM] 20; [CPU] 25;队列queue
队列的特征
queue是一种容器适配器专门设计用于在 FIFO 上下文先进先出中操作其中元素被插入到容器的一端并从另一端提取。
queue被实现为容器适配器它们是使用特定容器类的封装对象作为其底层容器的类提供一组特定的成员函数来访问其元素。元素被推入特定容器的“后面”并从其“前面”弹出。
底层容器可以是标准容器类模板之一或一些其他专门设计的容器类。该底层容器至少应支持以下操作
empty
size
front
back
push_back
pop_front标准容器类 deque 和 list 满足这些要求。默认情况下如果没有为特定队列类实例化指定容器类则使用标准容器 deque。
应用实列
#include iostream
#include array
#include queue using namespace std;int main ()
{arrayint, 5 arr {1,2,3,4,5};queueint myqueue;int myint;for (auto x : arr)myqueue.push (x);cout myqueue contains: ;while (!myqueue.empty()){cout myqueue.front();myqueue.pop();}cout \n;return 0;
}myqueue contains: 1 2 3 4 5priority_queue
priority_queue是一种容器适配器经过专门设计根据某些严格的弱排序标准其第一个元素始终是其包含的最大元素。
此上下文类似于堆可以随时插入元素并且只能检索最大堆元素优先级队列中位于顶部的元素。
priority_queue被实现为容器适配器它们是使用特定容器类的封装对象作为其底层容器的类提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”弹出即优先级队列的顶部。
底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。容器应可通过随机访问迭代器进行访问并支持以下操作
empty()
size()
front()
push_back()
pop_back()标准容器类vector和deque满足这些要求。默认情况下如果没有为特定priority_queue类实例化指定容器类则使用标准容器vector。
需要随机访问迭代器的支持才能始终在内部保留堆结构。这是由容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 自动完成的。
应用实列
下面展示一些 内联代码片。
#include iostream
#include array
#include queue using namespace std;templatetypename T
void pop_println(string rem, T pq)
{cout rem : ;for (; !pq.empty(); pq.pop())cout pq.top() ;cout endl;
}int main()
{const auto data {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};priority_queueint max_priority_queue;for (int n : data)max_priority_queue.push(n);pop_println(max_priority_queue, max_priority_queue);priority_queueint, vectorint, greaterintmin_priority_queue1(data.begin(), data.end());pop_println(min_priority_queue1, min_priority_queue1);struct customLess{bool operator()(int l, int r) const { return l r; }};priority_queueint, vectorint, customLess custom_priority_queue;for (int n : data)custom_priority_queue.push(n); pop_println(custom_priority_queue, custom_priority_queue);priority_queueint, vectorint, greaterint priority_queue;for (int n : data)priority_queue.push(n); pop_println(priority_queue, priority_queue);
}// output
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
priority_queue: 0 1 2 3 4 5 6 7 8 9集合set
集合的特征
set是按照特定顺序存储唯一元素的容器。
在set中元素的值也标识它值本身就是键并且每个值必须是唯一的。集合中元素的值一旦在容器中就无法修改元素始终是常量但可以将它们插入容器或从容器中删除。
在内部set中的元素始终按照其内部比较对象Compare 类型指示的特定严格弱排序标准进行排序。
通过键访问元素set 容器通常比 unordered_set 慢但set允许根据子集的顺序直接迭代。
通常使用二叉搜索树实现set。
应用实列 #include iostream
#include setusing namespace std;struct FatKey
{int x;int data[1000];
};struct customComp
{bool operator()(FatKey r, FatKey l){return (r.x l.x);}
};int main()
{setint example{1, 2, 3, 4};for ( auto x : example)cout x , ;coutendl;auto search example.find(2);if (search ! example.end())cout Found (*search) \n;elsecout Not found\n;setFatKey, customComp example2{{1, {}}, {2, {}}, {3, {}}, {4, {}}};for ( auto x : example2)cout x.x , ;coutendl;FatKey lk {3};auto s2 example2.find(lk); if (s2 ! example2.end())std::cout Found s2-x \n;elsestd::cout Not found\n;
}// output
1, 2, 3, 4,
Found 2
4, 3, 2, 1,
Found 3堆栈stack
堆栈的特征
stack是一种容器适配器专门设计用于在 LIFO 上下文后进先出中操作其中仅从容器的一端插入和提取元素。
stack被实现为容器适配器它们是使用特定容器类的封装对象作为其底层容器的类提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”称为堆栈顶部推送/弹出。
底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。容器应支持以下操作
empty
size
back
push_back
pop_back标准容器类向量、双端队列和列表满足这些要求。默认情况下如果没有为特定堆栈类实例化指定容器类则使用标准容器双端队列。
应用实列
#include iostream // std::cout
#include stack // std::stackusing namespace std;int main ()
{stackint mystack;for (int i0; i5; i) mystack.push(i);cout Popping out elements...;while (!mystack.empty()){cout mystack.top();mystack.pop();}cout endl;return 0;
}// output
Popping out elements... 4 3 2 1 0无序映射unordered_map
无序映射的特征
无序映射是关联容器用于存储由键值和映射值组合形成的元素并且允许基于键快速检索各个元素。
在unordered_map中键值通常用于唯一标识元素而映射值是一个对象其内容与该键相关联。键和映射值的类型可能不同。
在内部unordered_map 中的元素不会按照其键或映射值以任何特定顺序排序而是根据其哈希值组织到存储桶中以允许直接通过其键值使用常量快速访问各个元素平均时间复杂度。
unordered_map 容器通过键访问各个元素比 map 容器更快尽管它们通常在通过其元素子集进行范围迭代时效率较低。
无序映射实现直接访问运算符operator[]它允许使用其键值作为参数直接访问映射值。
容器中的迭代器至少是前向迭代器。
应用实列
#include iostream
#include string
#include unordered_mapusing namespace std;int main()
{// Create an unordered_map of three strings (that map to strings)unordered_mapstring, string u {{RED, #FF0000},{GREEN, #00FF00},{BLUE, #0000FF}};// Helper lambda function to print key-value pairsauto print_key_value [](const auto key, const auto value){cout Key:[ key ] Value:[ value ]\n;};for (const pairconst string, string n : u)print_key_value(n.first, n.second);cout \n;// Add two new entries to the unordered_mapu[BLACK] #000000;u[WHITE] #FFFFFF;for (const auto n : u)print_key_value(n.first, n.second);
}
// output
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]Key:[WHITE] Value:[#FFFFFF]
Key:[BLACK] Value:[#000000]
Key:[RED] Value:[#FF0000]
Key:[GREEN] Value:[#00FF00]
Key:[BLUE] Value:[#0000FF]无序集合unordered_set
无序集合的特征
无序集是不按特定顺序存储唯一元素的容器并且允许根据单个元素的值快速检索各个元素。
在 unordered_set 中元素的值同时也是其唯一标识它的键。键是不可变的因此unordered_set 中的元素一旦进入容器就无法修改, 但它们可以插入和删除。
在内部unordered_set 中的元素不按任何特定顺序排序而是根据其哈希值组织到存储桶中以允许直接通过其值快速访问各个元素平均时间复杂度恒定。
通过键访问各个元素, unordered_set 容器比 set 容器更快尽管它们通常在通过其元素子集进行范围迭代时效率较低。
容器中的迭代器至少是前向迭代器。
应用实列
#include iostream
#include unordered_setusing namespace std;void print(const unordered_setint set)
{for (const auto elem : set)cout elem ;cout \n;
}int main()
{unordered_setint mySet{2, 7, 1, 8, 2, 8}; // initializingprint(mySet);mySet.insert(5); // puts an element 5 in the setprint(mySet);auto iter mySet.find(5); if (iter ! mySet.end())mySet.erase(iter); // removes an element pointed to by iterprint(mySet);mySet.erase(7); // removes an element 7print(mySet);
}// ourput
8 1 7 2
5 8 1 7 2
8 1 7 2
8 1 2向量vector
向量的特征
向量是表示大小可以更改的数组的序列容器。
就像数组一样向量对其元素使用连续的存储位置这意味着, 可以使用指向其元素的常规指针上的偏移量来访问其元素并且与数组中一样高效。但与数组不同的是它们的大小可以动态变化其存储由容器自动处理。
在内部向量使用动态分配的数组来存储其元素。当插入新元素时可能需要重新分配该数组, 以便增加大小这意味着分配一个新数组, 并将所有元素移动到其中。就处理时间而言这是一项相对昂贵的任务因此每次将元素添加到容器时向量不会重新分配。
相反向量容器可以分配一些额外的存储, 来适应可能的增长因此容器的实际容量可能大于包含其元素严格需要的存储即其大小。库可以实施不同的增长策略以平衡内存使用和重新分配之间的平衡但在任何情况下重新分配只能以对数增长的大小间隔进行以便可以为向量末尾的各个元素的插入提供常量时间复杂性。
因此与数组相比向量消耗更多的内存来换取管理存储和以高效方式动态增长的能力。
与其他动态序列容器双端队列、列表和前向列表相比向量可以非常高效地访问其元素就像数组一样并且从其末尾添加或删除元素也相对高效。对于涉及在末尾以外的位置插入或删除元素的操作它们的性能比其他操作更差并且迭代器和引用的一致性不如列表和前向列表。
应用实列
#include iostream
#include vectorusing namespace std;int main()
{vectorint v {8, 4, 5, 9};v.push_back(6);v.push_back(9);v[2] -1;for (int n : v)cout n ;cout endl;
}// output
8 4 -1 9 6 9
