STL学习笔记

标签：std 容器 iterator 迭代 STL 元素笔记学习键值

STL介绍
STL序列式容器
STL关联式容器
无序关联式容器
- - 无序容器（哈希容器）是什么
  - C++无序容器自定义哈希函数和排序方式
容器适配器
迭代器适配器
算法

STL介绍

什么是STL

STL 位于各个 C++ 的头文件中，即它并非以二进制代码的形式提供，而是以源代码的形式提供
STL是容器、算法和其他组件的集合

泛性编程

占位符，使用了泛型的代码称为模板
C++ 中，用以支持泛型应用的就是标准模板库 STL，它提供了 C++ 泛型设计常用的类模板和函数模板

STL基本组成

容器：用来封装数据结构的模板类
算法：包含数据结构算法的模板函数，在 std 命名空间中定义，其中大部分算法都包含在头文件<algorithm>中，少部分位于头文件<numeric>中
迭代器：对容器中数据的读和写，是通过迭代器完成的
函数对象：如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）
适配器：可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起
内存分配器：为容器类模板提供自定义的内存申请和释放功能

STL序列式容器

什么是STL容器

容器是模板类的集合，容器中封装的是组织数据的方法
STL有三类标准容器：序列容器、排序容器、哈希容器，后两类也被称为关联容器
容器种类和功能

什么是迭代器

迭代器类型
- 输入迭代器和输出迭代器比较特殊，它们不是把数组或容器当做操作对象，而是把输入流/输出流作为操作对象
- 前向迭代器，支持++p、p++，*p操作
- 双向迭代器，还支持--p、p--
- 随机访问迭代器，还支持p+=i、p-=i、p[i]
不同容器的迭代器
- array、vector是随机访问迭代器
- list、set、map是双向迭代器
迭代器定义方式

什么是序列式容器

类型
- array<T, N>：数组容器，用来存储N个T类型的元素，长度固定不变
- vector<T>：向量容器，长度可变，尾部插入元素O(1)
- deque<T>：双端队列容器，头部和尾部插入都是O(1)
- list<T>：链表容器，用双向链表组织元素，插入方便，访问慢（从头开始访问）
- forward_list<T>：正向链表容器，用单向链表组织，比list块、节省内存
容器常见的函数成员
- begin()，返回指向容器第一个元素的迭代器
- end()，指向容器最后一个元素后一个位置的迭代器
- rbegin()，返回指向最后一个元素的迭代器
- sort()，序列式容器不会自动进行排序，要手动调用sort

array容器

特点：大小固定，无法动态扩展，只允许访问和替换
定义方式
```
std::array<double, 10> values
```

初始化

std::array<double, 10> values {0.5,1.0,1.5,,2.0}

访问

1.values[4] = values[3] + 2.O*values[1]; %不安全
2.values.at(i) = i; %安全
3.get<n>(values); %n必须是常量，使用的是get<n>模板函数

基于范围的遍历

读

for (double x : prices)
	std::cout << x << std::endl;

写

for (double &x : prices)
	x = x * 0.80;

表示首元素地址
```
value.begin()
&value[0]
value.data()
```

vector容器

特点：array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除

设置内存分配

values.reserve(20) #分配至少容纳20个元素的内存

初始化

std::vector<double> values(num, value) #num个value值

独特之处
- push_back进行初始化
- 当vector容器容量发生变化时，所有元素可能会被复制或移动到新的内存地址，需要重新初始化迭代器
访问元素同array
容量和大小
- capacity()是指在不分配更多内存的情况下，容器可以保存的最多元素个数
- size()是指容器实际所包含的元素个数

emplace_back和push_back区别

push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）;
而emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。
emplace_back执行效率更高

指定位置插入元素
- insert() 函数的功能是在 vector 容器的指定位置插入一个或多个元素

emplace() 每次只能插入一个元素。在插入元素时，是在容器的指定位置直接构造元素，而不是先单独生成，再将其复制（或移动）到容器中。因此，在实际使用中，推荐大家优先使用 emplace()。
删除

vector<bool>
- vector<bool>不是容器，底层是用一个bit位来存储元素
- 避免是用vector<bool>，可以使用deque<bool>替代

deque容器

特点：和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，并且更重要的一点是， deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。当需要向序列两端频繁的添加或删除元素时，应首选 deque 容器。
因为元素不是存储在连续内存空间中，所以最好不要用指针去访问deque容器

访问第一个和最后一个元素

values.front() = 10; %访问首元素
values.back() = 20; %访问最后一个元素

成员方法

list容器

特点：双向链表，如何需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，建议使用 list 容器存储序列
访问：list 容器不支持随机访问，未提供下标操作符 [] 和 at() 成员函数，也没有提供 data() 成员函数。通过 front() 和 back() 成员函数，可以分别获得 list 容器中第一个元素和最后一个元素的引用形式
添加元素：

删除元素

splice方法
- 将其它list容器中的元素，添加到当前list容器指定位置处
```
void splice(iterator position, list &x)
```
empty和size都可以判断容器为空，用empty更好

STL关联式容器

特点：存储的元素是键值对，并且默认根据键值大小做升序排序，底层用红黑树来存储键值对

pair容器

定义和初始化

# 1.构造函数
pair <string, string> pair1("1","2"); 
# 2.拷贝构造函数
pair <string, string> pair3(pair2);
# 3.移动构造函数
pair <string, string> pair4(make_pair("1", "2")); #make_pair返回一个临时pair对象

取键：pair1.first，取值：pair1.second
swap函数：用来交换两个pair对象的键值对
```
pair1.swap(pair2);
```

map容器

特点：使用 map 容器存储的各个键值对，键的值既不能重复也不能被修改，该容器存储的都是pair<const K, T>类型

定义和初始化

std::map<std::string, int>myMap{ {"C 语言教程",10},{"STL 教程",20} };

查找
- find(key) 成员方法，它能帮我们查找指定 key 值的键值对，如果成功找到，则返回一个指向该键值对的双向迭代器
- lower_bound(key) 返回的是指向第一个键不小于 key 的键值对的迭代器；
- upper_bound(key) 返回的是指向第一个键大于 key 的键值对的迭代器
获取键值
- []：只有当 map 容器中确实存有包含该指定键的键值对，借助重载的 [ ] 运算符才能成功获取该键对应的值；反之，若当前 map 容器中没有包含该指定键的键值对，则此时使用 [ ] 运算符将不再是访问容器中的元素，而变成了向该 map 容器中增添一个键值对
```
string cValue = myMap["C 语言教程"];
```
- at：at() 成员方法也需要根据指定的键，才能从容器中找到该键对应的值；不同之处在于，如果在当前容器中查找失败，该方法不会向容器中添加新的键值对，而是直接抛出 out_of_range 异常
```
cout << myMap.at("C 语言教程") << endl;
```
- find：返回迭代器，当 find() 方法查找失败时，其返回的迭代器指向的是容器中最后一个键值对之后的位置，即不指向任何有意义的键值对

插入

不指定pos，返回键值对

ret = mymap.insert({ "C 语言教程","http://c.biancheng.net/c/" });

指定pos，返回迭代器

std::map<string, string>::iterator it = mymap.begin();
//向 it 位置以普通引用的方式插入 STL
auto iter1 = mymap.insert(it, STL);

插入其他容器指定区域内的所有键值对

std::map<string, string>::iterator first = ++mymap.begin();
std::map<string, string>::iterator last = mymap.end();
//将<first,last>区域内的键值对插入到 copymap 中 
copymap.insert(first, last);

插入多个键值对

mymap.insert({ {"STL 教程", "http://c.biancheng.net/stl/"}, { "Java 教程","http://c.biancheng.net/java/" } });

insert的增添效率更高，[]的更新效率更高

emplace
```
pair<map<string, string>::iterator, bool> ret = mymap.emplace("STL 教程", "http://c.biancheng.net/stl/");
```
- 当该方法将键值对成功插入到 map 容器中时，其返回的迭代器指向该新插入的键值对，同时 bool 变量的值为 true
- 当插入失败时，则表明 map 容器中存在具有相同键的键值对，此时返回的迭代器指向此具有相同键的键值对，同时 bool 变量的值为 false。
emplace_hint
- 该方法不仅要传入创建键值对所需要的数据，还需要传入一个迭代器作为第一个参数，指明要插入的位置（新键值对键会插入到该迭代器指向的键值对的前面）
- 该方法的返回值是一个迭代器，而不再是 pair 对象。当成功插入新键值对时，返回的迭代器指向新插入的键值对；反之，如果插入失败，则表明 map 容器中存有相同键的键值对，返回的迭代器就指向这个键值对
- 在实现向 map 容器中插入键值对时，应优先考虑使用 emplace() 或者 emplace_hint()

按key排序

指定升序

std::map<std::string, int, std::less<std::string> >myMap{ {"C 语言教程",10},{"STL 教程",20}};

指定降序

std::map<std::string, int, std::greater<std::string> >myMap{ {"C 语言教程",10},{"STL 教程",20}};

multimap容器

特点：和 map 容器的区别在于，multimap 容器中可以同时存储多（≥2）个键相同的键值对
方法：
- insert
- erase
- emplace
- emplace_hint
- count(key)
- find(key)

set容器

特点：使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等

定义和初始化

std::set<std::string> myset{"http://c.biancheng.net/java/", "http://c.biancheng.net/stl/","http://c.biancheng.net/python/"};

自定义关联式容器的排序方式

使用函数对象类来自定义排序

class cmp {
	public:
	//重载 () 运算符
	bool operator ()(const string &a,const string &b) {
    //按照字符串的长度，做升序排序(即存储的字符串从短到长)
    return (a.length() < b.length());
    }
};

int main() {
	//创建 set 容器，并使用自定义的 cmp 排序规则
	std::set<string, cmp>myset{"http://c.biancheng.net/stl/", 	 "http://c.biancheng.net/python/","http://c.biancheng.net/java/"};

修改关联式容器中键值对的键

map 和 multimap 容器只能采用“先删除，再添加”的方式修改某个键值对的键

借助const_cast，可以直接修改set和multiset容器中元素的非键部分

class student {
    public:
    student(string name, int id, int age) :name(name), id(id), age(age){
    }
    const int& getid() const {
        return id;
    }
    void setname(const string name){
        this->name = name;
    }
}

class cmp {
    public:
    bool operator ()(const student &stua, const student &stub) {
        //按照字符串的长度，做升序排序(即存储的字符串从短到长)
        return stua.getid() < stub.getid();
    }
};

set<student, cmp> myset{ {"zhangsan",10,20},{"lisi",20,21},{"wangwu",15,19} };

//*iter会调用operator*，其返回的是一个 const T&类型元素，用const_cast去掉常	  量限定
set<student>::iterator iter = mymap.begin();
const_cast<student&>(*iter).setname("xiaoming");

无序关联式容器

无序容器（哈希容器）是什么

区别
- 关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
- 无序容器的底层实现采用的是哈希表的存储结构。
特点
- 无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键
- 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。
选择
- 实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器
- 反之，如果更多的操作是通过键获取对应的值，则应首选无序容器
类型
- unordered_map、unordered_multimap
- unordered_set、unordered_multiset

C++无序容器自定义哈希函数和排序方式

假设我们想创建一个可存储 Person 类对象的 unordered_set 容器，考虑到 Person 为自定义的类型，因此默认的 hash 哈希函数不再适用，这时就需要以函数对象类的方式自定义一个哈希函数

使用函数对象类实现自定义哈希函数

class hash_fun {
    public:
    int operator()(const Person &A) const {
    	return A.getAge();
    }
};

std::unordered_set<Person, hash_fun> myset；

容器适配器

什么是容器适配器

容器适配器，就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用，即通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。

stack容器适配器

无迭代器，访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素

queue容器适配器

无迭代器，访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素

priority_queue

优先级队列，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest out”原则
可以自定义排序方式，在插入或者删除时会自动按照排序方式重新排列

迭代器适配器

迭代器适配器，其本质也是一个模板类，该模板类是借助以上 5 种基础迭代器实现的

reverse_iterator反向迭代器

特点
- 当反向迭代器执行 ++ 运算时，底层的基础迭代器实则在执行 -- 操作，意味着反向迭代器在反向遍历容器；
- 当反向迭代器执行 -- 运算时，底层的基础迭代器实则在执行 ++ 操作，意味着反向迭代器在正向遍历容器。
定义和初始化

std::reverse_iterator<std::vector<int>::iterator> my_reiter(myvector.end())

插入迭代器

back和front迭代器的使用：

std::forward_list<int> foo;
std::back_insert_iterator< std::vector<int> > back_it(foo);
//将 5 插入到 foo 的末尾
back_it = 5;

insert迭代器的使用：

std::list<int> foo(2,5);
std::list<int>::iterator it = ++foo.begin();
std::insert_iterator<std::list<int>> insert_it (foo,it);
//it 是一个基础迭代器，表示新元素的插入位置

流迭代器

操作对象不再是某个容器，而是流对象。即通过流迭代器，我们可以读取指定流对象中的数据，也可以将数据写入到流对象中

输入流迭代器用于直接从指定的输入流中读取元素

double value1;
//创建表示结束的输入流迭代器
istream_iterator<double> eos;
//创建一个可逐个读取输入流中数据的迭代器，同时这里会让用户输入数据
istream_iterator<double> iit(cin);
//判断输入流中是否有数据
if (iit != eos) {
    //读取一个元素，并赋值给 value1
    value1 = *iit;
}
//如果输入流中此时没有数据，则用户要输入一个；反之，如果流中有数据，iit 迭代器后移一位，做读取下一个元素做准备
iit++;

输出流迭代器用于将数据写到指定的输出流（如 cout）中

//创建一个输出流迭代器
ostream_iterator<string> out_it(cout);
//向 cout 输出流写入 string 字符串
*out_it = "http://c.biancheng.net/stl/";
cout << endl;

//创建一个输出流迭代器，设置分隔符 ,
ostream_iterator<int> out_it1(cout, ",");
//向 cout 输出流依次写入 1、2、3
*out_it1 = 1;
*out_it1 = 2;
*out_it1 = 3;

/*和copy函数连用*/
//创建一个 vector 容器
vector<int> myvector;
//初始化 myvector 容器
for (int i = 1; i < 10; ++i) {
	myvector.push_back(i);
}
//创建输出流迭代器
std::ostream_iterator<int> out_it(std::cout, ", ");
//将 myvector 容器中存储的元素写入到 cout 输出流中
std::copy(myvector.begin(), myvector.end(), out_it);

流缓冲区迭代器

move_iterator移动迭代器

创建

//创建一个 vector 容器
std::vector<std::string> myvec{ "one","two","three" };
//将 vector 容器的随机访问迭代器作为新建移动迭代器底层使用的基础迭代器
typedef std::vector<std::string>::iterator Iter;
//创建并初始化移动迭代器
std::move_iterator<Iter>mIter = make_move_iterator(myvec.begin());

运用移动迭代器为 othvec 容器初始化

//使用的是移动迭代器，其会将myvec容器中的元素直接移动到 othvec 容器中。
vector<string>othvec(make_move_iterator(myvec.begin()), make_move_iterator(myvec.end()));

//创建2个移动迭代器
std::move_iterator<Iter>begin = make_move_iterator(myvec.begin());
std::move_iterator<Iter>end = make_move_iterator(myvec.end());
//通过base方法，获取到当前移动迭代器底层所使用的基础迭代器,以复制的方式初始化 othvec容器
vector <std::string> othvec(begin.base(), end.base());

算法

search函数

语法

//查找 [first1, last1) 范围内，和 [first2, last2) 序列满足 pred 规则的第一个子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2,
                        BinaryPredicate pred);

实例

    //以函数对象的形式定义一个匹配规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return (i%j == 0);
    }
};
int main() {
    vector<int> myvector{ 1,2,3,4,8,12,18,1,2,3 };
    int myarr2[] = { 2,4,6 };
    //调用第二种语法格式
    it = search(myvector.begin(), myvector.end(), myarr2, myarr2 + 3, mycomp2());
}

copy函数

std::vector<int> srce {1, 2, 3, 4};
std::deque<int> dest {5, 6, 7, 8};
std::copy(std::begin(srce), std::end(srce), std::back_inserter(dest));

move函数

std::vector<int> srce {1, 2, 3, 4};
std::deque<int> dest {5, 6, 7, 8};
std::move(std::begin(srce), std::end(srce), std::back_inserter(dest));

标签：std,容器,iterator,迭代,STL,元素,笔记,学习,键值
From： https://www.cnblogs.com/z5onk0/p/16755324.html

STL介绍

什么是STL

泛性编程

STL基本组成

STL序列式容器

什么是STL容器

什么是迭代器

什么是序列式容器

array容器

vector容器

deque容器

list容器

STL关联式容器

pair容器

map容器

multimap容器

set容器

自定义关联式容器的排序方式

修改关联式容器中键值对的键

无序关联式容器

无序容器（哈希容器）是什么

C++无序容器自定义哈希函数和排序方式

容器适配器

什么是容器适配器

stack容器适配器

queue容器适配器

priority_queue

迭代器适配器

reverse_iterator反向迭代器

插入迭代器

流迭代器

流缓冲区迭代器

move_iterator移动迭代器

算法

search函数

copy函数

move函数

相关文章

赞助商

阅读排行