数据结构基本操作

发表于 2024-03-13 更新于 2024-10-18 分类于算法刷题阅读次数：本文字数： 3.5k 阅读时长 ≈ 13 分钟

本文主要记录在刷题过程中遇到的一些未掌握或者不熟悉的基本操作

数组

vector是c++中的一个容器，可以用来存储数组。vector的使用方法和数组类似，但是vector的长度是可以动态变化的。vector的长度可以通过size()方法获取。
.begin()和.end()分别返回数组的首地址和尾地址。在c++中，数组的首地址是数组的第一个元素的地址，尾地址是数组的最后一个元素的下一个地址。因此，数组的长度为end() - begin()。
.rbegin()和.rend()分别返回数组的尾地址和首地址。
sort()1、reverse()2遵循的是左闭右开的原则，即[begin, end)。类似的还有fill()、copy()、unique()、lower_bound()、upper_bound()。
- fill()3将数组的元素全部赋值为某个值，fill(begin, end, value)。
- copy()4将一个数组的元素复制到另一个数组中，copy(begin1, end1, begin2)。
- unique()5去除数组中的重复元素，unique(begin, end)。
- lower_bound()6查找数组中第一个大于等于某个值的元素的地址，lower_bound(begin, end, value)。
- upper_bound()7查找数组中第一个大于某个值的元素的地址，upper_bound(begin, end, value)。

`sort()`函数

sort()函数是数组的一个方法，用于对数组元素进行排序。默认排序顺序是根据字符串Unicode码点——即按照字母顺序进行排序。如果需要按照其他标准进行排序，就需要提供比较函数。

默认使用方法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
    sort(v.begin(), v.end());
    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

输出结果为1 1 3 4 5 9。

自定义比较函数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
    sort(v.begin(), v.end(), cmp);
    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

上文中的sort()函数使用了自定义的比较函数cmp，该函数返回a > b，即从大到小的顺序对数组进行排序。输出结果为9 5 4 3 1 1。

lambda表达式

lambda表达式是一种匿名函数，可以用来替代比较函数，它是c++11的新特性。一个lambda表达式的一般形式如下：
[capture](parameters) -> return-type {body}如：[](int a, int b) { return a > b; }，其中capture是捕获列表，parameters是参数列表，return-type是返回类型，body是函数体。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });
    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

上文中的sort()函数使用了lambda表达式，即[](int a, int b) { return a > b; }，该表达式返回a > b，即从大到小的顺序对数组进行排序。输出结果为9 5 4 3 1 1。

`reverse()`函数

reverse()对数组元素进行逆序。默认使用方法如下：

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
    reverse(v.begin(), v.end());
    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

输出结果为9 5 1 4 1 3。

`fill()`函数

fill()用于将数组的元素全部赋值为某个值。默认使用方法如下：

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
    fill(v.begin(), v.end(), 0);
    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

输出结果为0 0 0 0 0 0。

`copy()`函数

copy()函数将一个数组的元素复制到另一个数组中。默认使用方法如下：


int main() {
    vector<int> v1 = {3, 1, 4, 1, 5, 9};
    vector<int> v2(6);
    copy(v1.begin(), v1.end(), v2.begin());
    for (int i : v2) {
        cout << i << " ";
    }
    return 0;
}

输出结果为3 1 4 1 5 9。

`unique()`函数

unique()用于去除数组中的重复元素。默认使用方法如下：

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i : v) {
        cout << i << " ";
    }
    return 0;
}

输出结果为1 3 4 5 9。

`lower_bound()`函数

lower_bound()用于查找数组中第一个大于等于某个值的元素的地址。默认使用方法如下：

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};
    cout << lower_bound(v.begin(), v.end(), 3) - v.begin() << endl;
    return 0;
}

输出结果为2。

`upper_bound()`函数

upper_bound()用于查找数组中第一个大于某个值的元素的地址。默认使用方法如下：

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};
    cout << upper_bound(v.begin(), v.end(), 3) - v.begin() << endl;
    return 0;
}

输出结果为3。

链表

链表的基本操作

哈希表

无论是unordered_map还是unordered_set，它们都是基于哈希表实现的。哈希表是一种高效的数据结构，可以在O(1)的时间复杂度内完成插入、删除和查找操作。在C++中，unordered_map和unordered_set是STL中提供的两种无序关联容器，它们分别用于存储键值对和唯一元素的集，都可以使用以下方法：

insert()插入元素。
find()查找元素。
erase()删除元素。
size()返回元素个数。
empty()判断是否为空。
clear()清空所有元素。
count()查找元素个数，也可以用来判断元素是否存在。

unordered_map

unordered_map是C++标准模板库（STL）中提供的一个无序映射容器，它用于存储键值对。unordered_map中的元素没有按照键值排序，而是根据键的哈希值组织成桶，以允许通过键值快速访问单个元素。

构造unordered_map

// 默认构造函数
unordered_map<int, string> myMap;

// 使用initializer list构造
unordered_map<string, int> myMap = {{"key1", 1}, {"key2", 2}};

// 使用迭代器构造
unordered_map<int, string> myMap(otherMap.begin(), otherMap.end());

// 使用拷贝构造函数
unordered_map<int, string> myMap(otherMap);

插入元素

myMap.insert({1, "hello"});  // 使用insert()方法插入元素
myMap[2] = "world";  // 使用[]操作符插入元素
myMap.emplace(3, "goodbye");  // 使用emplace()方法插入元素

查找元素

auto it = myMap.find(1);
if (it != myMap.end()) {  //使用find()方法查找元素
  cout << it->second << endl; // 输出 "hello"
}

string value = myMap[2]; // value = "world"  使用[]操作符查找元素

string value = myMap.at(3); // value = "goodbye" 使用at()方法查找元素

// 使用count()方法查找元素,返回0或1，表示是否存在该键值对。
if (myMap.count(4)) {
  cout << "key 4 exists" << endl;
}

删除元素


myMap.erase(1); // 使用erase()方法删除元素
myMap[2] = ""; // // 使用[]操作符删除元素,value = ""，删除键值对
myMap.clear(); // 使用clear()方法删除所有元素

遍历

// 使用迭代器遍历
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
  cout << it->first << " " << it->second << endl;
}

// 使用范围for循环遍历
for (auto& [key, value] : myMap) {
  cout << key << " " << value << endl;
}

for (auto& pair : myMap) {
  cout << pair.first << " " << pair.second << endl;
}

unordered_set

unordered_set 是 C++ 标准模板库(STL)提供的 another 一种无序关联容器，用于存储 唯一元素的集，与 unordered_map 不同点主要在于以下：

unordered_set 中的元素是唯一的，而 unordered_map 中的元素是键值对。
unordered_set 中的元素没有键的概念，元素本身即是键值。
unordered_set 中的元素不会按照任何特定顺序排列。

构造unordered_set

和unordered_map的构造方法类似，只是unordered_set中只有键没有值。

unordered_set<int> mySet;  // 默认构造函数
unordered_set<int> mySet = {1, 2, 3};  // 使用initializer list构造
unordered_set<int> mySet(otherSet.begin(), otherSet.end());  // 使用迭代器构造
unordered_set<int> mySet(otherSet);  // 使用拷贝构造函数

插入元素

1 2	mySet.insert(1); // 使用insert()方法插入元素 mySet.emplace(2); // 使用emplace()方法插入元素

查找元素

auto it = mySet.find(1);  // 使用find()方法查找元素
if (it != mySet.end()) {
  cout << *it << endl;  // 输出 "1"
}

if (mySet.count(2)) {  // 使用count()方法查找元素
  cout << "2 exists" << endl;
}

删除元素

1 2	mySet.erase(1); // 使用erase()方法删除元素 mySet.clear(); // 使用clear()方法删除所有元素

遍历

// 使用迭代器遍历
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
  cout << *it << endl;
}

// 使用范围for循环遍历
for (auto& value : mySet) {
  cout << value << endl;
}

字符串

可以使用string来定义字符串变量。string类提供了很多方法来操作字符串，例如size()、empty()、clear()、append()、insert()、erase()、replace()、find()、substr()等。

常用方法

size()：获取字符串的长度。
empty()：判断字符串是否为空。
clear()：清空字符串。
push_back()：在字符串末尾添加字符。
pop_back()：删除字符串末尾的字符。
append()：在字符串末尾添加字符串。
insert()：在字符串的某个位置插入字符串。
erase()：删除字符串的某个子串。
replace()：替换字符串的某个子串。
find()：查找字符串中的某个子串。
substr()：获取字符串的子串。

int main() {
    string s = "hello";
    cout << s.size() << endl;  // 输出 5
    cout << s.empty() << endl;  // 输出 0
    s.clear();
    cout << s.empty() << endl;  // 输出 1

    s.push_back('h');
    s.push_back('e');
    s.push_back('l');
    s.push_back('l');
    s.push_back('o');
    cout << s << endl;  // 输出 "hello"

    s.pop_back();
    cout << s << endl;  // 输出 "hell"

    s = "hello";
    s.append(" world");
    cout << s << endl;  // 输出 "hello world"

    s.insert(5, " C++"); // 在位置5插入字符串
    cout << s << endl;  // 输出 "hello C++ world"

    s.erase(5, 4);      // 删除位置5开始的4个字符
    cout << s << endl;  // 输出 "hello world"

    s.replace(6, 5, "C++");// 从位置6开始替换5个字符
    cout << s << endl;  // 输出 "hello C++"

    cout << s.find("C++") << endl;  // 输出 6

    cout << s.substr(6, 3) << endl;  // 从位置6开始截取3个字符，输出 "C++"

    return 0;
}

stringstream

stringstream是C++标准库中的一个类，用于在内存中读写字符串。可以被视为一个输入/输出设备，可以使用<<和>>操作符来读写数据。stringstream常用于将字符串转换为数字，或者将数字转换为字符串。

`<<`和`>>`操作符

<<操作符用于将数据写入stringstream；
>>操作符用于从stringstream中读取数据，会按照空格、制表符、换行符等空白字符分隔数据，不输出空白字符，也可自定义分隔符。

int main() {
    stringstream ss;
    //字符串拼接
    ss << "hello" << " " << "world";
    string s;
    ss >> s;
    cout << s << endl;  // 输出 "hello"

    //字符串转数字
    ss.str("");  // 清空stringstream
    ss << "1 2 3";
    int a, b, c;
    ss >> a >> b >> c;
    cout << a << " " << b << " " << c << endl;  // 输出 "1 2 3"
    //数字转字符串
    ss.str("");  // 清空stringstream
    ss << 123;
    string s;
    ss >> s;
    cout << s << endl;  // 输出 "123"
    //自定义分隔符
    ss.str("");  // 清空stringstream
    ss << "1,2。3&4";
    char ch;
    while (ss >> ch) {
        if (ch == ',' || ch == '。' || ch == '&') {// 自定义分隔符
            cout << " ";
        } else {
            cout << ch;
        }
    }
    cout << endl;  // 输出 "1 2 3 4"
}

栈

栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。在C++中，可以使用stack容器来实现栈。

stack

stack是C++标准模板库（STL）中提供的一个容器适配器，它是基于deque实现的。stack只提供了push()、pop()、top()、empty()、size()等方法，没有提供迭代器。

构造方法：

stack<int> myStack;  // 默认构造函数

deque<int> myDeque = {1, 2, 3};
stack<int> myStack(myDeque);  // 使用deque构造

stack<int> myStack(otherStack);  // 使用拷贝构造函数

其他方法： - push()：插入元素到栈顶。
- pop()：删除栈顶元素。
- top()：访问栈顶元素。
- empty()：判断栈是否为空。
- size()：获取栈的大小。

队列

队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。在C++中，可以使用queue容器来实现队列。

queue

queue是C++标准模板库（STL）中提供的一个容器适配器，它是基于deque实现的。queue只提供了push()、pop()、front()、back()、empty()、size()等方法，没有提供迭代器。

构造方法：

queue<int> myQueue;  // 默认构造函数

deque<int> myDeque = {1, 2, 3};
queue<int> myQueue(myDeque);  // 使用deque构造

queue<int> myQueue(otherQueue);  // 使用拷贝构造函数

其他方法： - push()：插入元素到队尾。
- pop()：删除队头元素。
- front()：访问队头元素。
- back()：访问队尾元素。
- empty()：判断队列是否为空。
- size()：获取队列的大小。

双端队列

双端队列（deque）是一种具有队列和栈的性质的数据结构，它支持在队头和队尾进行插入和删除操作。在C++中，可以使用deque容器来实现双端队列。

构造方法：

deque<int> myDeque;  // 默认构造函数

deque<int> myDeque(5);  // 创建大小为5的deque，元素值为0

deque<int> myDeque(5, 1);  // 创建大小为5的deque，元素值为1

vector<int> myVector = {1, 2, 3};

deque<int> myDeque(myVector.begin(), myVector.end());  // 使用vector构造

deque<int> myDeque(otherDeque);  // 使用拷贝构造函数

其他方法： - push_front()：插入元素到队头。
- push_back()：插入元素到队尾。
- pop_front()：删除队头元素。
- pop_back()：删除队尾元素。
- front()：访问队头元素。
- back()：访问队尾元素。
- empty()：判断双端队列是否为空。
- size()：获取双端队列的大小。

优先队列

优先队列是一种特殊的队列，它的插入操作和删除操作的时间复杂度都是O(logN)，其中N是队列中元素的个数。在C++中，可以使用priority_queue容器来实现优先队列。

priority_queue是C++标准模板库（STL）中提供的一个容器适配器，它是基于vector实现，提供了push()、pop()、top()、empty()、size()等方法，没有提供迭代器。

构造方法：

priority_queue<int> myPriorityQueue;  // 默认构造函数

vector<int> myVector = {1, 2, 3};
priority_queue<int> myPriorityQueue(myVector.begin(), myVector.end());  // 使用vector构造

priority_queue<int> myPriorityQueue(otherPriorityQueue);  // 使用拷贝构造函数

其他方法： - push()：插入元素到优先队列。
- pop()：删除优先队列中的最大元素。
- top()：访问优先队列中的最大元素。
- empty()：判断优先队列是否为空。
- size()：获取优先队列的大小。

自定义比较函数

priority_queue默认是大顶堆，即根节点是最大值。如果需要使用小顶堆，可以通过自定义比较函数来实现。

struct cmp {            // 自定义比较函数
  bool operator()(int a, int b) {
    return a < b;
  }
};

priority_queue<int, vector<int>, cmp> myPriorityQueue;  // 使用自定义比较函数

经典例题：

数组

sort()函数

默认使用方法

自定义比较函数

lambda表达式

更多用法

reverse()函数

fill()函数

copy()函数

unique()函数

lower_bound()函数

upper_bound()函数

链表

链表的基本操作

哈希表

unordered_map

构造unordered_map

插入元素

查找元素

删除元素

遍历

unordered_set

构造unordered_set

插入元素

查找元素

删除元素

遍历

字符串

常用方法

stringstream

<<和>>操作符

栈

stack

队列

queue

双端队列

优先队列

自定义比较函数

`sort()`函数

`reverse()`函数

`fill()`函数

`copy()`函数

`unique()`函数

`lower_bound()`函数

`upper_bound()`函数

`<<`和`>>`操作符