cpp_note

String

• string = vector
• vector的函数string都可以用

字符串（字符数组）的输入输出

1. cin遇到space/enter结束

char line[10];
cin >> line;  //输入 "123 456"
cout << line << endl;  //只能输出 "123"

//string同理
string s;
cin >> s;

2. getchar()

• 读取一个字符

vector<int> nums;
int num;
while(cin >> num) {
	nums.push_back(num);
	// 读到换行符，终止循环
	if(getchar() == '\n') {
		break;
	}
}

3. getline(cin, str)

• 读取一行，且输入结束后丢弃最后的换行符

• 头文件<string>

string s;
getline(cin, s);
// 输出读入的字符串
cout << s << endl;

获取字符串长度

• sizeof()

得到指针占用的字节数 = 4

• strlen(char* s)

在计算字符数组(char str[ ])时，一般用strlen()函数

• s.size() / length()

计算字符串（string）长度，不能用char*作为参数。

除此之外，size()函数还可以获取vector类型的长度。

裁切

s.substr(int pos, int len)

转int

stoi(str)

把string转为int

拼接

append&+

s1.append("def");
//or
s2 += s3;

替换

replace(pos,len,str)

判断数字/字母

isdigit(c)

isalpha(c)

查找子串

char *strstr(const char *haystack, const char *needle)

返回在 haystack 中第一次出现 needle 字符串的位置，如果未找到则返回 null

获取末尾字符

auto b=a.back();

数学函数<math.h>

乘方

double pow(double x, double y): x^y

标准库<limits.h>

max/min

CHAR_MAX	char最大值
INT_MAX
LLONG_MAX
CHAR_MIN	char最小值
INT_MIN
LLONG_MIN

cout << "char: "<< CHAR_MAX << endl;

常用方法<algorithm.h>

翻转

reverse(a, a+n);//n为数组中的元素个数
reverse(str.begin(), str.end());//string

排序

sort(vec.begin(), vec.end()); //默认升序

//自定义排序
bool cmp_max(int x,int y){
	return x > y; //降序
}
sort(arr.begin(),arr.end(),cmp_max); 

链表

• 必须自定义构造函数，默认构造函数无法赋值

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

哈希表

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

集合set

• 构造函数：创建一个空的 unordered_set。

  std::unordered_set<int> uset;

• 插入元素：使用 insert() 方法。

  uset.insert(10);

• 查找元素：使用 find() 方法。

  auto it = uset.find(10);
  if (it != uset.end()) {
    // 元素存在
  }

• 删除元素：使用 erase() 方法。

  uset.erase(10);

• 大小和空检查：使用 size() 和 empty() 方法。

  size_t size = uset.size();
  bool isEmpty = uset.empty();

• 清空容器：使用 clear() 方法。

  uset.clear();

字典map

• 包含头文件:

  #include <map>

• 声明 map 容器:

  std::map<key_type, value_type> myMap;
  
  std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}};

  • key_type 是键的类型。
  • value_type 是值的类型。

• 插入元素:

  myMap[key] = value;

• 访问元素:

  value = myMap[key];

• 遍历map:

  std::map<std::string, int> employees;
  // 遍历 map 并打印员工信息
  for (std::map<std::string, int>::iterator it = employees.begin(); it != employees.end(); ++it) {
  	std::cout << it->first << " is " << it->second << " years old." << std::endl;
  }

• 查找键find：

  auto it = myMap.find(2); // 查找键为2的元素
  if (it != myMap.end()) {
      std::cout << "Found: " << it->second << std::endl;
  }

• 删除元素：使用 erase() 方法。

  umap.erase(key);

• 大小：使用 size()。

  size_t size = umap.size();

• 清空容器：使用 clear() 方法。

  umap.clear();

map自定义排序

• map-value排序

  //map value排序
  bool compare(const pair<string,int>& a,const pair<string,int>& b){
  	if(a.second==b.second)return a.first<b.first;
          else return a.second>b.second;
  }
  map<string,int> m{{"a",1},{"b",2},{"c",3}};
  
  vector<pair<string,int>> v(m.begin(),m.end());//将map中的元素拷贝到vector中
  sort(v.begin(),v.end(),compare);//实现value的排序

• map-key排序

  //自定义map的key排列顺序
  map<string,int,greater<string>> m1;
  struct myCompare {
   bool operator()(const string& l, const string& r)const
   {
    return l.length() > r.length();
   }
  };
  map<string,int,myCompare> m2;

• 注意：在class内定义cmp函数需要加static

  错误解决方法：error: reference to non-static member function must be called-CSDN博客

堆、栈、队列

栈

#include<stack>

• 初始化

  std::stack<Type> s;

• push(): 在栈顶添加一个元素。

• pop(): 移除栈顶元素。

• top(): 返回栈顶元素的引用，但不移除它。

• empty(): 检查栈是否为空。

• size(): 返回栈中元素的数量。

队列

#include <queue>

• 初始化

  std::queue<Type> q;

• empty(): 检查队列是否为空。

• size(): 返回队列中的元素数量。

• front(): 返回队首元素的引用。

• back(): 返回队尾元素的引用。

• push(): 在队尾添加一个元素。

• pop(): 移除队首元素。

双端队列

<deque>

• ```c++ std::deque dq;

  - `push_back()`：在队列尾部添加元素。
  - `push_front()`：在队列头部添加元素。
  - `pop_back()`：移除队列尾部的元素。
  - `pop_front()`：移除队列头部的元素。
  - `empty()`: 检查队列是否为空。
  - `size()`: 返回队列中的元素数量。
  - `front()`: 返回队首元素的引用。
  - `back()`: 返回队尾元素的引用。
  - `clear()`：移除所有元素，使 deque 为空。
  - `erase(pos)`：移除指定位置的元素。
  
  
  
  #### 优先队列 (堆)
  
  `priority_queue< type, container, function>`
  
  + 初始化
  
    ```c++
     std::priority_queue<int> pq; 

• empty(): 检查队列是否为空。

• size(): 返回队列中的元素数量。

• top(): 返回队列顶部的元素（不删除它）。

• push(): 向队列添加一个元素。

• pop(): 移除队列顶部的元素。

自定义优先级

默认最大堆

struct compare {		// 也可以class compare{ public: ...}
    bool operator()(int a, int b) {
        return a > b; // 定义最小堆
    }
};
// 创建一个自定义类型的优先队列，使用最小堆
std::priority_queue<int, std::vector<int>, compare> pq_min;

// or
priority_queue<int,vector<int>,greater<int>> small_heap;

vector

#include <vector>

初始化

vector<int> myVector; // 空 vector
vector<int> myVector(5); // 创建一个包含 5 个整数的 vector，每个值都为默认值（0）
vector<int> myVector(5, 10); // 创建一个包含 5 个整数的 vector，每个值都为 10
vector<int> vec2 = {1, 2, 3, 4}; // 初始化一个包含元素的 vector

vector<int> v3(v.begin()+1, v.end()-1);

扩容/缩容

vector.resize (5, 0); //初始化容量5和初值0

添加/插入元素

myVector.push_back(7); // 将整数 7 添加到 vector 的末尾

//插入
auto it1 = a.begin(); 
auto it2 = a.insert((it1+1), {6, 7, 8});

访问元素

int x = myVector[0]; // 获取第一个元素
int y = myVector.at(1); // 获取第二个元素
int p = myVector.back()//最后一个元素

获取元素个数

int size = myVector.size(); // 获取 vector 中的元素数量

迭代

for (auto it = myVector.begin(); it != myVector.end(); ++it) {
    cout << *it << " ";
}

or

for (int element : myVector) {
    std::cout << element << " ";
}

删除

myVector.erase(myVector.begin() + 2); // 删除第三个元素
int p = myVector.pop_back() // 移除末尾
myVector.clear(); // 清空 vector

list 双向链表

不需要在创建时指定大小，并且可以在任何位置添加或删除元素，而不需要重新分配内存。相比vector，插入或删除元素更快

• 头文件：#include <list>

• 声明列表：std::list<T> mylist;

• 插入元素：

  • mylist.push_back(value);
  • `push_front()

• 删除元素：

  • pop_back();
  • `pop_front()
  • erase(iterator);

• 访问元素：不支持随机访问

  • mylist.front();
  • mylist.back();

• 遍历列表：使用迭代器

  • for (auto it = mylist.begin(); it != mylist.end(); ++it)

  begin()		// 返回指向容器中第一个元素的双向迭代器。
  end()		// 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
  rbegin()	// 返回指向最后一个元素的反向双向迭代器。
  rend()		// 返回指向第一个元素所在位置前一个位置的反向双向迭代器。

• 容器容量

  • size()

pair

#include <utility>

pair<T1, T2> p1;            
pair<T1, T2> p1(v1, v2);   

p1 < p2;   // 依次比较first,second
p1 == p2；   
    
p1.first;                   
p1.second;