容器本质的作用是对数据进行存储，学习容器的关键是掌握各种容器的特点及其对数据的增删改查的操作方法。
STL的一个重要特点是数据结构和算法的分离。算法是用来操作容器中的数据的模板函数，函数本身与他们操作的数据的结构和类型无关。
一些常用算法
1、概述
算法不直接操作容器，也不依赖于具体的容器，只会运行于迭代器之上。
大多数算法的头文件定义在 algorithm 中。
2、常用算法
容器应用举例
1、LRU缓存机制
- 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) – 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。写入数据 put(key, value) – 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作？来源：力扣（LeetCode）第146道题
- 题目分析
O(1)的时间查询数据选择map；O(1)的时间插入\删除数据选择list。创建键-值map用于查询数据，保存为key和list中的迭代器对应关系；创建n个list用于保存相同频率的节点，可以快速的插入和删除数据。
- 代码示例
struct Node{ int key; int value; Node(int m_key,int m_value):key(m_key),value(m_value){}};class LRUCache {public: unordered_map<int,list<Node>::iterator> key_map;//k-v键值对 list<Node> nodelist; int m_capatity = 0; LRUCache(int capacity) { m_capatity = capacity; nodelist.clear(); key_map.clear(); } int get(int key) { if( m_capatity == 0) return -1; if( key_map.find(key) == key_map.end()) return -1; else { list<Node>::iterator node = key_map[key] ; int val = node->value; nodelist.erase(node);//先删除 nodelist.push_front(Node(key,val));//插入到list开头 key_map[key] = nodelist.begin(); return val; } } void put(int key, int value) { if( m_capatity == 0) return ; if( key_map.find(key) != key_map.end()) { list<Node>::iterator node = key_map[key]; nodelist.erase(node); nodelist.push_front(Node(key,value)); key_map[key] = nodelist.begin(); } else { if( key_map.size() == m_capatity) { key_map.erase(nodelist.back().key ); nodelist.pop_back(); } nodelist.push_front(Node(key,value)); key_map[key] = nodelist.begin(); } }};/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */2、LFU缓存
- 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。get(key) – 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。put(key, value) – 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。进阶：你是否可以在 O(1) 时间复杂度内执行两项操作？来源：力扣（LeetCode）第460道题
- 题目分析
O(1)的时间查询数据选择map；O(1)的时间插入\删除数据选择list。创建键-值map用于查询数据，保存为key和list中的迭代器对应关系；创建list保存节点，用于快速的插入和删除数据，当前节点更新时删除节点，然后在list开头插入新节点。
- 代码示例
struct Node// 双向链表list中的节点 { int key,val,freq; Node(int m_key,int m_val,int m_freq):key(m_key),val(m_val),freq(m_freq){}};class LFUCache { int minfreq,m_cpacity; unordered_map<int,list<Node>::iterator> key_table;// key-list中指针 unordered_map<int,list<Node>> freq_table;//频率-listpublic: LFUCache(int capacity) { minfreq = 0; m_cpacity = capacity; key_table.clear(); freq_table.clear(); } int get(int key) { if( m_cpacity == 0) return -1; if( key_table.find(key) == key_table.end()) { return -1; } list<Node>::iterator node = key_table[key];//找到节点 int val = node->val,freq = node->freq; freq_table[freq].erase(node);//从频率为freq的list中删除node if( freq_table[freq].size() == 0) { freq_table.erase(freq); if( minfreq == freq) minfreq++; } freq_table[freq+1].push_front(Node(key,val,freq+1));//插入到freq 链表头部 key_table[key] = freq_table[freq+1].begin();//更新k-v map return val; } void put(int key, int value) { if( m_cpacity == 0) return ; if( key_table.find(key) != key_table.end()) //key 已存在 { list<Node>::iterator node = key_table[key]; int val = node->val,freq = node->freq; freq_table[freq].erase(node); if( freq_table[freq].size() == 0) { freq_table.erase(freq); if( minfreq == freq) minfreq++; } freq_table[freq+1].push_front(Node(key,value,freq+1)); key_table[key] = freq_table[freq+1].begin(); } else //key 不存在 { if( key_table.size() == m_cpacity)//缓存已满 { auto node = freq_table[minfreq].back(); key_table.erase(node.key);//删除节点 freq_table[minfreq].pop_back();//删除尾节点 if( freq_table[minfreq].size() == 0) freq_table.erase(minfreq); } freq_table[1].push_front(Node(key,value,1)); key_table[key] = freq_table[1].begin(); minfreq = 1; } }};
/** * Your LFUCache object will be instantiated and called as such: * LFUCache* obj = new LFUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
