0%

三次握手

当两台计算机之间建立TCP连接时,它们之间会执行一个称为“三次握手”的过程。这个过程允许双方在通信开始前进行一些必要的协商,确保双方都准备好发送和接收数据。下面是TCP三次握手的详细过程:

TCP三次握手

  1. 第一次握手(SYN)
    • 客户端向服务器发送一个特殊的TCP数据包,称为SYN包(同步序列编号)。这个包包含了一个随机生成的序列号(client_isn),用于后续的数据传输。
    • 客户端将SYN标志位设置为1,表明这是一个连接请求。
  2. 第二次握手(SYN + ACK)
    • 服务器收到客户端发送的SYN包后,会回复一个SYN包和一个ACK包(确认),称为SYN-ACK包。
    • 服务器在SYN-ACK包中将SYN标志位设置为1,表示它接受了客户端的连接请求,并且同时发送一个确认序号(ACK),确认客户端的序列号加1,以表明它准备好接收数据。
  3. 第三次握手(ACK)
    • 客户端收到服务器发送的SYN-ACK包后,会向服务器发送一个确认ACK包。
    • 这个ACK包不包含任何数据,只是用来确认服务器的SYN-ACK包已经收到了。
    • 客户端将确认序号设置为服务器发送的序列号加1。

完成了这个三次握手过程后,TCP连接就建立起来了,双方就可以开始通过这个连接传输数据。此时,双方都知道对方已经准备好了,并且双方也都知道对方的序列号,从而可以保证数据的可靠传输。

需要注意的是,如果在这个过程中的任何一个阶段出现了问题,比如某个数据包丢失或者超时,TCP协议会尝试重新发送数据包或者触发超时重传机制,以确保连接的建立。

四次挥手

TCP连接的四次挥手是在通信结束时,双方关闭连接的过程。它相比于三次握手有更多的细节,因为在这个过程中,每一方都需要确保对方收到了关闭请求,并且双方都知道连接已经关闭。以下是四次挥手的详细过程:

  1. 第一次挥手(FIN)
    • 客户端或服务器其中一方决定关闭连接,发送一个FIN包给对方。
    • FIN包中的FIN标志位被置为1,表示发起方已经没有数据要发送了,但仍能接收数据。
  2. 第二次挥手(ACK)
    • 接收到FIN包的一方(假设为服务器)确认收到了关闭请求,发送一个ACK包作为确认。
    • 这个ACK包通常不会携带任何数据,只是简单地确认收到了FIN包。
  3. 第三次挥手(FIN)
    • 确认收到关闭请求的一方(服务器)也决定关闭连接,向对方发送一个FIN包。
    • 这个FIN包告诉对方它也没有数据要发送了,但仍能接收数据。
  4. 第四次挥手(ACK)
    • 收到第三次挥手的一方(假设为客户端)发送一个ACK包作为确认。
    • 这个ACK包通常不会携带任何数据,只是简单地确认收到了第三次挥手的FIN包。

完成了这个四次挥手过程后,连接就完全关闭了。双方都知道对方已经关闭了连接,不会再发送数据。这样可以确保数据的可靠传输,并且释放了双方的资源,使其可以用于其他连接。

C++11 引入了 lambda 表达式,它是一种用于创建匿名函数的语法。Lambda 表达式提供了一种更加简洁和灵活的方式来编写函数对象,尤其适用于需要传递函数作为参数的情况,比如 STL 算法、函数式编程、事件处理等。

Lambda 表达式的基本语法

Lambda 表达式的一般形式如下:

1
[capture](parameters) -> return_type { body }
  • capture:捕获列表,用于捕获外部变量,可以是值捕获、引用捕获或混合捕获。
  • parameters:参数列表,与普通函数的参数列表类似,可以为空。
  • return_type:返回类型,可以省略,由编译器自动推导。
  • body:函数体,与普通函数体相似,可以包含一系列语句或表达式。

Lambda 表达式的用法示例

  • Lambda 表达式作为函数对象:
1
2
auto sum = [](int a, int b) { return a + b; };
int result = sum(3, 4); // result = 7
  • Lambda 表达式作为 STL 算法的参数:
1
2
std::vector<int> numbers = {1, 2, 3, 4, 5};
int total = std::accumulate(numbers.begin(), numbers.end(), 0, [](int a, int b) { return a + b; });
  • Lambda 表达式与标准库函数配合使用:
1
2
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::for_each(numbers.begin(), numbers.end(), [](int num) { std::cout << num << std::endl; });

Lambda 表达式捕获列表

Lambda 表达式的捕获列表控制了它可以访问的外部变量。捕获列表可以为空,也可以包含一个或多个变量。捕获列表支持值捕获、引用捕获和混合捕获。

  1. 值捕获: 捕获外部变量的值,在 lambda 表达式创建时复制该变量的值。
1
2
int x = 10;
auto func = [x]() { return x; };
  1. 引用捕获: 捕获外部变量的引用,可以修改外部变量的值。
1
2
int y = 20;
auto func = [&y]() { y++; };
  1. 混合捕获: 混合使用值捕获和引用捕获。
1
2
int x = 10, y = 20;
auto func = [&x, y]() { return x + y; };

Lambda 表达式的返回类型推导

在 C++14 中,Lambda 表达式的返回类型可以由编译器根据其返回语句的类型自动推导。

1
auto add = [](int a, int b) { return a + b; };

std::functionstd::bind 是 C++11 标准库中引入的两个重要组件,用于实现函数对象的封装和绑定。它们为 C++ 中的函数式编程提供了更加灵活和方便的方式。可以用于实现回调函数的思想。

std::function

std::function 是一个模板类,用于封装任意可调用对象(函数指针、函数对象、成员函数指针、lambda 表达式等),并提供一种统一的接口来调用这些对象。它可以看作是一个类型安全的函数指针的容器。

特点:

  • std::function 是可调用对象的包装器,它可以存储、复制和调用任何可调用对象。
  • std::function 的类型由其模板参数确定,因此它可以表示各种不同的函数类型。
  • std::function 对象可以在运行时被赋予不同的可调用对象,并且可以被多次复制、传递和调用。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <functional>

void say_hello() {
std::cout << "Hello, world!" << std::endl;
}

int add(int a, int b) {
return a + b;
}

int main() {
std::function<void()> func1 = say_hello;
func1(); // 调用 say_hello 函数

std::function<int(int, int)> func2 = add;
std::cout << "Sum: " << func2(3, 4) << std::endl; // 调用 add 函数

return 0;
}

std::bind

std::bind 是一个函数模板,用于创建一个新的可调用对象。该对象会将参数绑定到函数或函数对象上。它允许延迟绑定参数,以后再调用时传递剩余的参数。

语法:

1
2
3
#include <functional>

auto new_function = std::bind(function, arg1, arg2, ...);
  • function:要绑定的函数或函数指针。
  • arg1, arg2, ...:要绑定到函数的参数。

特点:

  • std::bind 可以绑定函数的部分或全部参数,从而创建一个新的可调用对象。
  • std::bind 返回的可调用对象可以被多次复制、传递和调用。
  • std::bind 可以绑定参数的位置,也可以绑定参数的值,还可以使用占位符 _1_2 等来表示未指定的参数。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <functional>

void greet(const std::string& name, int age) {
std::cout << "Hello, " << name << "! You are " << age << " years old." << std::endl;
}

int main() {
auto greet_function = std::bind(greet, "Alice", std::placeholders::_1);
greet_function(30); // 输出:Hello, Alice! You are 30 years old.

auto add_function = std::bind(std::plus<int>(), std::placeholders::_1, std::placeholders::_2);
std::cout << "Sum: " << add_function(3, 4) << std::endl; // 输出:Sum: 7

return 0;
}

在这个示例中,std::bind 函数用来创建一个新的可调用对象 greet_function,它绑定了 greet 函数的第一个参数为 “Alice”,第二个参数由调用者传入。而另一个可调用对象 add_function 绑定了 std::plus<int>() 函数对象,表示对两个参数进行加法运算。

假设我们有一个事件循环,当某个定时器超时时,我们需要执行一个回调函数,并传递一些参数给这个回调函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <functional>
#include <chrono>
#include <thread>

void callback(const std::string& message, int value) {
std::cout << message << ": " << value << std::endl;
}

int main() {
// 定义一个 std::function 对象,用来存储回调函数
std::function<void()> func;

// 使用 std::bind 创建一个绑定了参数的可调用对象,并将其赋值给 func
func = std::bind(callback, "Callback message", 42);

// 模拟定时器超时,当定时器超时时调用回调函数
std::this_thread::sleep_for(std::chrono::seconds(2));
func(); // 调用回调函数

return 0;
}

function与bind的结合使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <functional>

// 普通函数
void freeFunction(int a) {
std::cout << "Free function called with " << a << std::endl;
}

// 函数对象
struct Functor {
void operator()(int a) const {
std::cout << "Functor called with " << a << std::endl;
}
};

// 成员函数
class MyClass {
public:
void memberFunction(int a) {
std::cout << "Member function called with " << a << std::endl;
}
};

int main() {
// 使用std::function包装普通函数
// std::function<void(int)> func1 = freeFunction;
std::function<void(int)> func1 = std::bind(freeFunction, std::placeholders::_1);
func1(1);

// 使用std::function包装函数对象
// std::function<void(int)> func2 = Functor();
Functor functor;
std::function<void(int)> func2 = std::bind(functor, std::placeholders::_1);
func2(2);

// 使用std::function包装lambda表达式
std::function<void(int)> func3 = [](int a) {
std::cout << "Lambda called with " << a << std::endl;
};
func3(3);

// 使用std::function包装成员函数
MyClass obj;
// std::function<void(MyClass*, int)> func4 = &MyClass::memberFunction;
// func4(&obj, 4);
std::function<void(int)> func4 = std::bind(&MyClass::memberFunction, &obj, std::placeholders::_1);
func4(4);

return 0;
}

占位符std::placeholders

用来表示未绑定的参数。这些占位符在 std::placeholders 命名空间中定义。常见的占位符有:

  • std::placeholders::_1:表示调用时传递的第一个参数。
  • std::placeholders::_2:表示调用时传递的第二个参数。
  • 以此类推,可以使用 _3, _4 ….等表示更多的参数。

举个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <functional>

// 普通函数
void exampleFunction(int a, int b, int c) {
std::cout << "Called with a=" << a << ", b=" << b << ", c=" << c << std::endl;
}

int main() {
// 使用std::bind绑定部分参数
std::function<void(int)> boundFunction = std::bind(exampleFunction, std::placeholders::_1, 100, std::placeholders::_2);

// 调用绑定的函数
boundFunction(10, 20); // 实际调用exampleFunction(10, 100, 20)

return 0;
}
1
std::function<void(int)> boundFunction = std::bind(exampleFunction, std::placeholders::_1, 100, std::placeholders::_2);

这行代码创建了一个新的可调用对象 boundFunction,它绑定了 exampleFunction 的第二个参数 b 为 100,而第一个参数 a 和第三个参数 c 使用占位符 _1_2,表示它们将在调用 boundFunction 时传递。

Reactor模式和Proactor模式是两种常见的事件处理模式,通常用于构建高性能的并发系统。它们都是在事件驱动的系统中使用的设计模式,但它们在处理事件时的方式有所不同。下面我将详细解释它们的工作原理和区别。

Reactor模式

概念:

在Reactor模式中,有一个事件循环(Event Loop),负责监听并分发事件。该循环通过轮询或者异步IO等机制监视多个输入源(如文件描述符、套接字等),当有事件发生时,调用相关的事件处理器来处理这些事件。在Reactor模式中,事件处理是同步的,即当一个事件发生时,Reactor会调用相应的事件处理器,并且一直等待处理器完成处理,然后再继续监听新的事件。

特点:

Reactor模式的主要特点包括:

  1. 单线程:通常Reactor模式在单线程中运行,事件循环会按顺序处理事件。
  2. 同步处理:事件处理是同步的,一个事件处理器处理完事件之后,才会继续处理下一个事件。
  3. 高效:由于采用了非阻塞IO和事件驱动的方式,Reactor模式在高并发场景下表现出色。

单、多Reactor模式:

单Reactor模式中,只有一个事件循环负责监听和分发事件,并且事件处理是同步的,即事件处理器会在事件循环中同步执行。这种模式通常适用于轻量级的应用或者处理较少并发连接的情况。

与单Reactor模式不同,多Reactor模式通过将事件处理分布到多个事件循环中来提高系统的并发能力。每个事件循环负责监听和处理一部分事件,从而降低了单个事件循环的负载,提高了系统的并发处理能力。通常采用主从Reactor模式

​ 在主从Reactor模式中,通常有一个主Reactor负责监听连接请求,并且负责创建和分配子Reactor。当主Reactor接收到连接请求时,会将连接分配给某个子Reactor,然后由子Reactor负责处理该连接的事件。这样可以避免单个Reactor负载过重,并且能够充分利用多核处理器的性能。

回调函数

在Reactor模式中,回调函数被广泛应用于处理事件。回调函数是一种在某个事件发生时被调用的函数,用于处理特定类型的事件。在Reactor模式中,当事件发生时,事件循环会调用相应的回调函数来处理事件,例如读取数据、写入数据、关闭连接等。

具体来说,在多Reactor模式中,每个事件循环都会注册一组回调函数,用于处理不同类型的事件。当事件发生时,事件循环会根据事件的类型找到对应的回调函数,并调用它来处理事件。这样可以实现事件驱动的编程模型,将事件的处理与业务逻辑分离开来,提高了代码的可维护性和可扩展性。

举个例子,假设一个Web服务器使用多Reactor模式来处理客户端连接。每个事件循环会注册一组回调函数,包括处理新连接事件、读取数据事件、写入数据事件等。当有新的客户端连接到达时,主Reactor会接收到连接请求,并将连接分配给某个子Reactor。子Reactor会调用相应的回调函数来处理该连接的读取数据事件和写入数据事件。

Proactor模式

Proactor模式与Reactor模式有所不同。在Proactor模式中,操作(通常是IO操作)被提交给一个专门的组件,称为Proactor,然后由Proactor负责执行这些操作。当操作完成时,Proactor会通知相关的事件处理器,告诉它们操作已完成,可以进行下一步处理。与Reactor模式不同,Proactor模式中的事件处理是异步的,事件处理器不需要等待操作完成,而是在操作完成后得到通知。

Proactor模式的主要特点包括:

  1. 异步处理:事件处理是异步的,事件处理器可以继续执行其他任务,而不必等待操作完成。
  2. 多线程:通常Proactor模式会使用多线程来处理IO操作,以提高系统的并发能力。
  3. 高性能:通过异步IO和多线程的结合,Proactor模式可以实现高性能的并发处理。

区别

  1. 同步 vs. 异步:Reactor模式中事件处理是同步的,而Proactor模式中事件处理是异步的。
  2. 单线程 vs. 多线程:Reactor模式通常在单线程中运行,而Proactor模式通常使用多线程来处理IO操作。
  3. 处理方式:在Reactor模式中,事件发生后Reactor负责调用事件处理器,而在Proactor模式中,操作完成后Proactor负责通知事件处理器。

static 是 C++ 中的关键字,用于声明静态成员变量和静态成员函数,以及在局部变量中具有持久性。

1. 静态变量
  1. 静态局部变量:在函数内部声明的静态变量。和全局变量一样,数据都存放在全局区。

    在函数内部声明的静态变量,其生命周期跨越函数调用。它们只会在第一次函数调用时初始化,并且保留其值直到程序结束。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void foo() {
    static int count = 0;
    count++;
    std::cout << "Count: " << count << std::endl;
    }

    int main() {
    foo(); // 输出:Count: 1
    foo(); // 输出:Count: 2
    foo(); // 输出:Count: 3
    return 0;
    }
  2. 静态成员变量:静态成员变量属于类,而不是类的实例。它们被所有类的对象所共享,并且在类的所有实例中只有一个副本。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <iostream>

    class MyClass {
    public:
    static int count;
    };

    int MyClass::count = 0; // 静态成员变量在类外部进行初始化

    int main() {
    MyClass obj1;
    MyClass::count = 5; // 通过类名访问静态成员变量
    std::cout << "Count: " << obj1.count << std::endl; // 输出:Count: 5,因为静态成员变量是共享的
    return 0;
    }
  3. 静态全局变量:在函数外部声明的静态变量称为静态全局变量。它们的作用域限制在声明它们的文件内,并且在程序的整个生命周期内保留其值。

    说到这,顺便说说extern关键字。它用于声明一个变量或函数是在其他文件中定义的,而不是在当前文件中定义的。即在当前文件中声明在其他文件中定义的变量或函数,以便在当前文件中使用它们。

2. 静态函数

静态成员函数:静态函数属于类,而不是类的实例。它们可以直接通过类名调用,而无需创建类的实例。

1
2
3
4
5
6
7
8
9
10
11
12
class Math {
public:
static int add(int a, int b) {
return a + b;
}
};

int main() {
int sum = Math::add(5, 3); // 直接通过类名调用静态函数
std::cout << "Sum: " << sum << std::endl; // 输出:Sum: 8
return 0;
}

const

const 用于定义常量、声明常量引用以及修饰成员函数。const 的作用是告诉编译器这个东西是不可修改的,即它的值在初始化后不能再被修改。

编译器通常不为普通的const常量分配内存空间,而是将他们保存在符号表中。

1. 定义常量
1
const int x = 5;

定义了一个常量 x,其值为 5。一旦定义,就不能再修改 x 的值。

2. const和引用

const修饰的引用称为”常用引用“,常量引用不能直接修改所引用的对象。

1
2
3
4
const int ci = 1024;//ci是一个int型的常量
const int &r1 = ci;//正确,r1是一个常量引用,并且r1本身也是一个常量
r1 = 42;//错误,引用被const限制了,不能修改所引用对象的值了
int &r2 = ci;//错误,试图让一个非常量引用指向一个常量对象
3. const和指针
  1. 常量指针:指针指向的对象不可变,但指针本身的值可以改变。

    1
    2
    3
    4
    5
    6
    int x = 5;
    const int* ptr = &x; // ptr 是一个指向整型常量的指针,它所指向的对象不能被修改,但可以改变指针的值

    // *ptr = 10; // 错误,不能修改 ptr 所指向的对象的值
    int y = 10;
    ptr = &y; // 可以修改指针 ptr 的值,使其指向不同的对象
  2. 指针常量:指针本身的值不可变,但指针所指向的对象可以改变。

    1
    2
    3
    4
    5
    int x = 5;
    int* const ptr = &x; // ptr 是一个指向整型的常量指针,它的值不能改变,但可以修改其指向的对象

    *ptr = 10; // 可以修改 ptr 所指向的对象的值
    // ptr = &y; // 错误,无法修改指针 ptr 的值
4. const和类对象
  1. const成员变量:

    const 成员变量是指在类中声明为常量的数据成员。一旦被初始化,其值就不能再修改。它们只能在类的构造函数初始化列表中初始化,而不能在构造函数体中赋值。

  2. const成员函数:

    const只能限定类的成员函数,表示该函数不会修改类的成员变量,除非成员变量被 mutable 修饰符修饰

const限定后,该成员函数不允许修改类的数据成员,也不允许调用非const函数,即使该函数没有修改类的数据成员,只要没有声明成const,就不能调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

class MyClass {
public:
// 构造函数初始化 const 成员变量
MyClass(int x): constValue(x) {}

int getValue() const {
// 这是一个常量成员函数,不能修改类的成员变量
return value;
}

void setValue(int newValue) {
value = newValue;
}

private:
const int constValue;
};

int main() {
const MyClass obj(10);
std::cout << "Value: " << obj.getValue() << std::endl; // 合法,调用常量成员函数
// obj.setValue(5); // 错误,常量对象不能调用非常量成员函数
obj.constValue = 5; // 错误,不能修改 const 成员变量的值
return 0;
}
constexper

constexpr 是 C++11 引入的关键字,用于声明“常量表达式”。

常量表达式是在编译时就可以求值的表达式,即它的值可以在编译时被确定。

constexpr 可以用于变量、函数、构造函数以及类的成员函数,用于指示它们在编译时就可以被计算出来,而不是在运行时计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//5是一个常量表达式
constexpr int x = 5;

//square是一个constexpr函数
constexpr int square(int x){
return x * x;
}

class Circle {
private:
constexpr static double PI = 3.14159;
double radius;
public:
constexpr Circle(double r) : radius(r) {}
constexpr double getArea() const {
return PI * radius * radius;
}
};

使用 constexpr 可以使得程序在编译时进行更多的优化,提高程序的性能。

1. 智能指针

  • 智能指针是一种用于管理动态分配的内存的工具,能够帮助避免内存泄漏悬挂指针等问题。
  • 智能指针是C++11标准引入的一个重要特性,它们基于RAII(资源获取即初始化)原则,利用对象生命周期的概念,在对象生命周期结束时自动释放资源。
  • 智能指针实际上是一个类对象,它封装了原始指针,并在其生命周期结束时负责释放指针所指向的内存。
  • 智能指针的核心实现技术是引用计数,每使用它一次,内部引用计数加1,每析构一次内部的引用计数减1,减为0时,删除所指向的堆内存。
  • C++11引入了三种指针:std::shared_ptrstd::unique_ptrstd::weak_ptr

2. std::shared_ptr

共享指针,允许多个指针指向同一块内存,它使用引用计数来跟踪有多少个指针指向了该对象。并且会在最后一个指针不再指向该内存区域时自动释放资源。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <memory>
int main(){
// 使用make_shared创建shared_ptr
std::shared_ptr<int> ptr = std::make_shared<int>(42);
//或构造函数初始化
std::shared_ptr<int>(new int(42));
// 拷贝复制
std::shared_ptr<int> ptr2 = ptr1; //引用计数+1
//获取引用计数
std::cout <<"引用计数:" << ptr1.use_count() << std::endl;

return 0;// 当ptr1和ptr2都超出作用域时,所管理的内存会被自动释放
}
  • 创建shared_ptr

    使用std::make_shared函数来创建std::shared_ptr,它会自动分配内存并构造对象,同时返回一个指向该对象的std::shared_ptr

  • 拷贝和赋值

    将一个std::shared_ptr赋值给另一个时,引用计数会增加。当所有指向该对象的std::shared_ptr都被销毁时,引用计数会减少。只有当引用计数为0时,资源才会被释放。

  • 引用计数

    std::shared_ptr内部维护了一个引用计数器,用于跟踪有多少个std::shared_ptr指向了相同的资源。可以通过use_count()方法获取引用计数。

3. std::weak_ptr

循环引用指的是两个或多个对象彼此之间相互引用,导致它们的引用计数永远不会变为零,从而造成内存泄漏。在使用std::shared_ptr时,循环引用是一个常见的问题,因为std::shared_ptr的引用计数机制可能导致对象永远无法被释放。如以下示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <memory>

class A {
public:
std::shared_ptr<A> next;

A() {
std::cout << "A 构造函数" << std::endl;
}

~A() {
std::cout << "A 析构函数" << std::endl;
}
};

int main() {
std::shared_ptr<A> a1 = std::make_shared<A>();
std::shared_ptr<A> a2 = std::make_shared<A>();

a1->next = a2;
a2->next = a1; // 循环引用

return 0;
}

在这个例子中,a1a2相互引用,即a1next指针指向a2,而a2next指针又指向a1。这样一来,它们之间的引用计数永远不会变为零,因为彼此都在互相引用。即使在main函数结束时,a1a2的引用计数也不会为零,导致A类对象永远无法被销毁,造成内存泄漏。

std::weak_ptrstd::shared_ptr的一种弱引用,它不会增加引用计数。用于解决std::shared_ptr的循环引用带来的内存泄漏问题。可以通过lock()方法获得一个std::shared_ptr,如果原来的std::shared_ptr已经被销毁,则返回一个空指针。

上述示例中,可以将next成员改为std::weak_ptr类型,这样就不会导致循环引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <memory>
#include <iostream>

class A {
public:
std::weak_ptr<A> next; // 使用weak_ptr

A() {
std::cout << "A 构造函数" << std::endl;
}

~A() {
std::cout << "A 析构函数" << std::endl;
}
};

int main() {
std::shared_ptr<A> a1 = std::make_shared<A>();
std::shared_ptr<A> a2 = std::make_shared<A>();

a1->next = a2;
a2->next = a1; // 循环引用被打破

return 0;
}

在这个修改后的示例中,A类的next成员现在是std::weak_ptr类型,这意味着a1->nexta2->next不会增加A对象的引用计数。因此,即使a1a2相互引用,它们之间的循环引用也被打破了。这样在main函数结束时,A类对象的引用计数会变为零,对象会被正确地销毁,从而避免了内存泄漏问题。

4. std::unique_ptr

std::unique_ptr是一种独占所有权的智能指针,它确保在其生命周期内,只有一个指针可以指向该对象。当std::unique_ptr被销毁时,它所管理的对象也会被自动释放。

  • 创建unique_ptr
1
2
3
4
5
6
7
8
9
10
11
#include <memory>

int main() {
// 使用make_unique创建unique_ptr
std::unique_ptr<int> ptr = std::make_unique<int>(42);

// 或者使用构造函数
std::unique_ptr<int> ptr2(new int(42));

return 0;
}
  • 移动语义

std::unique_ptr是独占所有权的,因此它不支持拷贝语义,但支持移动语义。这意味着可以通过移动操作将资源所有权从一个std::unique_ptr转移到另一个。

1
2
3
4
5
6
7
8
9
10
11
#include <memory>

int main() {
std::unique_ptr<int> ptr1 = std::make_unique<int>(42);
std::unique_ptr<int> ptr2 = std::move(ptr1); // 移动所有权到ptr2

// 此时ptr1不再拥有资源,它指向nullptr
// ptr2拥有资源,可以安全地使用

return 0;
}
  • 释放资源

std::unique_ptr超出作用域时,它所管理的资源会被自动释放。

1
2
3
4
5
6
7
8
9
10
11
#include <memory>

void someFunction() {
std::unique_ptr<int> ptr = std::make_unique<int>(42);
// 在这里可以安全地使用ptr
} // ptr超出作用域,所管理的内存会被自动释放

int main() {
someFunction();
return 0;
}
  • 自定义删除器

std::unique_ptr支持自定义删除器,可以指定在释放资源时调用的函数或者函数对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <memory>
#include <iostream>

void customDeleter(int* ptr) {
std::cout << "自定义删除器被调用" << std::endl;
delete ptr;
}

int main() {
std::unique_ptr<int, decltype(&customDeleter)> ptr(new int(42), customDeleter);

return 0;
}

互斥锁(mutex)

互斥锁(Mutex)是一种同步机制,用于在多线程程序中保护共享资源,防止多个线程同时访问和修改共享资源而导致竞争条件的发生。互斥锁通过在对共享资源的访问前先获得锁来确保同一时刻只有一个线程能够访问共享资源,其他线程必须等待该线程释放锁后才能访问。

mutex提供了4种互斥类型:

  • std::mutex:独占的互斥量,不能递归使用,不带超时功能
  • std::recursive_mutex:递归互斥量,可重入,不带超时功能
  • std::timed_mutex:带超时的互斥量,不能递归
  • std::recursive_timed_mutex:带超时的互斥量,可以递归使用

1. 创建和初始化互斥锁

在C++中,可以使用std::mutex类来创建和使用互斥锁。通常情况下,我们在全局范围内定义一个互斥锁对象,或者在需要保护的共享资源的类中定义一个互斥锁成员变量。

1
2
#include <mutex>
std::mutex mtx; // 全局范围内定义一个互斥锁对象

2. 加锁和解锁

在访问共享资源之前,线程需要先获取互斥锁,以确保其他线程不会同时访问该资源。获取锁时,线程会阻塞,直到它成功地获得了锁为止。使用完共享资源后,线程需要释放锁,以允许其他线程访问该资源。

1
2
3
mtx.lock();// 加锁
/*访问共享资源的代码*/
mtx.unlock();// 解锁

3. lock_guard

除了lock()unlock()方法外,还可以使用std::lock_guard自动管理锁的加锁和解锁std::lock_guard是一个RAII(资源获取即初始化)类型,它在创建时自动获取锁,在销毁时自动释放锁,从而避免忘记手动解锁而导致的死锁或资源泄漏。

1
2
3
4
5
6
7
8
#include <mutex>

std::mutex mtx;

void someFunction() {
std::lock_guard<std::mutex> guard(mtx); // 自动加锁
// 访问共享资源的代码
} // 在 guard 超出作用域时自动解锁

创建一个名为 guardstd::lock_guard 对象,用于管理名为 mtx 的互斥锁。在 lock 对象的作用域结束时,会自动释放 mtx 互斥锁,即使在作用域内发生异常也会自动释放。这样做可以确保互斥锁在不再需要时被正确释放,避免了手动调用 lock()unlock() 方法可能带来的错误和忘记释放锁的风险。

4. unique_lock

std::unique_lock 也是 C++ 标准库提供的一个 RAII 类型,用于管理互斥锁的加锁和解锁,类似于 std::lock_guard。但与 std::lock_guard 不同的是,std::unique_lock 具有更多的灵活性和功能。它可以在创建时选择是否加锁,也可以手动释放锁,并且可以在未加锁的情况下等待条件变量。下面详细讲解 std::unique_lock 的用法:

  1. 创建 std::unique_lock 对象
1
2
3
#include <mutex>

std::mutex mtx;
  1. 使用 std::unique_lock 自动管理锁
1
2
3
4
void someFunction() {
std::unique_lock<std::mutex> lock(mtx); // 自动加锁
// 访问共享资源的代码
} // 在 lock 超出作用域时自动解锁
  1. 手动控制加锁和解锁

std::unique_lock 允许手动控制锁的加锁和解锁。例如:

1
2
3
4
std::unique_lock<std::mutex> lock(mtx, std::defer_lock); // 不加锁
lock.lock(); // 手动加锁
// 访问共享资源的代码
lock.unlock(); // 手动解锁
  1. std::unique_lock 还可以在未加锁的情况下等待条件变量,从而避免了手动释放锁后再等待条件变量的复杂过程。
1
2
3
4
5
6
7
8
9
10
#include <condition_variable>

std::condition_variable cv;

void someFunction() {
std::unique_lock<std::mutex> lock(mtx);
// 等待条件变量
cv.wait(lock, []{ /* 条件函数 */ });
// 条件满足后继续执行
}

std::unique_lock 对象 lock 会自动加锁,然后等待条件变量 cv。当条件满足时,会自动解锁并继续执行。

原子操作-atomic

有两个线程,一个要写数据,一个读数据,如果不加锁可能会造成读写值混乱,使用std::mutex可以使得执行不会导致混乱,但是每一次循环都要加锁解锁使得程序开销很大。为了提高性能,C++11提供了原子类型std::atomic,它提供了多线程间的原子操作。原子操作是不可分割的操作,要么完全执行,要么完全不执行,不会被其他线程中断。

原子类型是封装了一个值的类型,它的访问保证不会导致数据的竞争,并且可以用于在不同的线程之间同步内存访问。从效率上来说,原子操作要比互斥量的方式效率要高

  1. 创建 std::atomic 对象
1
2
3
#include <atomic>

std::atomic<int> atomicVariable;

创建了一个名为 atomicVariablestd::atomic<int> 对象,表示一个原子的整型变量。

  1. 原子操作

std::atomic 提供了一系列原子操作,包括读取、写入、加法、减法等。这些操作可以保证在多线程环境中的原子性,从而避免竞争条件。

1
2
3
4
5
6
7
8
9
atomicVariable.store(10); // 将10存储到原子变量中

int value = atomicVariable.load(); // 从原子变量中加载值

atomicVariable.fetch_add(5); // 原子地将5加到atomicVariable上

atomicVariable.fetch_sub(3); // 原子地将atomicVariable减3

int oldValue = atomicVariable.exchange(20); // 原子地将atomicVarible的值交换为 20,并返回之前的值
  1. 示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <thread>
#include <atomic>

std::atomic<int> counter(0); // 声明一个原子整型变量并初始化为 0

void incrementCounter(int numIncrements) {
for (int i = 0; i < numIncrements; ++i) {
counter++; // 原子地递增 counter 的值
}
}

int main() {
constexpr int numThreads = 4; // 定义线程数量
constexpr int numIncrementsPerThread = 1000000; // 每个线程递增的次数

std::thread threads[numThreads]; // 创建线程数组

// 启动多个线程,并分别调用 incrementCounter 函数
for (int i = 0; i < numThreads; ++i) {
threads[i] = std::thread(incrementCounter, numIncrementsPerThread);
}

// 等待所有线程执行完毕
for (int i = 0; i < numThreads; ++i) {
threads[i].join();
}

std::cout << "Final value of counter: " << counter.load() << std::endl; // 输出最终的 counter 值

return 0;
}

运行结果:

1
Final value of counter: 4000000

条件变量condition_varible

用于实现线程之间的条件等待通知机制。它通常与 std::mutex(互斥锁)一起使用,用于在某个条件满足时唤醒等待的线程。主要包括两个动作:

  1. 一个线程等待条件变量的条件成立而挂起(wait)
  2. 另一个线程使条件成立(notify_onenotify_all)

先来看一个示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

std::mutex mtx;
std::condition_variable cv;
bool isReady = false;

void waitingThread(){
std::unique_lock<std::mutex> lock(mtx); //自动上锁
while(!isReady){
cv.wait(lock);
}
std::cout << "Condition is met, continuing..." << std::endl;
}

int main(){
std::thread t1(waitingThread);
std::this_thread::sleep_for(std::chrono::seconds(5));//主线程休眠5秒,模拟主线程工作
{
std::unique_lock<std::mutex> lock(mtx);
isReady = true;
}// lock超出作用域时自动释放互斥锁
cv.notify_one(); //通知等待的线程
t1.join();

return 0;
}

1. 等待条件的线程

1
2
3
4
5
6
7
void waitingThread(){
std::unique_lock<std::mutex> lock(mtx); //自动上锁
while(!isReady){
cv.wait(lock);
}
std::cout << "Condition is met, continuing..." << std::endl;
}

它会执行如下步骤:

  1. 获取与条件变量相关联的互斥锁
  2. 进入 while 循环,检查条件是否满足。如果条件已经满足,线程会跳过等待,并继续执行后续代码。
  3. 如果条件尚未满足,则调用 cv.wait(lock) 函数,将当前线程置于阻塞状态,并释放互斥锁。以允许其他线程访问共享资源。
  4. 直到其他线程调用了与条件变量相关联的 notify_one()notify_all() 函数,条件变量被通知。该线程被唤醒,并会重新获取互斥锁,继续执行whie循环,检查条件是否满足。
  5. 如果条件满足,则线程会退出 while 循环,继续执行后续代码。

2. 设置条件并通知等待的线程

主线程负责设置条件并通知等待的线程

1
2
3
std::unique_lock<std::mutex> lock(mtx); // 获取互斥锁
isReady = true;
cv.notify_one(); // 通知等待的线程
  1. 在修改条件之前,必须先获得与条件变量关联的互斥锁,并在修改后立即释放锁。
  2. 然后,通过 cv.notify_one()cv.notify_all() 来通知等待的线程条件已经发生改变。

异步任务-async、future

  • 已经有多线程thread了,为什么还要有async?
    线程毕竟是属于比较低层次的东西,有时候使用有些不便,比如希望获取线程函数的返回结果的时候,就不能直接通过 thread.join()得到结果,这时就必须定义一个变量,在线程函数中去给这个变量赋值,然后join,最后得到结果,这个过程是比较繁琐的。

  • C++11 提供了**std::async()**,用于创建异步任务,即在一个新的线程中调用线程函数,并返回一个 std::future 对象,这个future中存储了线程函数返回的结果。

简单示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <future>
#include <chrono>

// 耗时操作函数,返回一个整数
int timeConsumingOperation() {
// 模拟一个耗时操作,这里暂停 2 秒钟
std::this_thread::sleep_for(std::chrono::seconds(2));
return 42;
}

int main() {
// 创建一个异步任务,异步执行 timeConsumingOperation 函数
std::future<int> fut = std::async(std::launch::async, timeConsumingOperation);

// 执行其他操作
std::cout << "Performing other tasks..." << std::endl;

// 等待异步操作完成并获取结果
int result = fut.get();

// 输出异步操作的结果
std::cout << "Result of asynchronous operation: " << result << std::endl;

return 0;
}

概括std::async()的用法:

1. 创建异步任务并获取future 对象

1
2
3
#include <future>

std::future<int> fut = std::async(std::launch::async, func);

创建了一个异步任务,异步任务会立即在一个新线程中执行,线程调用函数func(),将函数的返回值赋给了future对象fut

2. 获取异步任务的值

1
auto result = fut.get();

需要获取异步操作的结果时,调用 get() 函数来获取 std::future 对象的值。如果异步操作还没有完成,get() 函数会阻塞当前线程,直到异步操作完成并返回结果。

如何检查异步任务是否完成:

1
bool state = fut.valid();

可以调用 valid() 函数来检查 std::future 对象是否有效。如果 std::future 对象与异步操作相关联,并且异步操作尚未完成,则 valid() 函数返回 true,否则返回 false

3. 异步执行策略

std::async() 函数提供的三种异步执行策略。它们决定了 std::async() 函数创建的异步任务的执行方式。

1. std::launch::async

  • std::launch::async 策略表示创建一个新的线程,在新的线程中异步执行指定的可调用对象。
  • 这意味着异步任务会立即在一个新的线程中执行,不会阻塞当前线程。
  • 使用 std::launch::async 策略创建的异步任务可以实现并行执行,适用于耗时的计算任务和I/O操作等。
1
std::future<int> fut = std::async(std::launch::async, task);

2. std::launch::deferred

  • std::launch::deferred 策略表示延迟执行指定的可调用对象,直到调用 get() 函数时才在调用线程中执行。
  • 这种策略不会创建新的线程,而是在需要时延迟执行。
  • 使用 std::launch::deferred 策略创建的异步任务不会立即执行,直到调用 get() 函数时才执行,适用于延迟执行和惰性求值等场景。
1
std::future<int> fut = std::async(std::launch::deferred, task);

3. std::launch::async | std::launch::deferred

  • std::launch::async | std::launch::deferred 表示由实现自行选择执行策略。
  • 这种策略允许实现根据具体情况自行选择执行方式,可以在新的线程中异步执行,也可以在调用线程中延迟执行。
  • 使用 std::launch::async | std::launch::deferred 策略创建的异步任务有可能在新的线程中执行,也有可能在调用线程中延迟执行,具体取决于实现。
1
std::future<int> fut = std::async(std::launch::async | std::launch::deferred, task);

1. 选择排序

开启n-1轮循环,每次从未排序的元素中选择最小(或最大)的元素,将其与未排序序列的第一个元素交换位置,从而逐步构建有序序列。

选择排序的具体流程如下:

  1. 初始状态:将整个序列视为两部分,一部分是已排序序列,另一部分是未排序序列。
  2. 选择最小元素:从未排序序列中选择最小的元素,并将其与未排序序列的第一个元素交换位置。
  3. 扩大已排序序列:将交换后的元素视为已排序序列的一部分,未排序序列减少一个元素。
  4. 重复步骤2和步骤3:直到所有元素都被选择并放置到正确的位置上。

伪代码:

1
2
3
4
5
6
7
8
选择排序(A):
for i from 0 to length(A)-2:
minIndex = i
for j from i+1 to length(A)-1:
if A[j] < A[minIndex]:
minIndex = j
// 将未排序序列中最小元素与第i个元素交换位置
swap(A[i], A[minIndex])

时间复杂度为O(n^2)

2. 冒泡排序

多次遍历待排序序列,每轮连续比较相邻的元素,如果“左元素 > 右元素”则交换位置,使较大的元素逐步“冒泡”到数组的末端。

冒泡排序的具体流程如下:

  1. 比较相邻元素:从数组的第一个元素开始,比较相邻的两个元素,如果前一个元素比后一个元素大,则交换它们的位置,这样较大的元素就会向数组的末端移动。
  2. 遍历整个数组:重复步骤1,遍历整个数组,直到所有的元素都已经比较过一次。
  3. 缩小范围:每次遍历过程中,都会使得数组末端的一个元素排好序,因此在下一次遍历时,可以将待排序序列的范围缩小一个元素

伪代码:

1
2
3
4
5
6
冒泡排序(A):
n = length(A)
for i from 0 to n-1:
for j from 0 to n-1-i:
if A[j] > A[j+1]:
swap(A[j], A[j+1])

时间复杂度:O(n^2)

3. 插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。其基本思想是将待排序的数据序列分为已排序区间和未排序区间,通过构建有序序列,对未排序的数据逐个进行插入,从而达到排序的目的。

插入排序的具体思路如下:

  1. 初始状态:将第一个元素视为已排序序列,剩余的元素为未排序序列。
  2. 遍历未排序序列:从第二个元素开始,逐个遍历未排序序列的元素。
  3. 将当前元素插入已排序序列:对于每个未排序序列中的元素,将其与已排序序列中的元素逐个比较,找到合适的位置并插入。
  4. 移动元素:为了给当前元素腾出位置,需要将已排序序列中比当前元素大的元素依次向后移动。
  5. 重复步骤3和步骤4:直到所有元素都被插入到已排序序列中。

伪代码:

1
2
3
4
5
6
7
8
插入排序(A):
for i from 1 to length(A)-1:
currentElement = A[i]
j = i - 1
while j >= 0 and A[j] > currentElement:
A[j+1] = A[j]
j = j - 1
A[j+1] = currentElement

时间复杂度:O(n^2)

4. 快速排序

快速排序(quick sort)是一种基于分治策略的排序算法。基本思想是选择一个基准元素,将序列分割成两个子序列,其中一个子序列中的所有元素小于基准元素,另一个子序列中的所有元素大于基准元素,然后对这两个子序列分别进行递归排序。

快速排序的具体步骤如下:

  1. 选择基准元素:从待排序序列中选择一个元素作为基准元素。通常选择序列的第一个元素、最后一个元素或者中间的元素作为基准元素。
  2. 分割序列:根据基准元素,将序列分割成两个子序列,其中一个子序列中的元素小于基准元素,另一个子序列中的元素大于基准元素。通常使用两个指针(左指针和右指针)来实现分割,左指针指向序列的起始位置,右指针指向序列的末尾位置,然后从左右两端向中间移动指针,交换不符合条件的元素,直到左右指针相遇。
  3. 递归排序:对两个子序列分别进行递归排序,直到子序列的长度为1或0。
  4. 合并结果:将经过排序的子序列合并成最终的有序序列。

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
快速排序(A, low, high):
if low < high:
pivotIndex = partition(A, low, high)
快速排序(A, low, pivotIndex - 1)
快速排序(A, pivotIndex + 1, high)

partition(A, low, high):
pivot = A[low] // 选择第一个元素作为基准元素
left = low + 1
right = high
while left <= right:
while left <= right and A[left] <= pivot:
left = left + 1
while left <= right and A[right] > pivot:
right = right - 1
if left < right:
swap(A[left], A[right])
swap(A[low], A[right])
return right

快速排序的时间复杂度为 O(n log n),其中 n 是待排序序列的长度。在平均情况下,快速排序的性能非常好,但是在最坏情况下(例如,当选择的基准元素总是序列中的最大或最小元素时),快速排序的时间复杂度可能会退化为 O(n^2)。

空间复杂度为O(n):在输入数组完全倒序的情况下,达到最差递归深度 n ,使用 O(n)栈帧空间。若采用尾递归优化,则复杂度为O(log n)。

尾递归优化是一种编译器优化技术,用于优化递归调用的栈空间使用。在尾递归优化中,如果函数的最后一个操作是对自身的递归调用,编译器会将这种递归调用转换为循环,从而避免在调用栈上创建新的帧,节省了栈空间的使用。

5. 归并排序

归并排序(Merge Sort)是一种基于分治思想的排序算法。其基本思路是将待排序序列成两个子序列,分别对这两个子序列进行递归排序,然后将两个已经排好序的子序列并成一个有序序列。

具体的算法流程:

  1. 分割序列:不断地将待排序序列划分成两个子序列,直到子序列的长度为1或0
  2. 递归排序:递归地对分割后的两个子序列进行排序。
  3. 合并序列:将两个已经排好序的子序列合并成一个有序序列。

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
归并排序(A):
if length(A) <= 1:
return A
else:
middle = length(A) / 2
left_half = 归并排序(A[0:middle]) // 递归排序左半部分
right_half = 归并排序(A[middle:length(A)]) // 递归排序右半部分
return 合并(left_half, right_half) // 合并左右两部分并返回合并后的有序序列

合并(left_half, right_half):
result = []
while left_half 不为空 and right_half 不为空:
if left_half[0] <= right_half[0]:
result.append(left_half[0])
left_half = left_half[1:]
else:
result.append(right_half[0])
right_half = right_half[1:]
// 将剩余的元素追加到结果中
result += left_half
result += right_half
return result

归并排序的时间复杂度为 O(n log n)。虽然归并排序的时间复杂度较低,但是需要额外的空间来存储归并过程中产生的临时序列,因此其空间复杂度为 O(n)。

6. 堆排序

堆排序(Heap Sort)是一种基于堆数据结构的排序算法,其基本思想是利用堆的性质实现排序。堆是一个特殊的树形数据结构,具有以下性质:

  1. 它是一个完全二叉树,即除了最后一层,其他层都是满的。
  2. 在一个小顶堆(Min Heap)中,任意节点的值都小于或等于其子节点的值。
  3. 在一个大顶堆(Max Heap)中,任意节点的值都大于或等于其子节点的值。

将待排序的序列构建成一个大顶堆,重复从堆中取出堆顶元素,并重新构建堆,直到堆为空,最终得到即为排序好的序列。

算法的流程:

  1. 构建堆:

    ​ 首先需要将待排序的序列构建成一个堆。一种常见的方法是从最后一个非叶子节点开始,依次向前进行调整,保证每个节点都满足堆的性质。

    大顶堆的调整过程:

    • 从最后一个非叶子节点开始(即 n/2-1),向前遍历到根节点。
    • 对于每个节点,如果它的子节点中有比它大的,就将其与最大的子节点进行交换,直到它没有比它大的子节点或者到达叶子节点为止。
  2. 排序:

    ​ 构建好堆之后,需要重复从堆中取出最大(或最小)的元素,并重新调整堆,直到堆为空。具体的过程如下:

    • 将堆顶元素(最大或最小值)与堆中的最后一个元素交换位置。
    • 从堆中移除最后一个元素(即最大或最小值)。
    • 对剩余的元素重新调整堆,使其满足堆的性质。

    重复以上步骤,直到堆为空。

7. 桶排序

8. 计数排序

9. 基数排序

10. 希尔排序

搜索算法用于在数据结构(例如数组、链表、树或图)中搜索一个或一组满足特定条件的元素。

搜索算法可根据实现思路分为以下两类。

  • 通过遍历数据结构来定位目标元素,例如数组、链表、树和图的遍历等。
  • 利用数据组织结构或数据包含的先验信息,实现高效元素查找,例如二分查找、哈希查找和二叉搜索树查找等。

1. 暴力搜索

暴力搜索通过遍历数据结构的每个元素来定位目标元素。

1. 线性搜索

  • 适用于数组链表等线性数据结构。
  • 顺序地逐个检查数据结构中的每个元素,直到找到目标元素或搜索完整个数据结构。
  • 时间复杂度为**O(n)**,其中n是数据结构中的元素数量。

2. 图搜索

  • 用于在图/树中查找特定的节点或路径,即深度优先搜索(Depth-First Search,DFS)广度优先搜索(Breadth-First Search,BFS)
  • 广度优先搜索从初始节点开始逐层搜索,由近及远地访问各个节点。
  • 深度优先搜索从初始节点开始,沿着一条路径走到头,再回溯并尝试其他路径,直到遍历完整个数据结构。
  • 时间复杂度取决于图的结构和算法的实现方式。

2. 自适应搜索

自适应搜索利用数据的特有属性(例如有序性)来优化搜索过程,从而更高效地定位目标元素。

1. 二分搜索

  • 仅适用于已排序的数据结构(如有序数组),通过不断将搜索范围减半来定位目标元素。
  • 时间复杂度为**O(log n)**。

2. 哈希查找

  • 利用哈希表将搜索数据目标数据建立为键值对映射,从而实现查询操作。
  • 时间复杂度通常为**O(1)**,但在冲突较多的情况下可能会降低到O(n)。

3. 树查找

  • 通过有序的树结构和特定的查找算法(如递归或迭代)来查找目标元素。
  • 包括二叉搜索树(Binary Search Tree,BST)、平衡二叉树(Balanced Binary Tree,如AVL树、红黑树)、B树等
  • 平均情况下的时间复杂度取决于树的高度,**通常为O(log n)**,但在最坏情况下可能为O(n)。