首页计算机科学C++汇编与STl新特征

# 顺序容器

容器库是 类 与 算法 的汇集

# 数组

  • 静态的连续数组 array
  • 动态连续数组 vector

# array

# 头文件

#include <array>

# 定义

std::array<int,3> a = {1,2,3};

注意：当期长度为零时，array (N==0) 有特殊情况，此时 array.begin ()==array.end (), 并拥有某个唯一值，在零长亦可将 array 上调用 front 或 back () 是未定义的

# 元素访问

  • at : 访问 指定 的元素，同时进行越界检查
  • operator[] : 访问指定的元素
  • front : 访问 第一个 元素
  • back : 访问 最后一个 元素
  • data : 直接访问底层数组的指针，返回的指针使得返回 [data (),data ()+size ()] 始终是合法范围，即使容器为空 (此时 data () 不可解引用)。对于底层元素存储的指针，对于非空容器，返回的指针与首元素地址比较相等
//array 数组元素访问
#include <iostream>
#include <array>
using namespace std;
int main(void)
{
	array<int,8> a = { 1,2,3,4,5,6,7,8 };
	cout << "at(2)=" << a.at(2) << endl;
	cout << "operator[2]=" << a[2] << endl;
	cout << "首front=" << a.front() << endl;
	cout << "尾back=" << a.back() << endl;
	//a.data 返回 array 首元素地址
	cout << "data =" << a.data()[2] << endl;
	// 遍历数组
	for (int i = 0; i < a.size() ; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

# 迭代器

  • begin/cbegin : 访问指向起始的 迭代器
  • end / cend ：返回指向末位的迭代器
  • rbegin / crbegin ：返回指向起始的 逆向 迭代器
  • rend / crend ： 返回指向末位的逆向迭代器
    迭代器区别
//array 的迭代器
#include <iostream>
#include <array>
using namespace std;
int main(void)
{
	array<int,6> a = { 1,2,3,4,5,6 };
	// 打印首元素
	//cout << *a.begin() << endl;
	// 打印所有元素
	//for_each(a.cbegin(), a.cend(),
	//	[](int x){
	//		cout << x << " ";
	//	});
	//cout << "\n";
	//// 不加 c
	//for_each(a.begin(), a.end(),
	//	[](int x)
	//	{
	//		cout << x << " ";
	//	});
	//cout << "\n";
	// 使用 while 正序
	auto first = a.cbegin();
	auto last = a.cend();
	while (first != last)
	{
		cout << *first << " ";
		(first)++;
	}
	cout << endl;
	// 逆序 r
	// 使用 while
	auto first_r = a.rbegin();
	auto last_r = a.rend();
	while (first_r !=last_r)
	{
		cout << *first_r << " ";
		first_r++;
	}
	cout << endl;
	return 0;
}
// 输出
/*
1 2 3 4 5 6
6 5 4 3 2 1
*/
# 容器
  • empty : 检查容器是否为空，若为空 0, 否则 1
  • size : 返回容纳的元素数
  • max_size ：返回可容纳的最大元素数
#include <iostream>
#include <array>
using namespace std;
int main(void)
{
	array<int, 3> a = { 1,2,3 };
	array <int, 0> no;
	// 判断是否为空
	cout << boolalpha; // 把 bool 值显示为 true 或 false
	cout << "a.empty() ： " << a.empty() << endl;
	cout << "no.empty() ： " << no.empty() << endl;
	// 返回元素个数
	cout << "a.size() :" << a.size() << endl;
	// 返回元素最大，由于 array 大小固定等于 size
	cout << "a.max_size() :" << a.max_size() << endl;
	return 0;
}
/*
a.empty() ： false
no.empty() ： true
a.size() :3
a.max_size() :3
*/
# 操作
  • fill : 以指定值填充容器
  • swap : 交换内容
#include <iostream>
#include <array>
using namespace std;
int main(void)
{
	array<int, 3> a;
	array<int, 3> b ;
	// 判断是否为空
	cout << boolalpha; // 把 bool 值显示为 true 或 false
	cout << "a.empty() ： " << a.empty() << endl;
	// 将所有元素用 2 填充
	a.fill(2);
	b.fill(6);
	// 将 a 的元素与 b 元素交换
	a.swap(b);
	// 返回 a 元素个数
	cout << "a.size() :" << a.size() << endl;
	// 返回 a 的所有元素
	cout << "A数组:";
	auto first_ra = a.rbegin();
	auto last_ra = a.rend();
	while (first_ra != last_ra)
	{
		cout << *first_ra << " ";
		first_ra++;
	}
	cout << endl;
	// 返回 b 元素个数
	cout << "b.size() :" << a.size() << endl;
	// 返回 b 的所有元素
	auto first_rb = b.rbegin();
	auto last_rb = b.rend();
	cout << "B数组:";
	while (first_rb != last_rb)
	{
		cout << *first_rb << " ";
		first_rb++;
	}
	cout << endl;
	return 0;
}
/*
a.empty () ： false
a.size () :3
A 数组：6 6 6
b.size () :3
B 数组：2 2 2
*/
# 辅助类
  • tuple_size(std::array) : 提供用于编译时常量表达式访问 array 中元素数量的方法
  • tuple_element<std::array> : 获取 array 元素的类型。提供 tuple 接口，提供 array 元素类型编译时代下标访问
/* 辅助类 */
#include <iostream>
#include <array>
using namespace std;
template<class T>
void test(T t)
{
	int a[tuple_size<T>::value];// 能用于编译时
	cout << tuple_size<T>::value << endl;
}
int main(void)
{
	array<float, 3> arr = { 1,2,3 };
	test( arr );
	return 0;
}
/*
3
*/
# vector
# 头文件
vector 是封装动态数组的顺序容器， vector 的存储是自动管理的，按需扩张收缩， vector 通产占用 多余 静态数组的空间，因此要分配更多内存以管理将来的增长。 vector 所用的方式不在每次插入元素时，而只在额外内存耗尽时重分配。分配的内存总量可用 capacity() 函数查询，可以通过调用 shrink_to_fit() 返回多出的内存给系统。重分配通常是性能上有开销的操作，如果元素数量已知，那么 reserve () 函数可用于消除重分配
#include <vector>
# 元素访问
  • at ： 访问指定的元素，同时进行越界检查
  • operator[] ：访问指定的元素
  • front ：访问第一个元素
  • back ：访问之后一个元素
  • data ：直接访问底层数组
# 迭代器
  • begin/cbegin ：返回指向起始的迭代器
  • end/cend ：返回指向末位的迭代器
  • rbegin/crbegin : 返回指向起始的逆向迭代器
  • rend/crend : 返回指向末尾的逆向迭代器
# 容量
  • empty : 检查容器是否为空
  • size : 返回容纳的元素数
  • max_size : 返回可容纳的最大元素数 (根据系统或库实现限制的容器可保有的元素最大数量)，此值通常反应容器大小的理论极限
  • reserve : 预留存储空间
  • capacity : 返回当前存储空间能够容纳的元素数
  • shrink_to_fit ：通过释放未使用的内存减少内存的使用
/*
* project： vector 容器语法
*/
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	vector<int> a;
	// 返回当前可容纳元素容量的理论最大值
	cout << "Maximum size of a vector is :" << a.max_size() << endl;
	//capacity 返回容器当前已为之分配空间的元素数
	cout << "capacity size of a vector is :" << a.capacity() << endl;
	// 增加 vector 的容量到大约或等于 new_cap 的值，参数 vector 的新容量
	a.reserve(10);
	//capacity 返回容器当前已为之分配空间的元素数
	cout << "New capacity size of a vector is :" << a.capacity() << endl;
	a = { 1,2,3,4 };
	// 请求移除未使用的容量
	a.shrink_to_fit();
	//capacity 返回容器当前已为之分配空间的元素数
	cout << "Shrink capacity size of a vector is :" << a.capacity() << endl;
	return 0;
}
/*
Maximum size of a vector is :4611686018427387903
capacity size of a vector is :0
New capacity size of a vector is :10
Shrink capacity size of a vector is :4
*/
# 修改器
  • clear : 清除内容
  • insert : 插入元素
    • 参数；
    • pos : 将内容那个插入到它前面的迭代器
    • value : 要插入的元素值
    • first,last ：要插入的元素范围，不能是指向调用 insert 所用的容器中的迭代器
    • ilist ：要插入来源的 initializer_list
    • 注意：如果新的 size () 大于留的 capacity 就会导致 重分配 ，如果新的 size () 大于 capacity ()，那么所有迭代器和引用都会失效，否则只有在插入点前的迭代器和引用会保持有效
#include <iostream>
//project:
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
// 动态数组输出函数
void print(int id, const vector<int>& a)
{
	cout << id << ". ";
	for (const int x : a)
	{
		cout << x << " ";
	}
	cout << endl;
}
int main(void)
{
	// 创建动态数组
	vector<int> c1 (3,100);
	// 插入元素
	print(1, c1);
	// 在 c1 受元素插入 200
	auto it = c1.begin();
	it = c1.insert(it, 200);
	print(2, c1);
	// 将上面的两个值 it 初始位置插入两个 300
	c1.insert(it, 2, 300);
	print(3, c1);
	//it 已经是失效，提供新迭代器
	it = c1.begin();
	// 创建 c2 数组
	vector<int>c2(2, 400);
	// 在 c1 中插入 it 的位置插入 c2 从 begin 到 end
	c1.insert(next(it, 2), c2.begin(), c2.end());
	print(4, c1);
	return 0;
}
/*
1. 100 100 100
2. 200 100 100 100
3. 300 300 200 100 100 100
4. 300 300 400 400 200 100 100 100
*/
  • emplace : 原位构造元素，直接与 pos 前插入元素到容器中
  • push_back : 将元素添加到容器 末尾
  • emplace_back : 在容器末尾就地构造元素
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
class MyString
{
public:
    MyString(const char* str = NULL);// 普通构造函数
    MyString(const MyString& other);// 拷贝构造函数
    ~MyString(void);// 析构函数
    MyString& operator = (const MyString& other);// 赋值函数
private:
    char* m_data;// 用于保存字符串
};
// 普通构造函数
MyString::MyString(const char* str)
{
    if (str == NULL)
    {
        m_data = new char[1];
        *m_data = '\0';
    }
    else
    {
        int length = strlen(str);
        m_data = new char[length + 1];
        strcpy(m_data, str);
    }
    std::cout << "construct:" << m_data << std::endl;
}
// String 的析构函数
MyString::~MyString(void)
{
    std::cout << "deconstruct:" << m_data << std::endl;
    delete[] m_data;
}
// 拷贝构造函数
MyString::MyString(const MyString& other)
{
    int length = strlen(other.m_data);
    m_data = new char[length + 1];
    strcpy(m_data, other.m_data);
    std::cout << "copy construct:" << m_data << std::endl;
}
// 赋值函数
MyString& MyString::operator = (const MyString& other)
{
    std::cout << "copy assignment" << std::endl;
    if (this == &other)
        return *this;
    if (m_data)
        delete[] m_data;
    int length = strlen(other.m_data);
    m_data = new char[length + 1];
    strcpy(m_data, other.m_data);
    return *this;
}
int main(void)
{
    {
        std::cout << "对比push_back和emplace_back的效率" << std::endl;
        std::cout << "push_back"<<std::endl;
        std::vector<MyString> vStr;
        // 预先分配，否则整个 vector 在容量不够的情况下重新分配内存
        vStr.reserve(100);
        // 将元素增加到末尾
        vStr.push_back(MyString("can ge ge blog"));
    }
    {
        std::cout << "emplace_back" << std::endl;
        std::vector<MyString> vStr;
        // 预先分配，否则整个 vector 在容量不够的情况下重新分配内存
        vStr.reserve(100);
        vStr.emplace_back("hello world");
    }
    return 0;
}
/*
对比 push_back 和 emplace_back 的效率
push_back
construct:can ge ge blog
copy construct:can ge ge blog
deconstruct:can ge ge blog
deconstruct:can ge ge blog
emplace_back
construct:hello world
deconstruct:hello world
*/
从运行结果行， emplace_back 只调用一次构造和析构，其 效率 不言而喻
  • erase : 擦除元素
    • 移除位于 pos 的元素
    • 移除范围 [first,last] 中的元素
  • pop_back : 移除莫末元素
  • resize : 改变容器中可存储元素的个数
    • 参数:
    • count ：容量的大小
    • value ：用以初始化新元素的值
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	vector<int> a = { 1,2,3 };
	for (const auto& el : a)
	{
		cout << el << " ";
	}
	cout << endl;
	// 增加大小，多余的赋值为 0
	a.resize(5);
	for (const auto& el : a)
	{
		cout << el << " ";
	}
	cout << endl;
	// 添加到 7，赋值为 6
	a.resize(7,6);
	for (const auto& el : a)
	{
		cout << el << " ";
	}
	cout << endl;
}
/*
1 2 3
1 2 3 0 0
1 2 3 0 0 6 6
*/
  • swap : 交换内容
将内容以及容器与 other 交换， 不 在单独的元素上调用任何移动，复制或交换操作
# deque
deque 双端队列，允许在它的首尾快速插入语删除，在 deque 任一端插入或删除都不会使指向其余元素的指针或引用失效。 deque 的存储按需自动扩展及收缩
# 元素访问
  • at : 访问 指定 的元素，同时进行越界检查
  • operator[] : 访问指定的元素
  • front : 访问 第一个 元素
  • back : 访问 最后一个 元素
# 迭代器
  • begin/cbegin ：返回指向起始的迭代器
  • end/cend ：返回指向末位的迭代器
  • rbegin/crbegin : 返回指向起始的逆向迭代器
  • rend/crend : 返回指向末尾的逆向迭代器
# 容量
  • empty : 检查容器是否为空
  • size : 返回容纳的元素数
  • max_size : 返回可容纳的最大元素数 (根据系统或库实现限制的容器可保有的元素最大数量)，此值通常反应容器大小的理论极限
  • shrink_to_fit ：通过释放未使用的内存减少内存的使用
# 修改器
  • clear : 清楚内容
  • insert : 插入元素
  • emplace ：原位构造元素
  • erase : 擦除元素
  • push_back ：将元素添加到容器末尾
  • emplace_back ：将容器末尾就地构造元素
  • pop_back : 移除末元素
  • pop_front ：移除首元素
  • push_front ：插入元素到容器起始
  • emplace_front ：在容器头部原位构造元素
  • resize : 改变容器中可存储元素的个数
  • swap : 交换内容
#include <iostream>
#include <deque>
using namespace std;
int main(void)
{
	deque<int> a = { 1,2,3,4,5 };
	//
	a.push_back(6);
	a.push_front(5);
	// 打印
	for (int n : a)
	{
		cout << n << " ";
	}
	cout << endl;
	a.pop_back();
	a.pop_front();
	for (int n : a)
	{
		cout << n << " ";
	}
	cout << endl;
	return 0;
}
/*
5 1 2 3 4 5 6
1 2 3 4 5
*/
# forward_list
forward_list 支持从容器中的 任何位置 快速插入和移除元素的容器，不支持快速随机访问。它实现为 单链表 ，且实质上与其在 C 中实现相比无任何开销，与 list 相比，此容器不需要双向迭代中提供更有效利用空间的存储
# 元素访问
  • front : 访问第一个元素
# 迭代器
  • before_begin\cbefore_begin : 返回指向第一个元素之前的迭代器
  • begin/cbegin : 返回指向起始的迭代器
  • end/cend : 返回指向末位的迭代器
# 容量
  • empty: 检查容器是否为空
  • max_size: 返回可容纳的最大元素数
# 修改器
  • clear : 清楚内容
  • insert_after : 在某个元素后插入新元素
    • 参数:
    • pos : 内容将其插入到其后的迭代器
    • value : 要插入的元素值
    • count : 要插入的副本数
    • first,last ：要插入的元素范围
    • ilist : 插入值来源 initializer_list
  • emplace_after ：在元素后原位构造元素
  • erase_after ：擦除元素后的元素
    • 参数；
    • pos : 指向前驱要移除元素的迭代器
    • first,last 要移除的元素范围
  • push_front : 插入元素到容器起始
  • emplace_front ：在容器头部构造元素
  • pop_front : 移除首元素
  • resize : 改变容器中可存储元素的个数
  • swap : 交换内容
#include <iostream>
#include <forward_list>
#include <string>
#include <vector>
using namespace std;
// 重载输出
template<typename T>
ostream& operator<<(ostream& s, const forward_list<T>& v)
{
	s.put('[');
	char comma[3] = { '\0',' ,','\0' };
	for (const auto& e : v)
	{
		s << comma << e;
		comma[0] = ', ';
	}
	return s << ']';
}
int main(void)
{
	forward_list<string> words{ "the","forgurt","is","alse","cursed" };
	cout << "words:" << words << endl;
	auto beginIn = words.begin();
	words.insert_after(beginIn, "strawberry");
	// insert_after (3)
	auto anotherIt = beginIn;
	++anotherIt;
	anotherIt = words.insert_after(anotherIt, 2, "strawberry");
	std::cout << "words: " << words << '\n';
	// insert_after (4)
	std::vector<std::string> V = { "apple", "banana", "cherry" };
	anotherIt = words.insert_after(anotherIt, V.begin(), V.end());
	std::cout << "words: " << words << '\n';
	// insert_after (5)
	words.insert_after(anotherIt, { "jackfruit", "kiwifruit", "lime", "mango" });
	std::cout << "words: " << words << '\n';
	// 更改元素个数
	words.resize(6);
	std::cout << "words: " << words << '\n';
	// 移除首元素
	words.pop_front();
	std::cout << "words: " << words << '\n';
	// 从容器中移除指定元素
	words.erase_after(words.begin());
	std::cout << "words: " << words << '\n';
	//
	words.emplace_after(words.begin(), "hello");
	std::cout << "words: " << words << '\n';
	// 清除元素
	words.clear();
	return 0;
}
/*
words:[the ,forgurt ,is ,alse ,cursed]
words: [the ,strawberry ,strawberry ,strawberry ,forgurt ,is ,alse ,cursed]
words: [the ,strawberry ,strawberry ,strawberry ,apple ,banana ,cherry ,forgurt ,is ,alse ,cursed]
words: [the ,strawberry ,strawberry ,strawberry ,apple ,banana ,cherry ,jackfruit ,kiwifruit ,lime ,mango ,forgurt ,is ,alse ,cursed]
words: [the ,strawberry ,strawberry ,strawberry ,apple ,banana]
words: [strawberry ,strawberry ,strawberry ,apple ,banana]
words: [strawberry ,strawberry ,apple ,banana]
words: [strawberry ,hello ,strawberry ,apple ,banana]
*/
# 操作
  • merge : 合并两个已排序列表，链表以升序排序，不复制元素，并且操作后容器 other 会变 为空 ，
  • splice_afte r: 从另一个 forward_list 移动元素
    • 参数:
    • pos ：指向将插入内容到其后的元素的迭代器
    • other : 移动内容来源的另一个容器
    • it 指向从 other 移动到 * this 的元素的迭代器的前驱迭代器
    • first,last ，从 other 移动到 * this 的元素范围
  • remove/remove_if : 移除满足特定标准的元素
    • 参数:
    • value - 要移除的元素的值
    • p 若应移除该元素则返回 true 的一元谓词
  • reverse : 将该链表的所有元素顺序反转
  • unique : 删除连续的重复元素
  • sort : 对元素进行排序
#include <iostream>
#include <forward_list>
#include <list>
using namespace std;
ostream& operator<<(ostream& ostr, const forward_list<int>& list)
{
	for (auto& i : list)
	{
		ostr << " " << i;
	}
	return ostr;
}
int main(void)
{
	forward_list<int> list1 = { 5,9,1,3,3,3,9};
	forward_list<int> list2 = { 8,7,2,3,4,5 };
	forward_list<int> list3 = { 66,99,33 };
	// 对列表排序
	list1.sort();
	list2.sort();
	cout << "list1" << list1 << endl;
	cout << "list2" << list2 << endl;
	list1.merge(list2); // 合并后 list2 为空
	cout << "合并后" << list1 << endl;
	// 插入
	list1.splice_after(list1.cbegin(), list3,list3.cbegin(), list3.cend());
	cout << "插入后" << list1 << endl;
	// 移除满足条件的值
	list1.remove(1);// 移除等于 1 的
	cout << "移除1后" << list1 << endl;
	// 移除 n 大于 10 的
	list1.remove_if([](int n) { return n > 10; });
	cout << "移除大于10后" << list1 << endl;
	// 将所有元素反转
	list1.reverse();
	cout << "列表反转后：" << list1 << endl;
	// 删除重复元素
	list1.unique();
	cout << "去重后：" << list1 << endl;
	return 0;
}
/*
list1 1 3 3 3 5 9 9
list2 2 3 4 5 7 8
合并后 1 2 3 3 3 3 4 5 5 7 8 9 9
插入后 1 99 33 2 3 3 3 3 4 5 5 7 8 9 9
移除 1 后 99 33 2 3 3 3 3 4 5 5 7 8 9 9
移除大于 10 后 2 3 3 3 3 4 5 5 7 8 9 9
列表反转后： 9 9 8 7 5 5 4 3 3 3 3 2
去重后： 9 8 7 5 4 3 2
*/
# list
支持 常量 时间从容器任何位置插入和移除元素的容器。它通常实现为双向链表
# 元素访问
  • front : 访问第一个元素
  • back : 访问最后一个元素
# 迭代器
  • begin/cbegin : 返回指向起始的迭代器
  • end/cend : 返回指向末尾的迭代器
  • rbegin/crbegin : 返回指向起始的逆向迭代器
  • rend/crend : 返回指向末尾的逆向迭代器
# 容量
  • empty : 检查容器是否为空
  • size : 返回容纳的元素数
  • max_size : 返回可容纳的最大元素数
# 修改器
  • clear : 清楚内容
  • insert : 插入元素
  • emplace ：原位构造元素
  • erase ：擦除元素
  • push_back : 在元素添加到容器末尾
  • emplace_back ：在容器末尾就地构造元素
  • pop_back ；移除末元素
  • push_front : 插入元素到容器起始
  • emplace_front ：在容器头部构造元素
  • pop_front : 移除首元素
  • resize : 改变容器中可存储元素的个数
  • swap : 交换内容
# 操作
  • merge : 合并 两个已排序 列表
  • splice : 从另一个 list 中移动元素
  • remove/remove_if : 移除满足特定标准的元素
  • reverse : 将该链表的所有元素顺序 反转
  • unique : 删除连续的 重复 元素
  • sort : 对元素进行排序
参考资料:
cppreference