C++数据结构

库函数

：提供标准输入输出流对象，例如cin和cout。
：提供字符串操作函数，例如连接、比较、查找等。
：提供向量容器类模板，用于动态数组操作。
// For srand() and rand()
// For time()

MAP的生成和遍历

unordered_map<int,int> map;
for (auto it = map.begin(); it != map.end(); ++it) {
  if (it->second > max) {
     max = it->second;
     majorityElement = it->first;
  }
 }

构造函数（与结构体同名，冒号后边用于初始化成员变量，大括号用于完成初始化操作如果没有操作可以为空）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

举例

class Person {  
private:  
    std::string name;  
    int age;  
  
public:  
    // 构造函数，接受名字和年龄作为参数  
    Person(std::string n, int a) : name(n), age(a) {  
        // 构造函数体可以留空，因为初始化列表已经完成了初始化工作  
        // 如果需要执行额外的操作，可以在这里添加代码  
    }
}  

STL：vector

构造函数

vector<int> v;                    // 创建一个空的vector  
vector<int> v(10);                // 创建一个含有10个元素的vector，默认初始化为0  
vector<int> v(10, 42);            // 创建一个含有10个元素的vector，每个元素值为42  
vector<int> v2(v);                // 复制构造函数，创建一个v的副本v2  
vector<int> v3(v.begin(), v.end()); // 使用迭代器创建v的一个副本v3

赋值操作

vector<int> v1 = {1, 2, 3};  //int数组初始化int a[3]= {1, 2, 3}
vector<int> v2;  
v2 = v1;                          // 使用赋值运算符复制v1到v2  
vector<int> v3(v1);               // 直接在构造时复制v1到v3（复制构造函数）

访问元素

vector<int> v = {10, 20, 30, 40, 50};  
int first = v[0];                 // 访问第一个元素，值为10  
int last = v.back();              // 访问最后一个元素，值为50  
int at_pos_2 = v.at(2);           // 访问位置为2的元素，并进行边界检查，值为30

迭代器

vector<int> v = {1, 2, 3, 4, 5};  
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {  
    cout << *it << " ";           // 输出1 2 3 4 5   
}  
  
// C++11及之后的版本可以使用范围for循环  
for (int num : v) {  
    cout << num << " ";           // 输出1 2 3 4 5   
}

容量

vector<int> v;  
v.push_back(1);  
cout << v.size() << endl;         // 输出元素数量，值为1  
cout << v.capacity() << endl;     // 输出当前已分配的内存可以容纳的元素数量，至少为1  
v.reserve(10);                    // 预留至少10个元素的空间（不改变size，但可能影响capacity）  
cout << v.capacity() << endl;     // 输出可能增加，但至少为10

修改

vector<int> v = {1, 2, 3};  
v.push_back(4);                   // 在末尾添加元素4，现在v为{1, 2, 3, 4}  
v.pop_back();                     // 移除末尾元素，现在v为{1, 2, 3}  
v.insert(v.begin() + 1, 99);      // 在位置1插入元素99，现在v为{1, 99, 2, 3}  
v1.insert(v1.end(), v2.begin(), v2.end()); // 在v1的末尾插入v2的所有元素  
v.erase(v.begin() + 1);           // 删除位置1的元素，现在v为{1, 2, 3}  
v.clear();                        // 清空vector，现在v为空{}
v.resize(3);                      // 将vector的大小改为3，删除或者添加末尾的元素

在C++中，”reverse”通常指的是将容器（如数组、向量、列表等）中的元素反转顺序，它可以用来反转任何支持双向迭代器的容器。

​ std::reverse(numbers.begin(), numbers.end());

if (rightNode) 判断一个指针式否为空，为空返回false，不为空返回true。

deque（双端队列）经常作为stack和queue的底层容器使用。

1. stack（栈）

stack是一个后进先出（LIFO）的数据结构。在STL中，你可以通过以下方式使用它：

声明和初始化

std::stack<int> s; // 默认使用deque作为底层容器  
std::stack<int, std::vector<int>> s_vec; // 使用vector作为底层容器  
std::stack<int, std::deque<int>> s_deq; // 使用deque作为底层容器（实际上与默认情况相同）

主要成员函数

• push(const value_type& val): 将元素压入栈顶。没有返回值。
• pop(): 删除栈顶元素。没有返回值
• top(): 返回栈顶元素的引用。如果栈不为空，则返回栈顶元素的引用；如果栈为空，则行为是未定义的（通常会导致程序崩溃）。
• empty(): 检查栈是否为空。返回一个布尔值，如果栈为空则返回true，否则返回false。
• size(): 返回栈中元素的数量。返回一个整数

2. queue（队列）

queue是一个先进先出（FIFO）的数据结构。在STL中，你可以通过以下方式使用它：

声明和初始化

std::queue<int> q; // 默认使用deque作为底层容器  
std::queue<int, std::list<int>> q_list; // 使用list作为底层容器  
std::queue<int, std::deque<int>> q_deq; // 使用deque作为底层容器（实际上与默认情况相同）

主要成员函数

• push(const value_type& val): 将元素添加到队列末尾。

• pop(): 删除队列的第一个元素。

  • front(): 返回队列的第一个元素的引用。

• back(): 返回队列的最后一个元素的引用（注意：这不是标准队列操作，但在STL的queue中提供）。

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

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

3. deque（双端队列）

虽然你提到的是stack和queue，但deque是一个独立的容器，它支持在两端进行插入和删除操作。它可以用作stack和queue的底层容器。

声明和初始化

cpp复制代码

std::deque<int> d;

主要成员函数

• push_front(const value_type& val): 在双端队列的前端插入元素。
• push_back(const value_type& val): 在双端队列的末尾插入元素。
• pop_front(): 删除双端队列的第一个元素。
• pop_back(): 删除双端队列的最后一个元素。
• front(): 返回双端队列的第一个元素的引用。
• back(): 返回双端队列的最后一个元素的引用。
• empty(): 检查双端队列是否为空。
• size(): 返回双端队列中元素的数量。

哈希数据

• set（集合）
• map(映射)

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

重点关注实现方式以及查询效率，所以一般情况下我们都使用unordered_set和unordered_map可以提升效率。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
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)

构造函数

unordered_map<string, int> ageMap; // 创建一个unordered_map，键为string类型，值为int类型

map.insert(make_pair("Alice", 30))

或者使用map[j] = i; 的语法来插入或更新元素，这里的 map 是一个 unordered_map 的变量名，j 是键（key），i 是值（value）。

插入与更新：如果该键 j 已经存在于 unordered_map 中，则 map[j] = i; 会更新该键对应的值为 i。如果该键 j 不存在，它会在 unordered_map 中插入一个新元素，键为 j，值为 i。

查找

auto it = ageMap.find("Charlie");  
if (it != ageMap.end()) {  
  // 找到了  
  cout << "Charlie's age: " << it->second << endl;  
} else {  
  // 没找到  
  cout << "Charlie not found" << endl;  
}

当你有一个指向map或unordered_map中元素的迭代器it时：

• it->first 表示当前元素（键值对）的键。
• it->second 表示当前元素（键值对）的值。

string字符串

在C++中，std::string是一个非常有用的类，它表示可变长度的字符串。这个类提供了许多方法来操作字符串。以下是一些常用的std::string成员函数：

1. 构造函数和析构函数

   • string(): 构造一个空的字符串
   • string(const string& str): 拷贝构造函数

2. 访问和修改

   • at(size_t pos): 通过索引访问字符，同时进行范围检查
   • front(): 返回字符串的第一个字符
   • back(): 返回字符串的最后一个字符
   • +=: 连接字符串或字符
   • append(): 在字符串末尾添加字符或字符串
   • push_back(char c): 在字符串末尾添加一个字符
   • insert(): 在指定位置插入字符或字符串
   • erase(): 删除从指定位置开始的特定数量的字符
   • replace(): 替换字符串中的一部分
   • swap(): 交换两个字符串的内容
   • clear(): 清空字符串内容

3. 字符串信息

   • size() / length(): 返回字符串的长度
   • empty(): 检查字符串是否为空
   • capacity(): 返回当前分配的存储空间的大小
   • reserve(): 预留一定的存储空间
   • resize(): 改变字符串的大小

4. 查找和比较

   • find(): 查找子字符串或字符的位置

5. 其他实用函数

   • substr(): 返回一个新的字符串，它是此字符串的一个子字符串
   • c_str(): 返回一个指向正规C字符串的指针, 内容与本字符串相同
   • get_allocator(): 返回配置器

添加字符

// 方法2: 使用 + 运算符
str1 += str2.substr(0, 3); // 添加 str2 的前三个字符到 str1

reserve(): 函数确实遵循左闭右开原则。这是 C++ 标准库中许多函数共有的范围

链表

struct ListNode {
    int val; // 节点存储的数据
    ListNode *next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};

整行字符串输入

while (getline(cin, s)) {
    // 接受⼀整⾏字符串
    for(int i = 0; i < s.size();i++) 
    { 
        //遍历字符串
    }
}
getchar(); 

一行不确定输入

for (int i = 0; i < n; ++i) {
       std::cout << "Enter line " << (i + 1) << ": ";
       std::string line;
       std::getline(std::cin, line);

       std::istringstream iss(line);
       std::vector<int> lineData;

       int num;
       while (iss >> num) {
           lineData.push_back(num);
       }

//（1）输入数字：
while(cin>>i){
 
     cout<<i<<endl;
}
//（2）输入字符串：
while(getline(cin,s)){
cout<<s<<endl;
}

创建二叉树

优先队列

priority_queue<int, vector<int>, greater<int>> pq;

第一个是放入的类型，第二个是存储的方式，第三个是从小到大，less是从大到小

没有遍历只有

priority_queue<int, vector<int>, greater<int>> pq;
pq.push()
pq.top()    
pq.pop() 

自定义比较函数

• 大顶堆：在大顶堆中，父节点的值大于或等于其每个子节点的值。因此，堆的根节点（顶部节点）是堆中的最大值。
• 小顶堆：在小顶堆中，父节点的值小于或等于其每个子节点的值。因此，堆的根节点（顶部节点）是堆中的最小值。

小顶堆的意思是优先队列的头部元素（即队首元素）是最小的。priority_queue默认使用的是大顶堆，也就是说队首元素是最大的

class mycomparison {
public:
    //从头到尾是从小到大
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

//常规的从小到大排序
bool compare(int a, int b) {
    return a < b; // 按照升序排序
}

struct

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};