程序设计思维第二周笔记（图片可以看附件）

博主： grinrain
发布时间：2022 年 03 月 02 日
1404次浏览
8 条评论
1803字数
分类：程序设计思维与实践

# **算法**

```
//将比较方法作为结构体的成员函数
 #include <bits/stdc++.h>
 using namespace std;
 
 struct point
 {
     int x, y, z;
     /*
     规则 
     x小
     y大
     z小 
     */
     bool operator < (const point &b) const
     {
         if( x != b.x)
             return x < b.x;
         else if( y != b.y)
             return y > b.y;
         else return z < b.z;
     }
 }
 
 
 int main()
 {
     point p[3] = {{3,2,1}, {2,1,3}, {1,3,2}};
     
     sort(p, p+3);
     
 }
```

```
//将比较方法作为sort函数的第三个参数传入
 #include <bits/stdc++.h>
 using namespace std;
 
 struct point
 {
     int x, y, z;
     /*
     规则 
     x小
     y大
     z小 
     */
 }
 
 bool cmp(point &a, point &b)
 {
     if( x != b.x)
             return x < b.x;
     else if( y != b.y)
             return y > b.y;
     else return z < b.z;
 }
 
 int main()
 {
     point p[3] = {{3,2,1}, {2,1,3}, {1,3,2}};
     
     sort(p, p+3, cmp);
     
 }
```

## **二分相关**

### **lower_bound和upper_bound**

* **传入一个区间（第一个位置和最后一个元素的下一个位置）**`STL表示区间一般用左闭右开`
* **lower_bound可以在指定区间内查找大于等于给定值的第一个位置**
* **upper_bound可以在指定区间内查找大于给定值的第一个位置**
* **如果没有大于等于给定值的位置, lower_bound返回的位置是正无穷，即数组的最后一个元素的下一个位置**
  ```
  int main()
   {
       int a[10] = {1,2,3,4,5,5,5,6,7,8};
       lower_bound(a, a+10, 5);    //4
       upper_bound(a, a+10, 5);    //6
  
       return 0;
   }
  ```

### **unique**

> **unique函数属于STL中比较常用函数，它的功能是元素去重。即******”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了(详细情况，下面会讲)。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。******返回值是一个迭代器，******它指向的是去重后容器中不重复序列的最后一个元素的下一个元素******。**

```
#include <bits/stdc++.h>
 using namespace std;
 
 int main()
 {
     int a[9] = {1,2,3,3,5,3,3,4,4};
     int n = unique(a, a+9) - a; // n的含义是去重后a的长度
     
     for(int i=0; i<n; i++)
     {
         
     } 
     
     return 0;
 }
```

### **next_permutation(课上没有细讲)**

* **生成指定区间的下一个排列，若不存在下一个排列则返回false**

![image-20220302194224069](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302194224069.png?lastModify=1646226106)

# **容器**

### **vector**

```
vector<int> a;  //生成一个有0个元素的vector
 vector<int> b(10, 3);   //生成一个有10个元素，每个元素都是3的vector
 
 
 //遍历方法
 for(int i=0; i<b.size(); i++);
 for(vector<int>::iterator it = b.begin(); it!=a.end(); it++);
 for(auto it = b.begin(); it!=a.end(); it++);
```

#### **C++11新特性: range for**

```
vector<int> a(10, 3);
 //i是a里某个元素的引用, 不加&符号的话i表示元素的拷贝
 //如果不确定容器的类型，可以用auto代替比较保险
 for(auto &i: a)
 {
     cout<< i << " ";
 }
```

#### **插入删除**

* **vector可以在任意位置进行插入删除元素操作，时间复杂度为O(n)**

```

### **list(了解)**

* **链表容器**

![image-20220302201113556](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302201113556.png?lastModify=1646226106)

![image-20220302201127452](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302201127452.png?lastModify=1646226106)

### **deque**

* **虽然内存中地址不是连续的（不同于vector），但是仍然支持vector那样的下标访问**

![image-20220302201338389](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302201338389.png?lastModify=1646226106)

### **string**

![image-20220302201624890](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302201624890.png?lastModify=1646226106)

**不对，s是class， 取地址取不到**

![image-20220302201650946](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302201650946.png?lastModify=1646226106)

**可以这样返回一个指针， 就可以输出了**

**两种构造方法**

```
string s = "1234";
 string s("1234");
```

![image-20220302201925815](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302201925815.png?lastModify=1646226106)

```
//短的小于长的，长度相等按字典序比较
string a = "1234", b = "1233";
cout << (a < b ) << endl;
```

#### **substr**

```
string a = "1233";
cout << a.substr(1, 3) << endl;	//从第1个开始（左闭右开）取3个数
//不加第二个参数默认取到末尾
cout << a.substr(1) << endl;
```

### **set**

* **保证元素的唯一性（插入多个相同的元素没有用）**
* **增删查的复杂度都是O(logn)**
* **不能通过下标访问，只能通过迭代器访问**
* **动态维护元素序列，元素都是按照从小到大排列**
* **访问过程中元素不允许修改，若需修改，需要删除并插入新元素**
* **和map一样，底层实现为红黑树（一种平衡二叉搜索树），基于此可以判断元素大小，对于类需要重载小于号**

![image-20220302202217684](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302202217684.png?lastModify=1646226106)

```
set<int> s;
for(int i=1; i<10; i++)
{
    s.insert(10 - i);
}

for(const int &i: s)
{
    cout << i << ' ';
}
```

![image-20220302202554325](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302202554325.png?lastModify=1646226106)

#### **判断元素是否存在**

```
//find,  count 均为O(n)

//方法一
if(s.find(10) == s.end())
{
    cout << "not found\n";
}

//方法二
if(s.count(10) == 0)
{
    // ...
}
```

### **map**

* **是一个映射**
* **可以通过first, second属性来访问键值**
* **插入O(logn), 遍历O(n)**

#### **和set一样可以通过count来判断元素是否存在**

![image-20220302203652114](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302203652114.png?lastModify=1646226106)

#### **常量map**

* **相当于一个表**

![image-20220302203727600](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302203727600.png?lastModify=1646226106)

### **multimap/multiset**

![image-20220302203947395](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302203947395.png?lastModify=1646226106)

# **容器适配器**

* **本身并不是容器，而是在容器的基础上封装，从而有一些操作**

### **stack**

**push(), pop(), top(), size()**

* **不提供clear()来清除所有元素，因为不能要求其底层容器具有相对应操作，底层容器为deque, 可以为vector, list等**

![image-20220302204442726](file://C:/Users/GrinRain/AppData/Roaming/Typora/typora-user-images/image-20220302204442726.png?lastModify=1646226106)

### **queue & priority_queue**

**front(), pop()**

* **优先队列是一个堆******（默认大根堆）****

```
priority_queue<int> q;
q.push(2);
q.push(3);
q.push(1);

// ...
```

* **变为小根堆**

最后修改：2022 年 03 月 02 日 09 : 08 PM

如果觉得我的文章对你有用，请随意赞赏

8 条评论

wlyzkfqiec
March 2nd, 2025 at 11:35 am

若能对分论点进一步细分，结构会更立体。

回复
njgkyxmbss
March 1st, 2025 at 12:29 am

案例丰富且贴合主题，论证逻辑环环相扣。

回复
egclnkfhsa
January 6th, 2025 at 02:35 pm

哈哈哈，写的太好了https://www.lawjida.com/

回复
cfichasptt
December 7th, 2024 at 09:50 am

《连环杀局1风云花戏楼》动作片高清在线免费观看：https://www.jgz518.com/xingkong/22447.html

回复
xgtmrdvzlx
November 28th, 2024 at 11:53 pm

《口香糖第一季》欧美剧高清在线免费观看：https://www.jgz518.com/xingkong/113044.html

回复
iosvnpidrq
November 27th, 2024 at 08:51 am

《不速之客2014》动作片高清在线免费观看：https://www.jgz518.com/xingkong/93299.html

回复
daddpbnnan
November 16th, 2024 at 05:34 pm

你的文章让我学到了很多知识，非常感谢。 http://www.55baobei.com/YwwIfGOLbr.html

回复
kspsoknxfl
September 23rd, 2024 at 09:42 am

想想你的文章写的特别好https://www.jiwenlaw.com/

回复