顺序容器

容器库是类与算法的汇集

数组

静态的连续数组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)
tuple_element<std::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
- 注意()大于留的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
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_after
- 参数:
- 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
remove/remove_if
reverse反转
unique重复元素
sort

参考资料:
cppreference

STL顺序容器

STL顺序容器

顺序容器

数组

array

头文件

定义

元素访问

迭代器

容器

操作

辅助类

vector

头文件

元素访问

迭代器

容量

修改器

deque

元素访问

迭代器

容量

修改器

forward_list

元素访问

迭代器

容量

修改器

操作

list

元素访问

迭代器

容量

修改器

操作