临时记录_C++容器相关

- [2020-01-10 五 11:53] 第9章顺序容器

vector,随机访问、大小可变、尾部之外插入删除慢、额外空间开销小

deque, 随机访问、大小可变、头尾之外插入删除慢、额外空间开销小

list, 顺序双向访问、大小可变、插入很快、额外空间开销大

forward_list，顺序单向访问、大小可变、插入很快、额外空间开销大

array, 随机访问、固定大小、不能增删、额外空间开销小

string，类似vector、专为字符、额外空间开销小

- <2020-01-12 日 10:56> 9.2 容器库概览

描述容器接口的思路：

1、所有容器通用接口

2、顺序与非顺序容器的特定接口

3、其它特殊容器特殊接口（如string）

类型别名

iterator

const_iterator

size_type

difference_type

value_type

reference

const_reference

构造函数

C c;

C c1(c2);

C c(b,e);

C c{a,b,c...};

赋值与swap

c1=c2;

c1={a,b,c...};

a.swap(b);

swap(a,b);

大小

c.size();

c.max_size();

c.empty();

增删(不适用于array)

c.insert(args);

c.emplace(inits);

c.erase(args)

c.clear();

关系

==,!=,<,<=,>,>=

迭代器

c.begin(),c.end();

c.cbegin(),c.cend();

反向额外成员

reverse_iterator

const_reverse_iterator

c.rbegin(),c.rend():

c.crbegin(),c.crend();

vector<NoDefault> v1(10,init)//对于一个没有默认构造函数的类型NoDefault通过元素初始化器。

容器是模板类，容器元素可以任何甚至可以是另外一个容器类，但是旧版编译器需要在两个尖括号之间加入空格，例如：

vector<vector<string> >;

两个迭代器构成的迭代器范围是左闭右开的，即：[begin,end), end可以与begin是同一个位置(范围为空)，但是不能在begin之前。

两个迭代器可以指向同一个容器中的元素或者最后一个元素之后的位置。

迭代器函数

begin/end这类返回迭代器的函数是被重载的，如果对象是普通变量，返回的是正常的iterator,如果是常量返回的则是const_iterator。

以c开头的函数是C++新引入的，以支持auto,与begin/end一起使用。

带r版本的迭代器是反向的。

- [2019-11-30 六 13:35] 将一个容器初始化为另一个容器的拷贝

容器定义和初始化

//默认构造函数

C c;

//用一个容器创建另一个做为它的拷贝的容器，必须两个容器的类型、以及容器元素类型都一样,array的大小还必须一样。

C c1(c2);

C c1=c2;

//c初始化为初始化列表元素的拷贝，列表元素与容器元素类型必须相同；array时，列表必须不能超过array大小

C c{a,b,c...};

C c={a,b,c...};

//初始化为范围中的元素，范围中元素类型必须与C中元素类型相同(不能是array)

C c(b,e);

//只适合顺序容器

C seq(n);//n个元素进行值初始化，构造函数是explicit的（即阻止自动隐式转换）（不能是string）

C seq(n,t);//n个元素，初始化为值t

用一个容器创建另一个做为它的拷贝的容器，必须两个容器的类型、以及容器元素类型都一样,array的大小还必须一样。

list<string> list2(authors);

用迭代器范围来初始化容器类型和容器元素的类型都可以不同，因为直接替换了容器原来的元素。

deque<string> authList(authors.begin(),it);//包括[begin(),it)迭代器范围

用列表初始化，列表隐含了被初始化容器的大小。

list<string> authors = {"one", "two", "three"};

除array外，初始化列表赋值之后，元素大小变为初始化列表大小（数组则要求初始化列表大小小于数组）。

顺序容器相关,如果没有默认构造函数，必须用两个参数的，第二个参数提供默认值；如果有默认构造函数，则只需要传递元素数目也行。

vector<int> ivec(10,-1);//10个元素，每个值-1

forward<int> ivec(10);//10个元素，每个值0

注：上面的例子中，authors是list。

- 9.2.5 赋值和swap

c1=c2;

c={a,b,c...};

swap(c1,c2);

c1.swap(c2);

seq.assign(b,e);

seq.assign(il);

seq.assign(n,t);

大小是array类型的一个部分：

array<int,10> size_type i;

所以array构造函数是不应当有大小参数的。

与内置数组不同，array可以赋值和初始化，不过使用其它数组赋值的时候，要求数组类型匹配（大小、元素类型）

array<int,10> ia2={0,1,2,3,4,5,6,7,8,9};

array<int,10> ia3={42};

array<int,10> ia4=ia3;

如果列表初始化，则列表大小需要小于数组，并且剩余的元素要有相应的默认构造函数来进行默认初始化。

注：花括号初始化列表只能初始化赋值，不能初始化之后，再用花括号对数组进行赋值。非数组可以用花括号赋值。

assign只用于除了array之外的顺序容器。允许从不同但相容类型赋值

由于是旧元素被替换，传递给assign的迭代器不能指向调用assign的容器。

<2020-01-13 一 13:21> 使用swap

除array之外，swap不会导致元素拷贝、删除、插入。swap后，string的迭代器会失效，数组的迭代器会指向原来的位置（但是元素已经被置换了），而其它的迭代器也会被置换(各自仍指向原来被换的元素）。

<2020-01-14 二 10:59> 比较

容器比较必须保证元素类型和容器类型是相同的，并且只有元素也定义了比较运算才能使用运算符号对容器进行比较。

- 9.3 容器操作

插入相关

//尾部追加,forwardlist不支持

c.push_back(t);//值为t的元素

c.emplace_back(args);//args创建的元素

//头部创建,vector与string不支持

c.push_front(t);

c.emplace_front(args);

//指定位置之前的插入,forwardlist不支持下面的而是有自己专用的insert和emplace

c.insert(p,t);//在p迭代器对应元素之前插入值为t的元素

c.emplace(p,args);

c.insert(p,n,t);//n个值为t的元素

c.insert(p,b,e);//迭代器范围[b,e)

c.insert(p,il);//花括号元素列表il

对象插入或初始化容器后，容器中的对应元素与对象并无关系，对象只是拷贝，类似传值调用。

emplace直接在容器管理的空间中创建对象而不拷贝对象,emplace参数必须与元素类型构造函数参数匹配，

访问相关

访问成员函数返回的是引用

front()是首元素（begin())，back是尾元素（end()-1),forwardlist不支持back();

c.front(),c.back();

下标操作和at()可以随机访问，下标需要程序员自己注意越界情况，而at()会在越界的时候自动抛出相关的out_of_range错误

c[n],c.at(n);

删除相关

//forwardlist不支持erase，它有自己专用的删除函数

//下面操作改变容器大小所以不支持array

c.pop_back();//删除尾元素，forwardlist不支持

c.pop_front();//删除首元素，vector和string不支持

c.erase(p);//删除p所指向的元素(p是迭代器）

c.erase(b,e);//删除[b,e)范围内的元素

c.clear();//删除所有元素

forwardlist特殊的函数

//特殊的迭代器

lst.before_begin();//首元素之前不存在的元素迭代器

lst.cbefore_begin();

//特殊的插入

lst.insert_after(p,t);

lst.insert_after(p,n,t);

lst.insert_after(p,b,e);

lst.insert_after(p,il);

emplace_after(p,args);

//特殊的删除

lst.erase_after(p);

lst.erase_after(b,e);

- <2020-01-14 二 11:50> 9.3.5改变容器大小

c.resize(n);

c.resize(n,t);

- 9.3.6 容器操作可能会使迭代器失效

插入、删除都可能导致容器迭代器失效，不同容器情况不同（比如vector、list等）具体参考相关位置。

大致情况如下：

对于插入，

指向list/forwardlist的引用、指针、迭代器都不会失效；

vector/string若重新分配则指针、引用、迭代器全失效，若未重新分配则插入之前的引用、指针、迭代器不会失效；

deque插入首尾之外则指针、引用、迭代器全失效，插入首尾则迭代器失效但是指向存在的指针、引用不会失效。

对于删除，

指向被删元素的迭代器、指针、引用全都失效；

指向list/forwardlist其它位置的引用、指针、迭代器都不会失效；

deque删除首尾之外则其它元素指针、引用、迭代器全失效，删除尾部则尾后迭代器失效其它不失效，删除首部则其它都不会被影响。

指向vector/string被删除元素之前的指针、引用、迭代器都有效。

只要删除元素，尾后迭代器都失效。

对于vector/string/deque，为防止失效，循环中操作容器后需要更新迭代器、引用、指针。

insert()/erase()均会返回新迭代器，用它更新迭代器即可。

类似如下这样进行：

inter= vi.insert(...);

inter= vi.erase(....);

不要在循环外保存c.end()返回的尾迭代器做为判断，而直接每次使用新的返回值

类似如下这样进行：

while(begin != v.end())

{...}

- 9.4 vector对象是如何增长的

vector元素连续，增加元素会导致重新分配空间，移动所有元素，所以通过一定策略预先给它分配多余的预留空间，防止频繁移动所有元素。

capacity()告诉我们不重新分配内存（扩张）的情况下可以容纳多少个元素；reserve告诉我们它应当预留准备保存的元素数目。

c.shrink_to_fit();//将capacity减少到与size（即实际的元素数）同样大小。

c.capacity();//最大能保存的元素数目，超过则重新分配内存。

c.reserve(n);//预留n的空间，不改变容器元素数量，仅影响vector预先分配多大的空间。

当需求大于当前容量，reserve才会改变vector容量，至少会分配与需求一样大的空间；当需求小于等于当前容量，reservse什么都不做并且小于时也并不会退回多余的空间。当调用reserve之后，capacity空间大小会大于等于传给reserve的参数。

总之，reserve不会减少容器占用的空间。类似地，resize只减少容器元素数目而不是容器容量，也不能用它减少预留空间。

shrink_to_fit()会要求退回多余空间，但是实际也不保证一定退回。

<2020-01-19 日 12:15> capacity和size

- [2020-03-17 二 11:48] 9.5额外的string操作

创建函数：使用const char*创建string对象时，如果未指定创建的大小或者指定的大小大于const char*字符数目，那么const char*必须以NULL空字符结束，否则不用。

string(s), string(s,pos), string(s,pos,n)

substr(pos), substr(pos,n)

修改字符串的操作：insert(),erase(),assign(),append(),replace()

搜索函数:返回string:size_typ类型，是下标，没有匹配则返回最大值npos的static成员。

find(),rfind(),find_first_of(),find_last_of(),find_first_not_of(),find_last_not_of()

比较函数: compare()

数值转换：to_string(val),stoi(),stol(),stoul(),stoll(),stoull(),stof(),stod(),stold()- [2020-01-10 五 11:53] 第9章顺序容器

vector,随机访问、大小可变、尾部之外插入删除慢、额外空间开销小

deque, 随机访问、大小可变、头尾之外插入删除慢、额外空间开销小

list, 顺序双向访问、大小可变、插入很快、额外空间开销大

forward_list，顺序单向访问、大小可变、插入很快、额外空间开销大

array, 随机访问、固定大小、不能增删、额外空间开销小

string，类似vector、专为字符、额外空间开销小

- <2020-01-12 日 10:56> 9.2 容器库概览

描述容器接口的思路：

1、所有容器通用接口

2、顺序与非顺序容器的特定接口

3、其它特殊容器特殊接口（如string）

类型别名

iterator

const_iterator

size_type

difference_type

value_type

reference

const_reference

构造函数

C c;

C c1(c2);

C c(b,e);

C c{a,b,c...};

赋值与swap

c1=c2;

c1={a,b,c...};

a.swap(b);

swap(a,b);

大小

c.size();

c.max_size();

c.empty();

增删(不适用于array)

c.insert(args);

c.emplace(inits);

c.erase(args)

c.clear();

关系

==,!=,<,<=,>,>=

迭代器

c.begin(),c.end();

c.cbegin(),c.cend();

反向额外成员

reverse_iterator

const_reverse_iterator

c.rbegin(),c.rend():

c.crbegin(),c.crend();

vector<NoDefault> v1(10,init)//对于一个没有默认构造函数的类型NoDefault通过元素初始化器。

容器是模板类，容器元素可以任何甚至可以是另外一个容器类，但是旧版编译器需要在两个尖括号之间加入空格，例如：

vector<vector<string> >;

两个迭代器构成的迭代器范围是左闭右开的，即：[begin,end), end可以与begin是同一个位置(范围为空)，但是不能在begin之前。

两个迭代器可以指向同一个容器中的元素或者最后一个元素之后的位置。

迭代器函数

begin/end这类返回迭代器的函数是被重载的，如果对象是普通变量，返回的是正常的iterator,如果是常量返回的则是const_iterator。

以c开头的函数是C++新引入的，以支持auto,与begin/end一起使用。

带r版本的迭代器是反向的。

- [2019-11-30 六 13:35] 将一个容器初始化为另一个容器的拷贝

容器定义和初始化

//默认构造函数

C c;

//用一个容器创建另一个做为它的拷贝的容器，必须两个容器的类型、以及容器元素类型都一样,array的大小还必须一样。

C c1(c2);

C c1=c2;

//c初始化为初始化列表元素的拷贝，列表元素与容器元素类型必须相同；array时，列表必须不能超过array大小

C c{a,b,c...};

C c={a,b,c...};

//初始化为范围中的元素，范围中元素类型必须与C中元素类型相同(不能是array)

C c(b,e);

//只适合顺序容器

C seq(n);//n个元素进行值初始化，构造函数是explicit的（即阻止自动隐式转换）（不能是string）

C seq(n,t);//n个元素，初始化为值t

用一个容器创建另一个做为它的拷贝的容器，必须两个容器的类型、以及容器元素类型都一样,array的大小还必须一样。

list<string> list2(authors);

用迭代器范围来初始化容器类型和容器元素的类型都可以不同，因为直接替换了容器原来的元素。

deque<string> authList(authors.begin(),it);//包括[begin(),it)迭代器范围

用列表初始化，列表隐含了被初始化容器的大小。

list<string> authors = {"one", "two", "three"};

除array外，初始化列表赋值之后，元素大小变为初始化列表大小（数组则要求初始化列表大小小于数组）。

顺序容器相关,如果没有默认构造函数，必须用两个参数的，第二个参数提供默认值；如果有默认构造函数，则只需要传递元素数目也行。

vector<int> ivec(10,-1);//10个元素，每个值-1

forward<int> ivec(10);//10个元素，每个值0

注：上面的例子中，authors是list。

- 9.2.5 赋值和swap

c1=c2;

c={a,b,c...};

swap(c1,c2);

c1.swap(c2);

seq.assign(b,e);

seq.assign(il);

seq.assign(n,t);

大小是array类型的一个部分：

array<int,10> size_type i;

所以array构造函数是不应当有大小参数的。

与内置数组不同，array可以赋值和初始化，不过使用其它数组赋值的时候，要求数组类型匹配（大小、元素类型）

array<int,10> ia2={0,1,2,3,4,5,6,7,8,9};

array<int,10> ia3={42};

array<int,10> ia4=ia3;

如果列表初始化，则列表大小需要小于数组，并且剩余的元素要有相应的默认构造函数来进行默认初始化。

注：花括号初始化列表只能初始化赋值，不能初始化之后，再用花括号对数组进行赋值。非数组可以用花括号赋值。

assign只用于除了array之外的顺序容器。允许从不同但相容类型赋值

由于是旧元素被替换，传递给assign的迭代器不能指向调用assign的容器。

<2020-01-13 一 13:21> 使用swap

<2020-01-14 二 10:59> 比较

容器比较必须保证元素类型和容器类型是相同的，并且只有元素也定义了比较运算才能使用运算符号对容器进行比较。

- 9.3 容器操作

插入相关

//尾部追加,forwardlist不支持

c.push_back(t);//值为t的元素

c.emplace_back(args);//args创建的元素

//头部创建,vector与string不支持

c.push_front(t);

c.emplace_front(args);

//指定位置之前的插入,forwardlist不支持下面的而是有自己专用的insert和emplace

c.insert(p,t);//在p迭代器对应元素之前插入值为t的元素

c.emplace(p,args);

c.insert(p,n,t);//n个值为t的元素

c.insert(p,b,e);//迭代器范围[b,e)

c.insert(p,il);//花括号元素列表il

对象插入或初始化容器后，容器中的对应元素与对象并无关系，对象只是拷贝，类似传值调用。

emplace直接在容器管理的空间中创建对象而不拷贝对象,emplace参数必须与元素类型构造函数参数匹配，

访问相关

访问成员函数返回的是引用

front()是首元素（begin())，back是尾元素（end()-1),forwardlist不支持back();

c.front(),c.back();

下标操作和at()可以随机访问，下标需要程序员自己注意越界情况，而at()会在越界的时候自动抛出相关的out_of_range错误

c[n],c.at(n);

删除相关

//forwardlist不支持erase，它有自己专用的删除函数

//下面操作改变容器大小所以不支持array

c.pop_back();//删除尾元素，forwardlist不支持

c.pop_front();//删除首元素，vector和string不支持

c.erase(p);//删除p所指向的元素(p是迭代器）

c.erase(b,e);//删除[b,e)范围内的元素

c.clear();//删除所有元素

forwardlist特殊的函数

//特殊的迭代器

lst.before_begin();//首元素之前不存在的元素迭代器

lst.cbefore_begin();

//特殊的插入

lst.insert_after(p,t);

lst.insert_after(p,n,t);

lst.insert_after(p,b,e);

lst.insert_after(p,il);

emplace_after(p,args);

//特殊的删除

lst.erase_after(p);

lst.erase_after(b,e);

- <2020-01-14 二 11:50> 9.3.5改变容器大小

c.resize(n);

c.resize(n,t);

- 9.3.6 容器操作可能会使迭代器失效

插入、删除都可能导致容器迭代器失效，不同容器情况不同（比如vector、list等）具体参考相关位置。

大致情况如下：

对于插入，

指向list/forwardlist的引用、指针、迭代器都不会失效；

vector/string若重新分配则指针、引用、迭代器全失效，若未重新分配则插入之前的引用、指针、迭代器不会失效；

deque插入首尾之外则指针、引用、迭代器全失效，插入首尾则迭代器失效但是指向存在的指针、引用不会失效。

对于删除，

指向被删元素的迭代器、指针、引用全都失效；

指向list/forwardlist其它位置的引用、指针、迭代器都不会失效；

deque删除首尾之外则其它元素指针、引用、迭代器全失效，删除尾部则尾后迭代器失效其它不失效，删除首部则其它都不会被影响。

指向vector/string被删除元素之前的指针、引用、迭代器都有效。

只要删除元素，尾后迭代器都失效。

对于vector/string/deque，为防止失效，循环中操作容器后需要更新迭代器、引用、指针。

insert()/erase()均会返回新迭代器，用它更新迭代器即可。

类似如下这样进行：

inter= vi.insert(...);

inter= vi.erase(....);

不要在循环外保存c.end()返回的尾迭代器做为判断，而直接每次使用新的返回值

类似如下这样进行：

while(begin != v.end())

{...}

- 9.4 vector对象是如何增长的

vector元素连续，增加元素会导致重新分配空间，移动所有元素，所以通过一定策略预先给它分配多余的预留空间，防止频繁移动所有元素。

capacity()告诉我们不重新分配内存（扩张）的情况下可以容纳多少个元素；reserve告诉我们它应当预留准备保存的元素数目。

c.shrink_to_fit();//将capacity减少到与size（即实际的元素数）同样大小。

c.capacity();//最大能保存的元素数目，超过则重新分配内存。

c.reserve(n);//预留n的空间，不改变容器元素数量，仅影响vector预先分配多大的空间。

总之，reserve不会减少容器占用的空间。类似地，resize只减少容器元素数目而不是容器容量，也不能用它减少预留空间。

shrink_to_fit()会要求退回多余空间，但是实际也不保证一定退回。

<2020-01-19 日 12:15> capacity和size

- [2020-03-17 二 11:48] 9.5额外的string操作

string(s), string(s,pos), string(s,pos,n)

substr(pos), substr(pos,n)

修改字符串的操作：insert(),erase(),assign(),append(),replace()

搜索函数:返回string:size_typ类型，是下标，没有匹配则返回最大值npos的static成员。

find(),rfind(),find_first_of(),find_last_of(),find_first_not_of(),find_last_not_of()

比较函数: compare()

数值转换：to_string(val),stoi(),stol(),stoul(),stoll(),stoull(),stof(),stod(),stold()