C++:线上课程2

文章目录

• 
  

  一、STL

• • 1.几种插入函数的区别
  • 2.vector和智能指针
• 
  

  二、List

• • 1、List存储结构
  • 2. *** 作
  • • 2.1 unique（排序之后删除重复元素）
  • 3.vector和list区别
• 
  

  三、deque(双端队列)

• • 1. deque简介
  • 2.deque使用
  • • 2.1 元素访问
    • 2.2.容量
    • 2.3. 修改器
  • 3.deque图
  • 4.deque面试问题
  • 5. 代码示例

---

一、STL 1.几种插入函数的区别

	objevc.reserve(100);//只进行空间的扩充，不进行对象的创建
	objevc.resize(100);//既进行空间的扩充，又进行对象的创建

class Object
{
private:
	int value;
public:
	Object(int x = 0)
		:value(x)
	{
		cout << " Object " << endl;
	}
	Object(int x, int y)
		:value(x + y)
	{
		cout << " Object " << endl;

	}
	Object(const Object& obj)
		:value(obj.value)
	{
		cout << " Object& " << endl;
	}
	Object(Object&& obj)
		:value(obj.value)
	{
		cout << " move Object&& " << endl;
	}
	Object& operator=(const Object& obj)
	{
		value = obj.value;
		cout << " operator = " << endl;
		return *this;
	}
	Object& operator=(Object&& obj)
	{
		value = obj.value;
		cout << " move operator = " << endl;
		return *this;
	}
	~Object()
	{
		cout << " ~Object " << endl;
	}

	int& Value()
	{
		return value;
	}
	const int& Value() const
	{
		return value;
	}
};

int main()
{
	vector<Object> objevc;//创建对象，有空间但是无对象
	objevc.reserve(100);//（只进行空间的扩充，不进行对象的创建)

	objevc.push_back(Object(10)); //调动构造函数产生无名对象，调动移动构造函数把产生的对象进行构造，析构无名对象
	objevc.push_back(20);//调动构造函数产生无名对象，调动移动构造函数把产生的对象构建进去，将临时对象进行析构
	objevc.emplace_back(30);//先定位构建对象地址，直接调动构造函数，把变量初始化到内存中

	return 0;
}

2.vector和智能指针

int main()
{
	std::vector<Shape*> shape;
	string name;
	while (cin >> name, name != "end")
	{
		if (name == "Circle")
		{
			shape.push_back(new Circle());
		}
		else if (name == "Square")
		{
			shape.push_back(new Square());
		}
		else
		{
			cout << "input class name error!" << name << endl;
		}
	}
	for (auto& x : shape)//x类型：shape*&
	{
		cout << typeid(x).name() << endl;
		x->draw();
		x->erase();
	}
	//写法一
	for (auto& x : shape)
	{
		delete x;
		x = nullptr;
	}
}

int main()
{
	std::vector<std::unique_ptr<Shape>> shape;

	string name;
	while (cin >> name, name != "end")
	{
		if (name == "Circle")
		{
			//shape.push_back(std::make_unique ());
			shape.push_back(unique_ptr<Shape>(new Circle()));
		}
		else if (name == "Square")
		{
			shape.push_back(std::make_unique <Square>());
		}
		else
		{
			cout << "input class name error!" << name << endl;
		}
	}
	for (auto& x : shape)//x类型：shape*&
	{
		cout << typeid(x).name() << endl;
		x->draw();
		x->erase();
	}
}

二、List 1、List存储结构

int main()
{
	int ar[] = { 12, 23, 34, 45, 56,67,78,89,90,100 };
	std::vector<int> vec = { 1,2,3,4,5,6,7 };//初始化
	std::list<int> ilist1;//initializer_list初始化列表中
	std::list<int> ilist2 = { 12,23,34,45,56 };
	std::list<int> ilist3(10, 23);
	std::list<int> ilist4(ar, ar + 10);//数组的每个元素放入链表中，构成双链表形式
	std::list<int> list5(ilist2);
	std::list<int> list6(std::move(ilist2));
	std::list<int> ilist7(vec.begin(), vec.end());//STL
}

2. *** 作

merge	合并两个已排序列表
splice	从另一个list中移动元素
remove/remove-if	移除满足特定标准的元素
reverse_if	将该链表的所有元素的顺序反转
unique	删除连续的重复元素
sort	对元素进行排序

2.1 unique（排序之后删除重复元素）

int main()
{
	std::list<int> ilist1 = { 2,4,7,4,3,9,7,5,3,1,4,6,8 };
	for (auto& x : ilist1)
	{
		cout << x << " ";
	}
	cout << endl;
	ilist1.sort();
	ilist1.unique();
	for (auto& x : ilist1)
	{
		cout << x << " ";
	}
	cout << endl;
}

运行结果

3.vector和list区别

	vector	list
底层实现	连续存储的容器，动态数组，在堆上分配内存	动态双向链表，在堆上分配空间
空间利用率	连续空间，不易造成内存碎片空间利用率高	节点不连续，易造成内存碎片，小元素使节点密度降低，空间利用率低
查询元素	iterator operaor[],find O(n),binary_search O(logn)	iterator fin O(n)
插入和删除	在最后插入（空间够）：push_back(val); O(1) 在最后插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝 在中间插入（空间够)︰内存拷贝 在中间插入(空间不够)︰需要内存申请和释放，以及对之前数据进行拷贝 Insert(it,val) O(n); 删除：pop_back() 在最后删除：O(1) 在中间删除：内存拷贝，不需要释放内存。 erase(it) O(n) resize(10):开辟空间，还放数据 reserve(10)：只开辟空间，不放数据。 初始化vector空间，提高vector的使用效率	插入：O(1),（需要内存申请）push_front(val);push_back(val) O(1),insert(it,val) o(1) 删除：O(1), （需要内存释放）opo_front() O(1); opo_back() O(1); erase(it) O(n);
迭代器	随机迭代器，迭代器检查越界。 支持++，–，+，+=，<，>，！=，==	双向迭代器，迭代器检查越界。 支持++,- -,==,!=
迭代器失效	插入和删除元素都会导致迭代器失效	插入元素不会导致迭代器失效；删除元素导致当前迭代器失效，不影响其他迭代器

总结：

1. vector底层实现是数组；list是双向链表
2. vector支持随机访问，list不支持
3. vecto是顺序内存，list不是
4. vector在中间节点进行插入删除会导致内存拷贝，list不会
5. vector一次性分配好内存，不够时才进行2倍扩容（或1.5倍）；list每次插入新节点都会进行内存申请
6. vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好

• 什么时候用vector？什么时候该用list？

1. 如果需要高效的随机存取，而不在乎插入和删除的效率（很少使用插入和删除 *** 作)。
   

   
   

   选用vector。
   

   
   

2. 如果需要大量的插入和删除的 *** 作，随机存取很少使用。
   

   
   

   选用list。
   

   
   

举例

例1:比如制作了一个游戏玩家排行榜，那么就要实时刷新这个排行榜，这个时候，如果有人达到排行的条件，那么就要把他加进去，如果人数多出了，那么就把排名靠后的移除掉，这就需要大量的插入删除 *** 作，那么这个时候就应该优先考虑list，而不是vector。

例⒉:比如我有大量的数据，这些数据是不变的，我需要不时的查看邃些数据，进行筛选之类的 *** 作，那么选择vector就要优于list。

三、deque(双端队列) 1. deque简介

deque是由一块一块的固定大小的连续空间构成(块与块之间是不连续)。

一旦有必要在deque的前端或尾端增加新的空间，便配置一块固定大小的连续空间，串接在整个deque 的头端或尾端。

deque 的最大任务，便是在这些分块的固定大小连续空间上，维护其整体连续的假象，并提供随机存取的接口(随机迭代器)，代价则是迭代器架构较为复杂。

deque 采用一块所谓的_M_map(注意，不是STL的map容器)作为主控。

这里所谓_M_map是一小块连续空间，其中每个元素（此处称为一个节点，node)都是指针，指向另一段(较大的）连续线性空间，称为缓冲区。

缓冲区才是deque的储存空间主体。

2.deque使用 2.1 元素访问

at	访问指定的元素，同时进行越界检查
operator[]	访问指定的元素
front	访问第一个元素
back	访问最后一个元素

2.2.容量

empty	检查容器是否为空
size	返回容纳的元素数
max_size	返回可容纳的最大元素数
shrink_to_fit	通过释放未使用的内存减少内存的使用

2.3. 修改器

clear	清除内容
insert	插入元素
emplace	原位构造元素
erase	擦除元素
push_back	将元素添加到容器末尾
emplace_back	在容器末尾就地构造元素
pop_back	移除末元素
push_front	插入元素到容器起始
emplace_front	在容器头部就地构造元素
pop_front	移除首元素
resize	改变容器中可存储元素的个数
swap	交换内容

3.deque图

4.deque面试问题

问题1:请描述deque vector 对存储空间的管理有何不同?

问题2:分析为什么STL的 stack和 queue 适配器默认优先使用deque而不是vector或 list 作为底层容器?

问题3∶分析为什么STL的priority_queue必须使用vector作为底层容器?而不能使用deque和 list作为底层容器?

双端队列元素插入结构图

5. 代码示例

template<class _Tp>
struct _Deque_iterator
{
	typedef _Tp** _Map_pointer;

	_Tp* _M_cur;
	_Tp* _M_first;
	_Tp* _M_last;
	_Map_pointer _M_node;
};

template<class _Tp>
class _Deque_base
{
	typedef_Deque_iterator<_Tp> iterator;
protected:
	_Tp** _M_map;//二级指针
	size_t _M_map_size;//map大小
	iterator _M_start;
	iterator _M_finish;
};

---