C++ STL 自整理_C_内存溢出

该文章属于自整理整合，参考了多个作者，少部分是通过自我理解，只是为了自我方便查找函数使用而整合起来。这文章一直只存在于我自己的电脑中，如今发出来没有别的意思。文章末尾有多个作者的原文链接。

查找某个函数的描述或者使用方法请使用快捷键Ctrl+F C++ Standard Template Library

STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

若要细分，则还拥有仿函数、适配器、分配器（空间配置器）

C++ Iterators

迭代器（iterator）有时又称光标（cursor）是程序设计的软件设计模式，可在容器对象（container，例如链表或数组）上遍访的接口，设计人员无需关心容器对象的内存分配的实现细节。

有点像指针，我们目前就认为他的作用为指针即可。

迭代器本身是一种抽象的设计概念，设计思想关键在于：将容器和算法分开，彼此独立设计，最后再用一中粘合剂将他们联系起来。从技术角度来看，迭代器是其中最难实现的技术。（就好比怎么把Java和数据库联系起来）

分类：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器（功能最强）。

C++ Algorithms

主要的头文件有、、

是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历 *** 作、复制、修改、移除、反转、排序、合并等等。

体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些 *** 作。

中则定义了一些模板类，用以声明函数对象。

如果要使用C++11的功能，需要加上-std=c++11这段代码

STL中算法大致分为四类：

可变序列算法：指可以修改它们所 *** 作的容器内容的算法。（拷贝、替换、删除等等）
非可变序列算法：指不直接修改其所 *** 作的容器内容的算法。（查找、计数、遍历、寻找极值等等）
排序算法：对序列进行排序和合并的算法、搜索算法以及有序序列上的集合 *** 作。
数值算法：对容器内容进行数值计算。

<一>查找算法(13个)：判断容器中是否包含某个值

adjacent_find:在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的ForwardIterator。否则返回last。重载版本使用输入的二元 *** 作符代替相等的判断。
binary_search: 在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。
count:利用等于 *** 作符，把标志范围内的元素与输入值比较，返回相等元素个数。
count_if:利用输入的 *** 作符，对标志范围内的元素进行 *** 作，返回结果为true的个数。
equal_range:功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound。
find:利用底层元素的等于 *** 作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个InputIterator。
find_end:在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator，否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的 *** 作符代替等于 *** 作。
find_first_of:在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义 *** 作符。
find_if:使用输入的函数代替等于 *** 作符执行find。
lower_bound:返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较 *** 作。
upper_bound:返回一个ForwardIterator，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较 *** 作。
search:给出两个范围，返回一个ForwardIterator，查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1。重载版本使用自定义的比较 *** 作。
search_n:在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较 *** 作。

<二>排序和通用算法(14个)：提供元素排序策略
inplace_merge:合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的 *** 作进行排序。
merge:合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。
nth_element:将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较 *** 作。
partial_sort:对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较 *** 作。
partial_sort_copy:与partial_sort类似，不过将经过排序的序列复制到另一个容器。
partition:对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前。
random_shuffle:对指定范围内的元素随机调整次序。重载版本输入一个随机数产生 *** 作。
reverse:将指定范围内元素重新反序排序。
reverse_copy:与reverse类似，不过将结果写入另一个容器。
rotate:将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素。
rotate_copy:与rotate类似，不过将结果写入另一个容器。
sort:以升序重新排列指定范围内的元素。重载版本使用自定义的比较 *** 作。
stable_sort:与sort类似，不过保留相等元素之间的顺序关系。
stable_partition:与partition类似，不过不保证保留容器中的相对顺序。

<三>删除和替换算法(15个)
copy:复制序列
copy_backward:与copy相同，不过元素是以相反顺序被拷贝。
iter_swap:交换两个ForwardIterator的值。
remove:删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数。
remove_copy:将所有不匹配元素复制到一个制定容器，返回OutputIterator指向被拷贝的末元素的下一个位置。
remove_if:删除指定范围内输入 *** 作结果为true的所有元素。
remove_copy_if:将所有不匹配元素拷贝到一个指定容器。
replace:将指定范围内所有等于vold的元素都用vnew代替。
replace_copy:与replace类似，不过将结果写入另一个容器。
replace_if:将指定范围内所有 *** 作结果为true的元素用新值代替。
replace_copy_if:与replace_if，不过将结果写入另一个容器。
swap:交换存储在两个对象中的值。
swap_range:将指定范围内的元素与另一个序列元素值进行交换。
unique:清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较 *** 作。
unique_copy:与unique类似，不过把结果输出到另一个容器。

<四>排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合

do
{
    
} while (next_permutation(a, a + n));

next_permutation:取出当前范围内的排列，并重新排序为下一个排列。重载版本使用自定义的比较 *** 作。
prev_permutation:取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较 *** 作。

<五>算术算法(4个)
accumulate:iterator对标识的序列段元素之和，加到一个由val指定的初始值上。重载版本不再做加法，而是传进来的二元 *** 作符被应用到元素上。
partial_sum:创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义 *** 作代替加法。
inner_product:对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的 *** 作。
adjacent_difference: 创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元 *** 作计算相邻元素的差。

<六>生成和异变算法(6个)

fill(v.begin(), v.end(), 1);

fill:将输入值赋给标志范围内的所有元素。
fill_n:将输入值赋给first到first+n范围内的所有元素。
for_each:用指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。该函数不得修改序列中的元素。
generate:连续调用输入的函数来填充指定的范围。
generate_n:与generate函数类似，填充从指定iterator开始的n个元素。

///大小写转换/
string strsrc("Hello, World!");
string strdest;
strdest.resize(strsrc.size());		// !!!必须预先设置一个大小与strsrc相同
transform(strsrc.begin(), strsrc.end(), strdest.begin(), to_upper);	// 转换为大写
cout << strdest << endl;

transform(strsrc.begin(), strsrc.end(), strdest.begin(), to_lower); // 转换为小写
cout << strdest << endl;

transform:将输入的 *** 作作用与指定范围内的每个元素，并产生一个新的序列。重载版本将 *** 作作用在一对元素上，另外一个元素来自输入的另外一个序列。结果输出到指定容器。

<七>关系算法(8个)

equal(v1.begin(), v1.end(), v2.begin())
equal(v1.begin() + 1, v1.end(), v2.begin())

equal:如果两个序列在标志范围内元素都相等，返回true。重载版本使用输入的 *** 作符代替默认的等于 *** 作符。
includes:判断第一个指定范围内的所有元素是否都被第二个范围包含，使用底层元素的<操作符，成功返回true。重载版本使用用户输入的函数。
lexicographical_compare:比较两个序列。重载版本使用用户自定义比较 *** 作。
max:返回两个元素中较大一个。重载版本使用自定义比较 *** 作。

cout << *max_element(v1.begin(), v1.end());

max_element:返回一个ForwardIterator，指出序列中最大的元素。重载版本使用自定义比较 *** 作。
min:返回两个元素中较小一个。重载版本使用自定义比较 *** 作。
min_element:返回一个ForwardIterator，指出序列中最小的元素。重载版本使用自定义比较 *** 作。
mismatch:并行比较两个序列，指出第一个不匹配的位置，返回一对iterator，标志第一个不匹配元素位置。如果都匹配，返回每个容器的last。重载版本使用自定义的比较 *** 作。

<八>集合算法(4个)

set_union(A.begin(),A.end(),B.begin(),B.end(),inserter( C1 , C1.begin() ) );

set_union:构造一个有序序列，包含两个序列中所有的不重复元素。重载版本使用自定义的比较 *** 作。
set_intersection:构造一个有序序列，其中元素在两个序列中都存在。重载版本使用自定义的比较 *** 作。
set_difference:构造一个有序序列，该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较 *** 作。
set_symmetric_difference:构造一个有序序列，该序列取两个序列的对称差集(并集-交集)。

<九>堆算法(4个)
make_heap:把指定范围内的元素生成一个堆。重载版本使用自定义比较 *** 作。
pop_heap:并不真正把最大元素从堆中d出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"d出"的元素或者使用pop_back进行真正的删除。重载版本使用自定义的比较 *** 作。
push_heap:假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较 *** 作。
sort_heap:对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较 *** 作。

C++ Container C++ String

基本概念：C语言风格字符串（以空字符结尾的字符数组）太过复杂难以掌握，不适合大程序的开发，所以STL定义了一种string类，定义在头文件

string 和 C语言风格的字符串对比：

Char 是一个指针，String 是一个类
string 封装了 char ，管理这个字符串，是一个 char 型的容器。
String 封装了很多实用的成员函数
查找 find，拷贝 copy，删除 delete 替换 replace，插入 insert
不用考虑内存释放和越界
string 管理 char* 所分配的内存。每一次 string 的复制，取值都由 string 类负责维护，不用担心复制越界和取值越界等。

string构造函数

string();//创建一个空的字符串 例如: string str;      
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化

string基本赋值 *** 作

string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串

string存取字符 *** 作

char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符

string拼接 *** 作

string& operator+=(const string& str);//重载+= *** 作符
string& operator+=(const char* str);//重载+= *** 作符
string& operator+=(const char c);//重载+= *** 作符
string& append(const char *s);//把字符串s连接到当前字符串结尾
string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s);//同operator+=()
string& append(const string &s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加n个字符c

string查找和替换

int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

string比较 *** 作

/*
compare函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的A比小写的a小。
*/
int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较

string子串

string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串

string插入和删除 *** 作

string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符

string和c-style字符串转换

//string 转 char*
string str = "it";
const char* cstr = str.c_str();
//char* 转 string 
char* s = "it";
string str(s);

C++ Vector vector构造函数

vector v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将n个elem拷贝给本身。
vector(const vector &vec);//拷贝构造函数。

vector常用的赋值 *** 作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector  &vec);//重载等号 *** 作符
swap(vec);// 将vec与本身的元素互换。

vector大小 *** 作

size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

vector数据存取 *** 作

at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

vector插入和删除 *** 作

insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

C++ Stack stack构造函数

stack stkT;//stack采用模板类实现， stack对象的默认构造形式： 
stack(const stack &stk);//拷贝构造函数

stack赋值 *** 作

stack& operator=(const stack &stk);//重载等号 *** 作符

stack数据存取 *** 作

push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

stack大小 *** 作

empty();//判断堆栈是否为空
size();//返回堆栈的大小

括号匹配问题

#include 
#include 

using namespace std;

stack op;

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '<' || s[i] == '(' || s[i] == '{' || s[i] == '[')
            op.push(s[i]);
        else
        {
            if (op.empty())
            {
                cout << "no";
                return 0;
            }
            if (s[i] == '>')
            {
                if (op.top() == '<')
                    op.pop();
                else
                {
                    cout << "no" << endl;
                    return 0;
                }
            }
            if (s[i] == ')')
            {
                if (op.top() == '(')
                    op.pop();
                else
                {
                    cout << "no" << endl;
                    return 0;
                }
            }
            if (s[i] == '}')
            {
                if (op.top() == '{')
                    op.pop();
                else
                {
                    cout << "no" << endl;
                    return 0;
                }
            }
            if (s[i] == ']')
            {
                if (op.top() == '[')
                    op.pop();
                else
                {
                    cout << "no" << endl;
                    return 0;
                }
            }
        }
    }

    cout << "yes" << endl;
    return 0;
}

C++ Queue/Deque queue构造函数

queue queT;//queue采用模板类实现，queue对象的默认构造形式：
queue(const queue &que);//拷贝构造函数

queue存取、插入和删除 *** 作

push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

deque存取、插入和删除 *** 作

deq[];//用来访问双向队列中单个的元素。
front();//返回第一个元素的引用。
back();//返回最后一个元素的引用。
push_front(elem)//把元素elem插入到双向队列的头部。
pop_front()//d出双向队列的第一个元素。
push_back(elem)//把元素elem插入到双向队列的尾部。
pop_back()//d出双向队列的最后一个元素。

queue赋值 *** 作

queue& operator=(const queue &que);//重载等号 *** 作符

queue大小 *** 作

empty();//判断队列是否为空
size();//返回队列的大小

优先队列

定义：priority_queue

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

//升序队列
priority_queue ,greater > q;
//降序队列
priority_queue ,less >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

基本类型例子：

#include
#include 
using namespace std;
int main() 
{
    //对于基础类型 默认是大顶堆
    priority_queue a; 
    //等同于 priority_queue, less > a;
    
  
    priority_queue, greater > c;  //这样就是小顶堆
    priority_queue b;

    for (int i = 0; i < 5; i++) 
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty()) 
    {
        cout << a.top() << ' ';
        a.pop();
    } 
    cout << endl;

    while (!c.empty()) 
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty()) 
    {
        cout << b.top() << ' ';
        b.pop();
    } 
    cout << endl;
    return 0;
}

pair的比较，先比较第一个元素，第一个相等比较第二个

#include 
#include 
#include 
using namespace std;
int main() 
{
    priority_queue > a;
    pair b(1, 2);
    pair c(1, 3);
    pair d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

对于自定义类型

#include 
#include 
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

C++ List list构造函数

list lstT;//list采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。

list数据元素插入和删除 *** 作

push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。

list大小 *** 作

size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

list赋值 *** 作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号 *** 作符
swap(lst);//将lst与本身的元素互换。

list数据的存取

front();//返回第一个元素。
back();//返回最后一个元素。

list反转排序

reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序

C++ Set/MultiSet

我们不可以通过set的迭代器改变set元素的值，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator。

multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树。

set构造函数

set st;//set默认构造函数：
mulitset mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数

set赋值 *** 作

set& operator=(const set &st);//重载等号 *** 作符
swap(st);//交换两个集合容器

set大小 *** 作

size();//返回容器中元素的数目
empty();//判断容器是否为空

set插入和删除 *** 作

insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。

set查找 *** 作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key<=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

重新指定set排序规则（运用仿函数）

//插入 *** 作返回值
void test01(){

	set s;
	pair::iterator,bool> ret = s.insert(10);
	if (ret.second){
		cout << "插入成功:" << *ret.first << endl;
	}
	else{
		cout << "插入失败:" << *ret.first << endl;
	}
	
	ret = s.insert(10);
	if(ret.second){
		cout << "插入成功:" << *ret.first << endl;
	}
	else{
		cout << "插入失败:" << *ret.first << endl;
	}

}

struct MyCompare02{
	bool operator()(int v1,int v2){
		return v1 > v2;
	}
};

//set从大到小
void test02(){

	srand((unsigned int)time(NULL));
	//我们发现set容器的第二个模板参数可以设置排序规则，默认规则是less<_Kty>
	set s;
	for (int i = 0; i < 10;i++){
		s.insert(rand() % 100);
	}
	
	for (set::iterator it = s.begin(); it != s.end(); it ++){
		cout << *it << " ";
	}
	cout << endl;
}

//set容器中存放对象
class Person{
public:
	Person(string name,int age){
		this->mName = name;
		this->mAge = age;
	}
public:
	string mName;
	int mAge;
};


struct MyCompare03{
	bool operator()(const Person& p1,const Person& p2){
		return p1.mAge > p2.mAge;
	}
};

void test03(){

	set s;

	Person p1("aaa", 20);
	Person p2("bbb", 30);
	Person p3("ccc", 40);
	Person p4("ddd", 50);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for (set::iterator it = s.begin(); it != s.end(); it++){
		cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
	}

}

C++ Map/MultiMap

map支持[]运算符，multimap不支持[]运算符

对组（pair）

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。

创建对组：

//第一种方法创建一个对组
pair pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值
//第二种
pair pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair=赋值
pair pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;

map构造函数

map mapTT;//map默认构造函数: 
map(const map &mp);//拷贝构造函数

map赋值 *** 作

map& operator=(const map &mp);//重载等号 *** 作符
swap(mp);//交换两个集合容器

map大小 *** 作

size();//返回容器中元素的数目
empty();//判断容器是否为空

map插入数据元素 *** 作

map.insert(...); //往容器插入元素，返回pair
map mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.insert(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

map删除 *** 作

clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。

map查找 *** 作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

重新指定map排序规则

#include   
#include   
#include   
using namespace std;
 
typedef struct tagStudentinfo
{
	int      niD;
	string   strName;
	bool operator < (tagStudentinfo const& _A) const
	{     //这个函数指定排序策略，按niD排序，如果niD相等的话，按strName排序  
		if (niD < _A.niD) return true;
		if (niD == _A.niD)
			return strName.compare(_A.strName) < 0;
		return false;
	}
}Studentinfo, *PStudentinfo; //学生信息  
 
int main()
{
	int nSize;   //用学生信息映射分数  
	mapmapStudent;
	map::iterator iter;
	Studentinfo studentinfo;
	studentinfo.niD = 1;
	studentinfo.strName = "student_one";
	mapStudent.insert(pair(studentinfo, 90));
	studentinfo.niD = 2;
	studentinfo.strName = "student_two";
	mapStudent.insert(pair(studentinfo, 80));
	for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
		cout << iter->first.niD << ' ' << iter->first.strName << ' ' << iter->second << endl;
	return 0;
}

C++ 11 新增容器