容器大全 - CSDN


Java容器大全
一、集合框架
二、Iterator
题外话
1. C++中的Reference与Pointer
2. 内存分析
三、Array、Arrays与ArrayList
四、HashMap
1. 概念
2. 用法
五、Set、List与Array之间的互转
1. Set与List互转
2. Array与List互转
3. Array与Set互转

一、集合框架
Java集合框架（java.util包）主要包括两种类型的容器：一种是集合Collection，存储一个元素集合；另一种是图Map，存储键值对映射。

所有的集合框架都包含：接口、实现（类）、算法。任何对象加入集合类后，自动转变为Object类型，所以在取出的时候，需要进行强制类型转换。




接口

Collection：最基本的集合接口，代表一组Object

List：有序，add()方法添加

Set：不重复，add()方法添加

SortedSet：有序不重复

Map：键值对，put()方法添加

Map.Entry：Map中的一个元素，Map的内部类

SortedMap：key有序

Enumeration：枚举


实现类

分为具体类（直接拿来用）和抽象类（提供了接口的部分实现）。

LinkedList：允许有null，用于创建链表

ArrayList：可变大小的数组

HashSet：允许包含最多一个null，只存储对象

LinkedHashSet：具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现

HashMap：散列表，最多允许一条键为null的记录

LinkedHashMap：使用元素自然顺序进行排列
Vector：与ArrayList类似，是同步的

Stack：是Vector的一个子类，栈

Dictionary：抽象类，存储键值对

Hashtable：Dictionary类的子类，是同步的，不能存null

Properties：继承于Hashtable，表示一个持久的属性值，键值都是String

BitSet：存储位值得数组


方法


boolean add(Object o)            //添加对象到集合
boolean remove(Object o)         //删除指定的对象
int size()                       //返回当前集合中元素的数量
boolean contains(Object o)       //查找集合中是否有指定的对象
boolean isEmpty()                //判断集合是否为空
Iterator iterator()              //返回一个迭代器
boolean containsAll(Collection c)//查找集合中是否有集合c中的元素
boolean addAll(Collection c)     //将集合c中所有的元素添加给该集合
void clear()                     //删除集合中所有元素
void removeAll(Collection c)     //从集合中删除c集合中也有的元素
void retainAll(Collection c)     //从集合中删除集合c中不包含的元素





二、Iterator
Collection是个接口，你的类继承这个接口必须实现这个接口里面的所有函数，其中就包括Iterator< E> iterator()这个函数。

迭代器是一种设计模式，是一个标准化遍历各类容器里面的所有对象的方法类，可以遍历并选择序列中的对象而不用关心底层结构。Java中的Iterator功能较为简单，只能单项移动。（ListIterator可以双向遍历，更为灵活）

接口定义：
public interface Iterator {  
　　boolean hasNext();  
　　Object next();  
　　void remove();  
}
//用法，以List为例
Iterator iter = list.iterator();





题外话
1. C++中的Reference与Pointer
int  i  = 1;
int *pi = &i;//i是一个指针类型的对象，并且也是一个“指向int整型的指针”，它的初始化值为对象i的地址
int &ri = i; //i是一个引用类型的对象，并且也是一个指向整型的引用，它指向的是i
//赋初值
*pi = 1;//后续可以指向其他不同的对象，可以为null
ri  = 1;//后续不可以改变，类似于常量指针，有意义必须要指向一个对象

二者的区别（参考《More Effective C++》）

1.没有null reference；

2.reference必须有初值；

3.使用reference要比使用指针效率高。因为reference不需要测试其有效性；

4.指针可以重新赋值，而reference总是指向它最初获得的对象。
Java中的Reference

Java中的引用可以随意赋值，并且可以为null，可以理解成一个披着C++中reference的pointer。实际上，Java中的reference就是一个地址，地位等同于C++中的point。
2. 内存分析

栈

1.描述的是方法执行的内存模型，每个方法被调用都会创建一个栈帧（存储局部变量、操作数、方法出口等）；

2.JVM为每个线程创建一个栈，用于存放该线程执行方法的信息（实际参数、局部变量等）；

3.栈属于线程私有，不能实现线程间的共享；

4.栈的存储特性是“先进后出”，由系统自动分配，速度快，是一片连续的内存空间。
堆

1.用于存储创建好的对象和数组；

2.JVM只有一个堆，被所有线程共享；

3.堆是一个不连续的内存空间，分配灵活，速度慢。
方法区（静态区）

1.JVM只有一个方法区，实际上也是堆，被所有线程共享，存放类、常量相关的信息；

2.用来存放程序中永远不变或唯一的内容（类信息、静态变量、字符串常量等）。






三、Array、Arrays与ArrayList
Array是对象数组的类（对象的reference）与基本类型数组非常类似，大小固定，可以存储基本数据类型和对象，Array还可以作为函数返回值。

Arrays是对数组的一系列操作，是工具类java.util.Arrays。

ArrayList是一个容器（一个个reference指向Object），只能存储对象，不能存储原生数据类型（上一篇博客中讨论过，如int）。java.util.ArrayList< E>长度是动态的，可以存储任意多个对象（泛型固定的类型），牺牲了效率，可以视为Array的二次封装。
分析：当能确定长度并且数据类型一致的时候就可以用数组，其他时候使用ArrayList。

List是一个接口，而ArrayList是其实现类，List无法被直接构造（new），但是可以通过List list = new ArrayList()来构造。




四、HashMap
1. 概念
HashMap继承于AbstractMap，基于散列表，实现了Map、Cloneable、java.io.Serializable接口。存储的内容是键值对映射，利用拉链法实现。其实现是不同步的，即非线程安全，key和value都可以是null。此外，HashMap中的映射不是有序的。
影响HashMap的实例有两个参数：初始容量和加载因子。

通常默认加载因子是0.75，当哈希表中的条目超过了加载因子与初始容量的乘积时，就要对该哈希表进行rehash操作，重建内部数据结构，使哈希表大约有两倍的桶数。
TreeMap基于红黑树实现的，内部元素是按需排列的。
2. 用法
构造函数：
// 默认构造函数。
HashMap()

// 指定“容量大小”的构造函数
HashMap(int capacity)

// 指定“容量大小”和“加载因子”的构造函数
HashMap(int capacity, float loadFactor)

// 包含“子Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)

API：
void                clear()                                  //清空表
Object              clone()
boolean             containsKey(Object key)                  //判断是否包含键为key的键值对
boolean             containsValue(Object value)              //判断是否包含值为value的键值对
V                   get(Object key)                          //获取key对应的value
boolean             isEmpty()                                //判断是否为空
V                   put(K key, V value)                      //添加一个映射
void                putAll(Map<? extends K, ? extends V> map)//将map所有的元素加入到表中
V                   remove(Object key)                       //删除键为key的元素
int                 size()                                   //获得表大小

Set<Entry<K, V>>    entrySet()                               //返回所有Entry的集合
Set<K>              keySet()                                 //返回所有key的集合
Collection<V>       values()                                 //返回所有value的集合

遍历方式：
//遍历键值对
Iterator iter = hashMap.entrySet().iterator();
while (iterator.hasNext()){
	Map.Entry entry = (Map.Entry) iter.next();
    String key = (String) entry.getKey();
    Integer value = (Integer) entry.getValue();
}

//遍历键
Iterator iter = hashMap.keySet().iterator();
key = (String) iter.next();
value = (Integer)hashMap.get(key);

//遍历值
Collection c = hashMap.values();
Iterator iter = c.iterator();
value = (Integer) iter.next();

HashMap与TreeMap的对比






五、Set、List与Array之间的互转
1. Set与List互转
因为List和Set都实现了Collection接口，且addAll(Collection<? extends E> c);方法，因此可以采用addAll()方法将List和Set互相转换；另外，List和Set也提供了Collection<? extends E> c作为参数的构造函数，因此通常采用构造函数的形式完成互相转化。
//List转Set
List<String> list = new ArrayList<>();
Set<String> set = new HashSet<>(list);

//Set转List
Set<String> set = new HashSet<>();
List<String> list_1 = new ArrayList<>(set);

注意：这里list与set相互独立，改变其中一个不会影响另一个。



2. Array与List互转
注意引用的情况。
//Array转List
String[] s = new String[]{"A", "B", "C", "D","E"};
List<String> list = Arrays.asList(s);//s改变会影响list
List<String> list = Arrays.asList(Arrays.copyOf(s, s.length));//s改变不会影响list

//List转Array
String[] s1 = list.toArray(new String[list.size()]);//new String[len]是指定返回数组的类型
String[] s1 = (String[]) list.toArray();//或者强转



3. Array与Set互转
由1、2可以推出：
//array转set
s = new String[]{"A", "B", "C", "D","E"};
Set<String> set = new HashSet<>(Arrays.asList(s));

//set转array
String[] s1= set.toArray(new String[0]);
String[] s1= (String[]) set.toArray();


总结：上述列出的互相转换离不开Arrays.asList()和Collection.toArray()两个重要的方法。需要注意的是asList()函数的参数必须是对象，如果是int[]，必须先转换成Integer[]。如果强行转换的话，需要用到jdk 1.8中的stream。
List<Integer> list = 
int[] i =

收起


STL容器
简介
STL有六大组件
STL初探
STL中的string
字符串的遍历
string的拼接
string的查找和替换
string区间删除和插入
string算法相关
STL中的vector容器
基本用法：
vector的初始化
vector的遍历
vector的push_back强化
vector的元素删除
vector的插入元素
STL中的deque容器
STL中的stack栈容器
复杂数据类型的stack
STL中的queue队列容器
STL中的list容器
list的删除
STL中的priority_queue优先级队列容器
STL中的set和multiset集合容器
普通数据类型的排序
创建集合的方式：
自定义对象的排序
pair类型的返回值
set容器数据的查找
STL中的map和multimap映射容器
map元素的查找
multimap容器
STL容器的通用性探究
STL容器的元素拷贝
STL容器的比较

简介
STL(标准模板库)，是目前C++内置支持的library。它的底层利用了C++类模板和函数模板的机制，由三大部分组成：容器、算法和迭代器。
STL有六大组件
容器 container
算法 algorthm
迭代器 iterator
仿函数 function object
适配器 adaptor
空间配置器 allocator
下面，我们会一一进行介绍。
STL初探
容器是STL中很重要的一种数据结构。常见的容器包括
vector容器
deque双端数组
stack栈模型
queue队列模型
list链表模型
priotriy_queue优先级队列
set与multiset容器
map与multimap容器
除了容器，STL还封装了强大的算法，能够实现查找、删除、替换、删除等很多常见操作。后面会重点讲解。
另外，迭代器也是STL重要的一环，通过迭代器，我们可以很方便对容器中的元素进行遍历，以及操作容器。后面我们会穿插讲解迭代器。
STL中的string
string是STL的字符串类型，在C语言中，我们通常用char *或者char[]字符数组来表示字符串。C++的string和C语言的char *有什么区别呢?
string是一个类，char *是指向字符的指针
string封装了char *,管理这个字符串，是一个char *类型的容器
string不用考虑内存释放和数组越界
string提供了一些列的字符串操作函数
string的构造函数
既然string是一个类，那么也就有构造函数，我们研究下string的构造函数。
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {

//通过const char * 初始化

string s1 = "aaaa";

//构造函数初始化

string s2("bbbbb");

//通过拷贝构造函数来初始化对象s3

string s3 = s2;

//用10个'a'字符来初始化字符串

string s4(10, 'a');

return 0;

}

字符串的遍历
字符串的遍历，有三种遍历的方式
数组方式遍历，通过[]操作符遍历 (不会抛出异常)
at()方法遍历，根据index取值 (会抛出异常)
通过STL迭代器遍历
int main(int argc, const char * argv[]) {

//创建字符串对象

string str("abcdefg");

//数组形式遍历

for (int i = 0; i < str.length(); i++) {

cout<< str[i] << endl;

}

//at方法遍历
for (int i = 0; i < str.length(); i++) {

cout << str.at(i) << endl;

}

//迭代器遍历
for (string::iterator it = str.begin(); it != str.end(); it++) {

cout << *it << endl;

}

return 0;

}

数组方式和at方法方式，有一个明显的不同
数组方式，如果出现越界或者其他错误，不会抛出异常，程序直接终端。
at()方法遍历，出现越界或其他错误，会抛出异常，程序可以处理异常。
迭代器其实可以看作是一个字符的指针，上个例子中string::iterator it = str.begin()就是定义一个string类型的迭代器，指向str的第一次位置。*it就表示当前的字符。注意str.end()表示字符串最后一个字符的后面一个位置。如果it == str.end()就表示已经遍历到终点了。
string与char *的转换
string提供了成员函数c_str来将string对象转化成const char *。string提供了copy(buf,size,begin)成员函数来讲string从begin位置开始的size个字符拷贝到buf中。需要注意的是:
如果buf容纳不下，会越界
拷贝过去后，不会转变成C风格的字符串，也就是不会在buf后面添加’\0’
int main(int argc, const char * argv[]) {

//1 string转char *

string str("aaaaaa");

const char *p = str.c_str();

//2 char *转string

const char *p1 = "12345";

string str2 = p1;

//3 string拷贝到buf[]中

char buf[128] = {0};

//从0开始，拷贝3个字符到buf指向的内存空间

//如果buf空间容纳不下，会越界

//拷贝过去时，不会给buf末尾添加\0

str.copy(buf, 3, 0);

return 0;

}

string的拼接
string为我们提供了两种字符串拼接方式，一种是重写了 + 操作符，我们可以直接将连个字符串相加，类似于java的语法。另一种是string提供了成员函数append()供我们拼接连个字符串.
int main(int argc, const char * argv[]) {

string s1 = "123456";

string s2 = "abcdef";

//直接使用加号运算符拼接

string s3 = s1 + s2;

//使用成员函数拼接

string s4 = s1.append(s2);

cout<<s3<<endl;

cout<<s4<<endl;

return 0;

}

string的查找和替换
string类提供了find函数，用来查找字符串中指定的字符。提供了replace函数，用来替换字符串中指定位置的字符串。
replace函数是，先删除指定位置，指定长度的字符，然后在当前指定位置插入新的字符。
int main(int argc, const char * argv[]) {

string s1 = "hello hello hello hello hello hello 1234 7876";

//从0位置开始查找第一个hello出现的首位位置

size_t index1 = s1.find("hello",0);

cout << index1 << endl;

//查找第一个hello出现时的首位位置

size_t index2 = s1.find_first_of("hello");

cout << index2 << endl;

//查找最后一个hello出现时的末尾位置

size_t index3 = s1.find_last_of("hello");

cout << index3 << endl;

//求hello出现的次数，以及对应的下标

int count = 0;

size_t offindex = s1.find("hello",0);

while (offindex != string::npos) { //如果 offindex != -1

//找到了

cout << "索引:" << offindex <<endl;

count++;

offindex++;

offindex = s1.find("hello", offindex);

}

//把hello替换成welcome

size_t offindex1 = s1.find("hello", 0);

while (offindex1 != string::npos) {

//从offindex1的位置开始删除5个位置，并插入新的字符串welcome

s1.replace(offindex1, strlen("hello"), "welcome");

//从后面的位置开始

offindex1 += strlen("welcome");

//继续查找

offindex1 = s1.find("hello", offindex1);

}

cout << "替换后的字符串：" << s1 <<endl;

return 0;

}

string区间删除和插入
string提供了insert和erase分别实现插入和删除操作。
插入：pos位置插入字符串s，返回新的string。
string &insert(int pos, const char *s)
string &insert(int pos, const string &s)
插入：pos位置插入n个字符c，返回string。
string &insert(int pos, int n, char c)
删除：删除从pos位置开始的n个字符，返回新的string
string &erase(int pos, int n)
删除：删除指定迭代器的位置，返回当前迭代器位置
string::iterator erase(string::iterator it)
删除：删除迭代器之间的字符，左闭右开区间
string::iterator erase(string::iterator beginIt, string::iterator endIt)
int main(int argc, const char * argv[]) {
string s1 = "hello1 world!";

//1 删除字符串中的'1'

//---通过find函数，查找'1'所在的迭代器位置

string::iterator it = find(s1.begin(), s1.end(), '1');

//---删除

if (it != s1.end()) {

s1.erase(it);

}

cout << s1 << endl;

//2 删除起始迭代器位置的字符

s1.erase(s1.begin(), s1.begin() + 3);

cout << s1 << endl;

//3 在0位置插入"AAA"

s1.insert(0, "AAA");

cout << s1 << endl;

return 0;

}

string算法相关
目前常见的string的算法是大小写转换。一般使用函数transform来进行转换。
int main(int argc, const char * argv[]) {

string s1 = "abcdefg";

string s2 = "AEDLFLKJDLKJFL";

//小写全部转换成大写,转换的结果放在s1.begin()的位置,后面的操作需要强制转换成指定的函数类型

transform(s1.begin(), s1.end(), s1.begin(), (int (*)(int))toupper);

cout << s1 <<endl;

//大写全部转换成小写

transform(s2.begin(), s2.end(), s2.begin(), (int (*)(int))tolower);

cout << s2 <<endl;

return 0;

}

STL中的vector容器
vector是将元素放到动态数组中加以管理的容器。vector容器可以随机存取元素，也就是说支持[]运算符和at方式存取。
vector在尾部添加或者移除元素非常快，在中间操作非常耗时，因为它需要移动元素
vector的基本用法
既然vector是容器，那么就可以向这个容器添加删除元素。
基本用法：
front()返回头部元素的引用，可以当左值
back()返回尾部元素的引用，可以当左值
push_back()添加元素，只能尾部添加
pop_back()移除元素，只能在尾部移除
int main(int argc, const char * argv[]) {

//定义一个vector容器

vector<int> v1;

//插入元素(尾部插入)

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

//迭代器遍历打印

for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {

cout << *it << " ";

}

cout << endl;

//修改头部元素的值(front()返回是引用，可以当左值)

v1.front() = 44;

//输出头部元素

cout<< "头部元素:" << v1.front() << endl;

//修改尾部的值(back()返回是引用，可以当左值)

v1.back() = 99;

//输出尾部元素

cout << "尾部元素" << v1.back() <<endl;

//删除元素(从尾部删除)

v1.pop_back();

//迭代器遍历打印

for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {

cout << *it << " ";

}

cout << endl;

return 0;

}

vector的初始化
vector有4种方式初始化，有直接初始化，也要通过拷贝构造函数初始化。
int main(int argc, const char * argv[]) {

//直接构造函数初始化

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

//通过拷贝构造函数初始化

vector<int> v2 = v1;

//使用部分元素来构造

vector<int> v3(v1.begin(), v1.begin() + 1);

vector<int> v4(v1.begin(), v1.end());

//存放三个元素，每个元素都是9

vector<int> v5(3,9);

return 0;

}

vector的遍历
vector的遍历有多种方式，可以根据[]或者迭代器遍历。
需要主要的是：
[]方式，如果越界或出现其他错误，不会抛出异常，可能会崩溃，可能数据随机出现
at方式，如果越界或出现其他错误，会抛出异常，需要捕获异常并处理
迭代器提供了逆向遍历，可以通过迭代器来实现逆向遍历，当然上面两种方式也可以
int main(int argc, const char * argv[]) {

//创建vector

vector<int> v1;

//插入元素

for (int i = 0; i < 10; i++) {

v1.push_back(i);

}

//遍历-[]取值

for (int i = 0; i < v1.size(); i++) {

cout << v1[i] << " ";

}

cout << endl;

//遍历-at取值

for (int i = 0; i < v1.size(); i++) {

cout << v1.at(i) << " ";

}

cout << endl;

//遍历-迭代器遍历

for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {

cout << *it << " ";

}

cout << endl;

//遍历-迭代器逆向遍历

for (vector<int>::reverse_iterator it = v1.rbegin(); it != v1.rend(); it++) {

cout << *it << " ";

}

cout << endl;

//测试越界

cout << "[]越界:" << v1[20] << endl; //不会抛出异常，可能会崩溃，可能会乱码

cout << "at越界:" << v1.at(20) << endl; //会抛出异常，需要捕获异常

return 0;

}

vector的push_back强化
push_back是在当前vector的内存末尾拷贝元素进入容器。注意这个地方可能产生浅拷贝，所以容器中的对象要支持拷贝操作。另外，如果vector初始化了个数，而不初始化具体的值，push_back也只会在最后面追加。
int main(int argc, const char * argv[]) {

//初始化10个元素的容器

vector<int> v(10);

//打印容器大小

cout << v.size() << endl;

//push_back添加元素

v.push_back(100);

//打印容器大小

cout << v.size() << endl;

//遍历后的结果是 0 0 0 0 0 0 0 0 0 0 100

for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {

cout << *it << " ";

}

cout << endl;

return 0;

}

vector的元素删除
vector的删除，是根据位置进行删除，如果想要删除某个元素，需要找到当前元素的迭代器位置，再进行删除。
erase(iterator)函数，删除后会返回当前迭代器的下一个位置。
int main(int argc, const char * argv[]) {

//1 创建容器并初始化

vector<int> v1(10);

for (int i = 0; i < v1.size(); i++) {

v1[i] = i;

}

//2 区间删除

//--2.1 删除前3个元素

v1.erase(v1.begin(), v1.begin() + 3);

//--2.2 删除指定位置的元素

v1.erase(v1.begin() +3);

//3 根据元素的值进行删除,删除值为2的元素

v1.push_back(2);

v1.push_back(2);

vector<int>::iterator it = v1.begin();

while (it != v1.end()) {

if (*it == 2) {

it = v1.erase(it); //删除后，迭代器指针会执行下一个位置并返回。

}else{

it++;

}

}

//4 遍历打印

for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {

cout << *it << " ";

}

cout << endl;

return 0;

}

vector的插入元素
vector提供了insert函数，结合迭代器位置插入指定的元素。
如果迭代器位置越界，会抛出异常。
int main(int argc, const char * argv[]) {

//初始化vector对象

vector<int> v1(10);

//在指定的位置插入元素10的拷贝

v1.insert(v1.begin() + 3, 10);

//在指定的位置插入3个元素11的拷贝

v1.insert(v1.begin(), 3, 11);

//遍历

for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {

cout << *it << " ";

}

cout << endl;

return 0;

}

STL中的deque容器
deque是一个双端数组容器:可以在头部和尾部操作元素。
push_back 从尾部插入元素
push_front 从头部插入元素
pop_back 从尾部删除元素
pop_front 从头部删除元素
知识点：
distance函数可以求出当前的迭代器指针it距离头部的位置，也就是容器的指针
用法: distance(v1.begin(), it)
int main(int argc, const char * argv[]) {

//定义deque对象

deque<int> d1;

//尾部插入元素

d1.push_back(10);

d1.push_back(20);

d1.push_back(30);

//头部插入元素

d1.push_front(1);

d1.push_front(2);

d1.push_front(3);

//尾部删除元素

d1.pop_back();

//头部删除元素

d1.pop_front();

//修改头部和尾部的值

d1.front() = 111;

d1.back() = 222;

//查找元素为1的下标

//通过distance求取下标

deque<int>::iterator it = d1.begin();

while (it != d1.end()) {

if (*it == 1) {

cout << "下标：" << distance(d1.begin(), it) << endl;

}

it++;

}

//遍历

for (deque<int>::iterator it = d1.begin(); it != d1.end(); it++) {

cout << *it << " ";

}

cout << endl;

return 0;

}

STL中的stack栈容器
在数据结构中，栈是一种先入后出的容器，增加元素叫压栈或者入栈。移除元素通常叫做出栈。
STL提供的stack容器，也是这种基本类型。这里我们演示一下基本元素类型和复杂元素类型。
▽ 基础数据类型的stack
int main(int argc, const char * argv[]) {

//定义stack对象

stack<int> s1;

//入栈

s1.push(1);

s1.push(2);

s1.push(3);

s1.push(4);

//打印栈顶元素，并出栈

while (!s1.empty()) {

//取出栈顶元素

cout << "当前栈顶元素" << s1.top() << endl;

//获取栈的大小

cout << "当前栈的大小" << s1.size() << endl;

//出栈

s1.pop();

}

return 0;

}

复杂数据类型的stack
//定义类

class Teacher {

public:

char name[32];

int age;

void printT()

{

cout << "age = " << age << endl;

}

};

int main(int argc, const char * argv[]) {

Teacher t1, t2, t3;

t1.age = 22;

t2.age = 33;

t3.age = 44;

//定义栈容器

stack<Teacher> s1;

//入栈

s1.push(t1);

s1.push(t2);

s1.push(t3);

//出栈并打印

while (!s1.empty()) {

//打印栈顶元素

Teacher tmp = s1.top();

tmp.printT();

//出栈

s1.pop();

}

return 0;

}

STL中的queue队列容器
队列是一种数据结构，具备队头和队尾。常见的有FIFO(先入先出)队列等。
#include <queue>

void main()

{

queue<int> q;

q.push(1);

q.push(2);

q.push(3);

cout << "对头元素" << q.front() <<endl;

cout << "队列的大小 " << q.size() <<endl;

while (!q.empty()){

int tmp = q.front();

cout << tmp << " ";

q.pop();

}

}

class Teacher

{

public：

int age;

char name[32];

void printT()

{

cout << "age ：" << age <<endl;

}

}

void main()

{

Teacher t1,t2,t3;

t1.age = 31;

t2.age = 32;

t3.age = 33;

queue<Teacher > q;

q.push(t1);

q.push(t2);

q.push(t3);

while (!q.empty()){

Teacher tmp = q.front();

tmp.printT();

q.pop();

}

}

STL中的list容器
list容器具有如下特性：
可以在头部和尾部插入和删除元素
不能随机访问元素，也就是迭代器只能只能++,不能一次性跳转
list的基本操作
int main(int argc, const char * argv[]) {

//创建list对象

list<int> l;

//尾部添加元素

for (int i = 0; i < 10; i++) {

l.push_back(i);

}

//头部添加元素

l.push_front(111);

//遍历

for (list<int>::iterator it = l.begin(); it != l.end(); it++) {

cout << *it << " ";

}

cout << endl;

//list不能随机访问

list<int>::iterator it = l.begin();

it++;

it++;

cout << *it <<endl;

// it = it + 1; //编译报错，不能随机访问

// it = it + 5; //编译报错，不能随机访问

return 0;

}

list的删除
list提供了两个函数用来删除元素,分别是erase和remove。
erase是通过位置或者区间来删除,主要结合迭代器指针来操作
remove是通过值来删除
int main(int argc, const char * argv[]) {

//创建list对象

list<int> l;

//添加数据

for (int i = 0; i < 10; i++) {

l.push_back(i);

}

l.push_back(100);

l.push_back(100);

//删除头部元素

l.erase(l.begin());

//删除某个区间

list<int>::iterator it = l.begin();

it++;

it++;

it++;

l.erase(l.begin(), it);

//移除值为100的所有元素

l.remove(100);

//遍历

for (list<int>::iterator it = l.begin(); it != l.end(); it++) {

cout << *it << " ";

}

cout << endl;

return 0;

}

STL中的priority_queue优先级队列容器
优先级队列分为：最小值优先队列和最大值优先队列。
此处的最大值、最小值是指队头的元素(增序、降序)。默认，是创建最大值优先级队列。
定义优先级的方法：
priority_queue默认定义int类型的最大值队列
priority_queue<int, vector, less>定义int型的最大值优先队列
priority_queue<int, vector, greater>定义int型的最小值队列
上面的定义中，less和greater相当于谓词，是预定义好的排序函数，我们称之为“仿函数”。后面会介绍它的用法。
void main()

{

//定义优先级队列(默认是最大值优先级队列)

priority_queue<int> p1;

//定义一个最大优先级队列

//less是提前定义好的预定义函数 相当于谓词

priority_queue<int, vector<int>, less<int>> p2;

//定义一个最小值优先级队列v

priority_queue<int, vector<int>, greater<int>> p3;

//给默认的最大优先级队列入栈

p1.push(33);

p1.push(11);

p1.push(55);

p1.push(22);

//打印最大优先级的对头元素

cout<<"对头元素:"<< p1.top() <<endl;

cout<<"队列的大小:"<< p1.size() <<endl;

//给最小值优先级队列入栈

p3.push(33);

p3.push(11);

p3.push(55);

p3.push(22);

//打印最小优先级队列的对头元素

cout<<"对头元素:"<< p3.top() <<endl;

cout<<"队列的大小:"<< p3.size() <<endl;

}

STL中的set和multiset集合容器
set是一个集合，Objective-C语言中也有集合的概念。C++中的集合与OC中的集合也有不同的地方。
C++的set容器，其中包含的元素是唯一的，而且是有序的。
C++的set容器，是按照顺序插入的，不能在指定位置插入。
C++的set容器，其结构是红黑二叉树，插入数据的效率比vector快
set元素的插入和删除
set提供了insert和erase函数，用来对元素进行插入和删除操作。
基础类型数据，如果插入的是重复的元素，则插入失败，返回值是一个pair类型
pair类型类似于swift语言中的元组的概念，通过其判断是否插入成功
复杂类型数据，需要通过仿函数来确定元素的顺序，进入判断是否是重复元素。在“自定义对象的排序”里面讲解。
void main()

{

set<int> set1;

//插入元素

for (int i = 0; i<5; i++) {

int tmp = rand();

set1.insert(tmp);

}

//重复插入元素(会插入不成功，下一节会分析如果根据返回值判断是否插入成功)

set1.insert(100);

set1.insert(100);

set1.insert(100);

set1.insert(100);

for (set<int>::iterator it = set1.begin(); it != set1.end(); it++) {

cout << *it <<" ";

}

//删除集合

while(!set1.empty())

{

//获取头部

set<int>::iterator it = set1.begin();

//打印头部元素

cout << *it << endl;

//从头部删除元素

set1.erase(set1.begin());

}

}

普通数据类型的排序
set容器是有序的集合，默认的顺序是从小到大的。
创建集合的方式：
set创建默认的从小到大的int类型的集合
set<int,less>创建一个从小打到大的int类型的集合
set<int,greater>创建一个从大到小的int类型的集合
上面的less和greater就是仿函数，集合会根据这个仿函数的返回值是否为真类进行排序。
//仿函数的原型，下面是C++提供的默认的greater的仿函数(删除了宏定义后的)
struct greater

{

bool operator()(const int &left, const int &right) const

{

//如果左值>右值，为真。从大到小的排列

return left > right;

}

};

我们可以测试下，添加进set集合的元素确实是有顺的。
void main()

{

//默认，从小到大

set<int> set1;

//从小到大--默认就是

set<int, less<int>> set2;

//从大到小

set<int, greater<int>> set3;

//添加元素

for (int i = 0; i < 5; i++) {

int tmp = rand();

set3.insert(tmp);

}

//遍历

for (set<int>::iterator it = set3.begin(); it != set3.end(); it++) {

cout<< *it << " ";

}

}

自定义对象的排序
上面，我们看到了基础的数据类型的集合，是可以排序的。但是，如果集合里面放的是特殊的自定义对象，该如何满足set有序的特性呢?
通过上面的例子，我们知道，基础数据类型的set是有序的关键原因是greater和less仿函数。所以，自定义对象的有序也是通过我们自定义仿函数来保证的。
仿函数，之所以叫仿函数，是因为它跟函数很像，但并不是一个函数。它的结果如下，只要我们实现了这个仿函数，我们也可以对自定义对象进行排序。
//定义仿函数的结构体
struct FunctionName

{

//重载了()运算符，实现两个自定义对象的比较

bool opeartor() (Type &left, Type &right)

{

//左值大于右值，从大到小的顺序

if(left > right)

return true;

else

return false;

}

};

下面，我们自定义一个Student对象，根据年龄进行排序，将对象加入到set集合中，并进行打印。
如果仿函数实现了根据年龄进行排序，因为set是元素唯一的，所以在插入对象的时候，如果年龄是重复的，则插入不进去了。
//定义student对象
class Student {

public:

Student(const char *name, int age)

{

strcpy(this->name, name);

this->age = age;

}

public:

char name[64];

int age;

};

//提供仿函数，用于自定义对象的set进行排序，要写一个仿函数，用来排序

struct FuncStudent

{

//重载了括号操作符，用来比较大小

bool operator() (const Student &left, const Student &right)

{

//如果左边比右边小，从小到大按照年龄排序

if(left.age < right.age)

return true;

else

return false;

}

};

void main()

{

Student s1("s1",32);

Student s2("s2",22);

Student s3("s3",44);

Student s4("s4",11);

Student s5("s5",22);

//创建集合，采用从小到大的排序

set<Student, FuncStudent> set1;

//插入数据

set1.insert(s1);

set1.insert(s2);

set1.insert(s3);

set1.insert(s4);

//插入不进去(年龄有重复的，所以插不进去了),要通过返回值来确保是否插入成功

set1.insert(s5);

//遍历

for (set<Student>::iterator it = set1.begin(); it != set1.end(); it++) {

cout << it->age << "\t" << it->name <<endl;

}

}

pair类型的返回值
pair类型，就类似于Swift语言中的“元组”的概念，这个类型包含了多个数据类型，在函数返回的时候，可以同时返回多个值。
我们来看一下pair类型的定义它实际上是一个结构体。它包含了两个属性，first和second。
template <class _T1, class _T2>

struct pair

{

typedef _T1 first_type;

typedef _T2 second_type;

_T1 first;

_T2 second;

}

上面的例子中，我们知道set集合中的元素是唯一的，重复的元素插入会失败。如果判断是否插入成功，我们可以通过insert函数的返回值来判断，它的返回值是一个pair类型。我们来看一下insert函数的原型:
pair<iterator,bool> insert(const value_type& __v)
返回的是pair<iterator, bool>类型，pair的第一个属性表示当前插入的迭代器的位置，第二个属性表示插入是否成功的bool值。所以，我们可以通过第二个属性来判断元素是否插入成功。
//pair的使用判断set的insert函数的返回值
void test3()

{

Student s1("s1",32);

Student s2("s2",22);

Student s3("s3",44);

Student s4("s4",11);

Student s5("s5",22);

//创建集合，采用从小到大的排序

set<Student, FuncStudent> set1;

//插入数据，接收返回值

pair<set<Student, FuncStudent>::iterator, bool> pair1 = set1.insert(s1);

if (pair1.second == true) {

cout << "插入s1成功" <<endl;

}else{

cout << "插入s1失败" <<endl;

}

}

set容器数据的查找
set容器提供了多个函数用来查找元素
iterator find(const key_type& __k) find函数查找元素为k的迭代器位置
iterator lower_bound(const key_type& __k) lower_bound函数查找小于等于元素k的迭代器位置
iterator upper_bound(const key_type& __k) upper_bound函数查找大于元素k的迭代器位置
pair<iterator,iterator> equal_range(const key_type& __k) equal_range函数返回一个pair类型，第一个属性表示大于等于k的迭代器位置，第二个是大于k的迭代器位置
void test4()

{

set<int> set1;

for (int i = 0; i < 10; i++) {

set1.insert(i+1);

}


//遍历

```cpp
for (set<int>::iterator it = set1.begin(); it != set1.end(); it++) {

cout << *it <<endl;

}

//查找元素是5的迭代器位置
set::iterator it0 = set1.find(5);
cout << “it0:” << *it0 <<endl;
//查找小于等于5的元素迭代器位置
set::iterator it1 = set1.lower_bound(5);
cout << “it1:” << *it1 <<endl;
//查找大于5的元素迭代器位置
set::iterator it2 = set1.upper_bound(5);
cout << “it2:” << *it2 <<endl;
//返回的pair第一个迭代器是>=5,另一个是>5
pair<set::iterator, set::iterator> mypair = set1.equal_range(5);
set::iterator it3 = mypair.first;
set::iterator it4 = mypair.second;
cout << “it3:” << *it3 <<endl;
cout << “it4:” << *it4 <<endl;
}

# multiset容器

multiset容器，与set容器相似，但是multiset容器中的元素可以重复。另外，他也是自动排序的，容器内部的值不能随便修改，因为有顺序的。

```cpp
void test5()

{

//定义multiset

multiset<int> set1;

//从键盘不停的接收值

int tmp = 0;

printf("请输入multiset集合的值:");

scanf("%d", &tmp);

while (tmp != 0) {

set1.insert(tmp);

scanf("%d", &tmp);

}

//迭代器遍历

for (multiset<int>::iterator it = set1.begin(); it != set1.end(); it++) {

cout<< *it <<" ";

}

cout <<endl;

//删除

while (!set1.empty()) {

multiset<int>::iterator it = set1.begin();

cout << *it << " ";

set1.erase(it);

}

}

STL中的map和multimap映射容器
map和multimap是一个键值映射的容器。map中的键值对都是唯一的，但是multimap中一个键可以对应多个值。
map和multimap是关联式容器，键值成对存在
map和multimap是红黑变体的平衡二叉树结构
map只支持唯一的键值对，集合中的元素是按照一定的顺序排列的
multimap中的键可以出现多次
map和multimap的元素插入过程是按照顺序插入的
map元素的增删改查
map元素的插入，有两种方式：
调用insert函数插入pair类型的键值对
直接使用[]来对键进行复制，类似于Objective-C中的NSMutableDictionary赋值一样。
map的insert函数返回的是pair类型，pair的第二个参数表示是否插入成功。如果插入的元素键名相同，则插入失败。
map元素的删除，跟上面其他的容器一样，都是直接调用erase函数.
int main()

{

map<int, string> map1;

//insert方法插入

//--1 通过pair<int, string>(1,”chenhua“) 构造pair元素

map1.insert(pair<int, string>(1,"chenhua"));

//--2 通过make_pair构造pair元素

map1.insert(make_pair(2,"mengna"));

//--3 通过value_type构造pair元素

map1.insert(map<int, string>::value_type(3,"chenmeng"));

//[]直接插入

map1[4] = "menghua";

//重复插入(插入会不成功)

pair<map<int, string>::iterator, bool> pair1 = map1.insert(make_pair(2, "haha"));

if (pair1.second) {

cout << "重复插入成功" << endl;

}else{

cout << "重复插入失败" << endl;

}

//元素的修改

//map[1] = "22"的方式，如果不存在键则插入，存在键则修改

map1[2] = "haha";

//元素的删除

//--删除值为"haha"的元素

for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++) {

if (it->second.compare("haha") == 0) {

map1.erase(it);

}

}

//遍历

for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++) {

cout << it->first << "\t" << it->second << endl;

}

return 0;

}

map元素的查找
map提供了两个函数进行key的查找：find和equal_range。
int main()

{

//定义map

map<int ,string> map1;

map1[1] = "chenhua";

map1[2] = "mengna";

//查找key=100的键值对

map<int, string>::iterator it = map1.find(100);

if (it != map1.end()) {

cout << "存在key=100的键值对";

}else{

cout << "不存在" << endl;

}

//查找key = 1000的位置

//返回两个迭代器，第一个表示<=1000的迭代器位置，第二个是>1000的迭代器位置

pair<map<int, string>::iterator, map<int, string>::iterator> mypair = map1.equal_range(1000);

if (mypair.first == map1.end()) {

cout << "大于等于5的位置不存在" << endl;

}else{

cout << mypair.first->first << "\t" << mypair.first->second << endl;

}

if (mypair.second == map1.end()) {

cout << "大于5的位置不存在" << endl;

}else{

cout << mypair.second->first << "\t" << mypair.second->second << endl;

}

return 0;

}

multimap容器
multimap容器，与map容器的唯一区别是：multimap支持多个键值。
由于支持多个键值，multimap提供了cout函数来计算同一个key的元素个数。
class Person {

public:

string name; //姓名

int age; //年龄

string tel; //电话

double sal; //工资

};

void test()

{

Person p1,p2,p3,p4,p5;

p1.name = "王1";

p1.age = 31;

p2.name = "王2";

p2.age = 31;

p3.name = "张3";

p3.age = 31;

p4.name = "张4";

p4.age = 31;

p5.name = "钱5";

p5.age = 31;

multimap<string, Person> map2;

//sale部门

map2.insert(make_pair("sale", p1));

map2.insert(make_pair("sale", p2));

//development部门

map2.insert(make_pair("development", p3));

map2.insert(make_pair("development", p4));

//Finanncial部门

map2.insert(make_pair("Finanncial", p5));

//遍历

for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++) {

cout << it->first << "\t" << it->second.name << endl;

}

//按部门显示员工信息

int developNum = (int) map2.count("development");

cout << "development部门人数：" << developNum << endl;

multimap<string,Person>::iterator it2 = map2.find("development");

int tag = 0;

while (it2 != map2.end() && tag < developNum) {

cout << it2->first << "\t" << it2->second.name <<endl;

it2 ++;

tag ++;

}

//把age=32 修改name= 32

for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++) {

if (it->second.age == 32) {

it->second.name = "32";

}

}

}

int main(int argc, const char * argv[]) {

test();

return 0;

}

STL容器的通用性探究
到这里，STL的容器我们基本讲解完毕了。STL的容器主要利用了C++的模板特性来实现。需要注意：
容器缓存了节点，节点类要确保支持拷贝(否则出现浅拷贝问题，导致崩溃)
容器中的一般节点类，需要提供拷贝构造函数，并重载等号操作符(用来赋值)
容器在插入元素时，会自动进行元素的拷贝。
针对容器，容器之间也支持拷贝。所以需要注意：
除了queue和stack外，每个容器都提供了可返回迭代器的函数，运用返回的跌打器就可以访问元素
通常STL不会抛出异常，要求使用者确保传入正确的参数
每个容器都提供了一个默认构造函数和一个默认拷贝构造函数
STL容器的元素拷贝
下面，我们演示一下，如果容器元素如果没有实现拷贝构造函数，出现浅拷贝后的崩溃问题。
#include <iostream>

#include <string>

#include <vector>

using namespace std;

class Student {

public:

Student(const char *name, int age)

{

cout << "构造函数" << endl;

//分配内存空间

m_name = new char[strlen(name) + 1];

//值拷贝

strcpy(m_name, name);

m_age = age;

}

~Student()

{

printf("%p 指向的空间 调用析构函数\n", m_name);

if (m_name != NULL) {

delete []m_name;

m_age = 0;

}

}

private:

char *m_name;

int m_age;

};

int main()

{

Student s1("chenhua",24);

vector<Student> v1;

v1.push_back(s1);

return 0;

}

上面的代码段，运行后的结果如下：
构造函数
0x100302a00 指向的空间 调用析构函数
0x100302a00 指向的空间 调用析构函数
运行后，打印出结果后并报错。报错原因是同一个内存空间被释放了2次，导致的崩溃。其根本原因是,v1将s1拷贝到容器，由于Student没有重写拷贝构造函数，从而出现了浅拷贝，只拷贝了地址。释放的时候毫无疑问出现错误。
如果我们给Student重写了拷贝构造函数和重载了等号操作符，则上面的错误就不会出现。
//重写拷贝构造函数
Student(const Student &obj)

{

//分配内存空间

m_name = new char[strlen(obj.m_name) + 1];

//值拷贝

strcpy(m_name, obj.m_name);

m_age = obj.m_age;

}

//重载等号运算符
Student & operator=(const Student &obj)

{

//释放旧值

if (m_name != NULL) {

delete [] m_name;

m_age = 0;

}

//分配内存空间并赋值

m_name = new char[strlen(obj.m_name) + 1];

strcpy(m_name, obj.m_name);

m_age = obj.m_age;

return *this;

}

STL容器的比较
STL提供了很多容器，每种容器有其自身的特点，我们该如何使用它们呢?
vectordequelistsetmutlisetmapmultimap
内存结构单端数组双端数组双向链表二叉树二叉树二叉树二叉树
随机存取是是否否否对key而言是否
查找速度慢慢非常慢快快对key而言快对key而言快
插入删除尾端头尾两端任何位置