C++STL容器

STL

• 近容器
• 容器
• 顺序容器
• • vector:一维数组
  • • vector基本操作
    • 使用迭代器遍历vector
    • • 方法一：
      • 方法二：
    • 使用迭代器对vector进行增删改查
    • • 增加
      • 修改
      • 删除
    • 通过模板函数打印容器内部的数据
    • 使用vector实现二维数组
  • list:链表
  • • 使用list的迭代器初始化vector
    • list的成员方法
  • deque：双端队列
  • • 重点：deque如何扩容
    • 容器适配器
    • • 栈
      • 队列
  • priority_queue:优先级队列
• 关联容器
• • set:集合
  • multiset：多重集合
  • map:映射表
  • multimap:多重映射表

近容器

• 接近容器。有容器的某些特点，但是不能完全满足容器的所有特点
  int arr[10]; 只可以存放整型数据
  string s1; 只可以存放字符串

void show(string& s)
{
	for (int i = 0; i < s.size(); i++)
	{
		cout << s[i] << " ";
	}
	cout << endl;
}

int main()
{
	//string s;//默认构造
	string s("xsyhello");
	string s1(s);//拷贝构造
	//使用迭代器区间进行构造
	string s2(s1.begin(), s1.end());
	for (int i = 0; i < 10; i++)
	{
		if (s[i] == 'b')
		{
			s[i] = 'x';
		}
		s.push_back('a' + i);
	}

	show(s);
	s.pop_back();

	show(s);

	cout << s.c_str() << endl;
	cout << typeid(s.c_str()).name() << endl;

	//string重载了输入和输出运算符
	//cin >> s;
	//cout << s << endl;

	string::iterator it = s.begin();
	for (; it != s.end(); it++)
	{
		//通过迭代器增加
		

		//通过迭代器删除
		if (*it == 'a')
		{
			it = s.erase(it);//无论增加还是删除都需要重新获取迭代器
			cout << *it << " ";
			it++;
		}
		cout << *it << " ";
	}
	cout << endl;


	char err[10] = { "abcdefg" };
	char* p = err;
	s.copy(p, 4);//从对象将数据拷贝到指针
	cout << err << endl;

	show(s1);
	s.swap(s1);//交换两个容器的数据
	show(s);

	int a=s.find("a");//find可以用来寻找字符
	cout << a << endl;
	int b=s.find("yhe");//find可以用来寻找子串
	cout << b << endl;

	return 0;
}

容器

目的的为了存放数据。作为数据的载体，容器要求所有的数据类型都可以存放

顺序容器

以下的容器都是模板，适配不同的类型参数就可以存放不同类型的数据

vector:一维数组

• 底层按照1.5倍进行扩容

vector基本操作

int main()
{
	vectorv;
	vectorv1;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	v.pop_back();

	cout << v.back() << endl;
	cout << v.size() << endl;
	cout << v.max_size() << endl;//当前内存里面该vector可以存放多少数据
	v.swap(v1);//交换两个容器中的数据
	v.clear();//清除
	v.empty();//判空
	v.reserve(10);
	v.resize(10);//强制扩容

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}

	return 0;
}

使用迭代器遍历vector

使用迭代器，通过统一的方式对容器内部数据进行访问，对于写泛型算法非常方便

方法一：

vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		cout << *it << " ";
	}

方法二：

copy(v1.begin(), v1.end(), ostream_iterator(cout, " "));

使用迭代器对vector进行增删改查 增加

vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		if (*it == 5)
		{
			it = v1.insert(it, 999);
			it++;
		}
	}

修改

vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		if (*it == 5)
		{
			*it=999;
		}
	}

删除

vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		if (*it == 5)
		{
			it = v1.erase(it);
		}
	}

通过模板函数打印容器内部的数据

template 
void show_con(CON& con)
{
	typename CON::iterator it = con.begin();
	for (; it != con.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

使用vector实现二维数组

vector>v1;

list:链表 使用list的迭代器初始化vector

	listL;
	for (int i = 0; i < 10; i++)
	{
		L.push_back(i);
	}
	show_con(L);

	vectorv1(L.begin(), L.end());

list的成员方法

list成员方法的使用和vector大致相同
list多了2个成员方法：

• push_front();//头插
• pop_back();//头删
• reverse();//链表逆置
• 有resize();//强制扩容
• 没有reserve();

deque：双端队列

• 底层是二维数组

重点：deque如何扩容

deque含有两个指针，一个指向头部，一个指向尾部。初始时指向同一处

容器适配器 栈

• 真正的容器里的栈(stack)----底层实现依赖于deque
  stack:先进后出
  deque 只使用push_back和pop_back就可以实现

int main()
{
	stacks;
	for (int i = 0; i < 10; i++)
	{
		s.push(i + 1);//入栈
	}
	s.pop();//出栈
	s.top();//获取栈顶元素
	cout << s.empty() << endl;


	return 0;
}

队列

• 队列（queue)-----底层实现依赖deque
  queue:先进先出
  deque 只使用push_front和pop_back就可以实现

int main()
{
	queueq;
	for (int i = 0; i < 10; i++)
	{
		q.push(i + 1);//入队列
		
	}
	cout << q.front() << endl;
	cout << q.back() << endl;

	q.pop();//出队列
	q.front();//取队头元素
	q.size();
	q.empty();
	//q.swap();//交换队列
	
	cout << q.empty() << endl;


	return 0;
}

priority_queue:优先级队列

• 相当于对插入队列的数据进行排序

关联容器 set:集合

• 数据有序：底层红黑树，插入自动排序
• 底层红黑树，增删改查速度非常快
• 数据不允许重复

multiset：多重集合

• 数据有序：底层红黑树，插入自动排序
• 底层红黑树，增删改查速度非常快
• 数据允许重复

multisets;
	s.insert(13);
	s.insert(24);
	s.insert(2);
	s.insert(12);
	s.insert(7);
	s.insert(3);
	s.insert(24);

	//s.erase(24);
	show_con(s);

	set::iterator it = s.find(12);
	if (it != s.end())
	{
		for (int i = 0; i < s.count(24);i++)
		{
			cout << *it << endl;
			it++;
		}
		
	}
	else
	{
		cout << "not find" << endl;
	}

map:映射表

• 数据按key有序
• 底层红黑树实现
• key不允许重复

int main()
{
	mapm;
	m.insert(make_pair(1, "aaaaa"));
	m.insert(make_pair(3, "vvvv"));
	m.insert(make_pair(2, "yyyyy"));
	m.insert(make_pair(7, "bbbbb"));
	m.insert(make_pair(4, "nnnnn"));//make_pair:是一个函数模板，返回一个pair类型的对象，再将对象插进去
	m.insert(pair(5, "jjjjj"));//插入pair类型的对象，可以直接构造一个pair类型对象插进去
	//show_con(m);

	//查询方式一：
	map::iterator it = m.begin();
	for (; it != m.end(); it++)
	{
		cout << it->first << "---->";
		cout << it->second << " " << endl;
	}
	cout << endl;
	
	//查询方式二：
	map::iterator it1 = m.find(2);
	if (it1 != m.end())
	{
		cout << it->first << "---->";
		cout << it->second << " " << endl;
	}

	//查询方式三：一般不推荐，容易出错
	cout << m[4] << endl;

	return 0;
}

multimap:多重映射表

• 数据按key有序
• 底层红黑树实现
• key允许重复

int main()
{
	multimapm;
	m.insert(make_pair(1, "aaaaa"));
	m.insert(make_pair(3, "vvvv"));
	m.insert(make_pair(2, "yyyyy"));
	m.insert(make_pair(3, "bbbbb"));
	m.insert(make_pair(4, "nnnnn"));//make_pair:是一个函数模板，返回一个pair类型的对象，再将对象插进去
	m.insert(pair(5, "jjjjj"));//插入pair类型的对象，可以直接构造一个pair类型对象插进去
//show_con(m);

//查询方式一：
	multimap::iterator it = m.begin();
	for (; it != m.end(); it++)
	{
		cout << it->first << "---->";
		cout << it->second << " " << endl;
	}
	cout << endl;

//查询方式二：
	multimap::iterator it1 = m.find(3);
	if (it1 != m.end())
	{
		for (int i = 0; i < m.count(3); i++)
		{
			cout << it1->first << "---->";
			cout << it1->second << " " << endl;
		}
	
	}

//查询方式三：一般不推荐，容易出错
	cout << m[4] << endl;

	return 0;
}