首页 秋招复盘7.25：cpp
文章
取消

秋招复盘7.25：cpp

发表于 2023/10/09
作者 Olimi
阅读量: 80 分钟阅读

C++11中智能指针

C++11中智能指针的分类。是线程安全的嘛，如果不是使用时怎么处理。

在C++11中，提供了四种类型的智能指针：

  1. std::unique_ptr: 独特所有权，不能被复制，但可以通过std::move进行所有权转移。
  2. std::shared_ptr: 共享所有权，可以有多个shared_ptr指向同一个对象，shared_ptr使用引用计数来跟踪有多少个智能指针指向同一个资源，当最后一个shared_ptr被销毁时，资源也将被释放。
  3. std::weak_ptr: 弱引用，它可以指向一个由shared_ptr管理的对象，但它不参与引用计数，主要用来解决shared_ptr可能会引发的循环引用问题。
  4. std::auto_ptr: 这是一个被废弃的智能指针，它试图实现独占所有权，但其语义在C++标准中并不怎么清晰，因此在C++11中被std::unique_ptr所取代。

关于线程安全性，除std::shared_ptr外，其他智能指针都不是线程安全的。注意，std::shared_ptr的线程安全性仅限于你可以在不同的线程中安全地使用单个shared_ptr的副本。然而，让多个线程同时访问同一shared_ptr实例（例如，一个线程读取，另一个线程写入）可能会导致数据竞争和未定义的行为。因此，如果在多线程环境中使用智能指针，你需要自己进行适当的同步。

以下是一个示例，展示如何在多线程环境中使用std::mutex来同步对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>
#include <mutex>
#include <thread>

std::shared_ptr<int> p;
std::mutex mtx;

void thread_func() {
    std::lock_guard<std::mutex> lock(mtx);
    // 在这里安全地使用p
}

int main() {
    p = std::make_shared<int>(42);

    std::thread t1(thread_func);
    std::thread t2(thread_func);

    t1.join();
    t2.join();

    return 0;
}

在这个示例中，我们使用了std::mutex和std::lock_guard来保证在多个线程中对p的访问是互斥的，这样就可以避免数据竞争和未定义的行为。

std::shared_ptr的线程安全性仅限于可以在不同的线程中安全地使用单个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

#include <memory>
#include <thread>

void thread_func(std::shared_ptr<int> p) {
    // 在这里安全地使用p
}

int main() {
    std::shared_ptr<int> p = std::make_shared<int>(42);

    // 创建新的shared_ptr副本，并在新线程中使用它们
    std::thread t1(thread_func, p);
    std::thread t2(thread_func, p);

    t1.join();
    t2.join();

    return 0;
}

在这个示例中，我们在主线程中创建了一个shared_ptr（p），然后在创建新线程时，我们将p传递给thread_func。每次thread_func被调用时，都会创建一个新的shared_ptr副本（即函数参数p），这个副本与原始的shared_ptr（主线程中的p）指向同一个对象。由于std::shared_ptr的线程安全性，这种用法是安全的，每个线程都有自己的shared_ptr副本，且不会发生数据竞争。

C++11中线程mutex

C++11中线程安全提供的mutex等。

std::mutex是C++11标准库中提供的一个线程同步原语，用于保护共享资源的访问。std::mutex提供了基本的互斥锁功能，即在多个线程中对共享资源进行访问时，只有一个线程可以访问该资源。当一个线程持有锁时，其他线程需要等待该锁被释放后才能获得锁并继续执行。以下是一些std::mutex的使用场景：

  1. 保护共享资源：在多线程环境下，当多个线程同时访问共享资源时，需要使用std::mutex保护共享资源，防止数据竞争问题的发生。例如：多个线程对一个共享的计数器进行更新时，需要使用std::mutex进行保护，以确保计数器的值是正确的。
  2. 等待/通知机制：在多线程编程中，有时需要一个线程等待另一个线程的某个事件的发生，然后再继续执行。这可以通过std::mutex和std::condition_variable实现。std::condition_variable可以用于等待另一个线程的通知，并在条件满足时通知等待的线程继续执行。
  3. 递归锁：当一个线程需要多次获取同一个锁时，可以使用std::recursive_mutex，它允许同一个线程多次获取锁，而不会发生死锁。但是，需要注意的是，std::recursive_mutex会增加锁的开销，因此在不需要递归锁的情况下，应该使用std::mutex。
  4. 超时锁：如果需要在等待锁的过程中设置超时时间，可以使用std::timed_mutex和std::unique_lock。std::timed_mutex提供了带超时时间的lock()操作，而std::unique_lock提供了更灵活的锁定方式。

除了上述标准库提供的互斥锁类之外，C++标准库还提供了其他类型的锁，如读写锁（std::shared_mutex）、自旋锁（std::spin_lock）和屏障（std::barrier）等，以满足不同的需求。

需要注意的是，使用锁是一种确保线程安全的方式，但也会带来一定的性能开销。因此，在使用锁的同时，应该避免过度锁定，尽量减少锁的持有时间，以提高程序的性能。

  • 具体的示例
    1. std::mutex：

    std::mutex是C++11标准库中最基本的互斥锁类，用于保护共享资源的访问。下面是一个简单的示例，演示了如何使用std::mutex来保护共享资源：

    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 <iostream>
  #include <thread>
  #include <mutex>
    
  std::mutex mtx;
  int count = 0;
    
  void increment() {
      mtx.lock();
      count++;
      mtx.unlock();
  }
    
  int main() {
      std::thread t1(increment);
      std::thread t2(increment);
    
      t1.join();
      t2.join();
    
      std::cout << "count: " << count << std::endl;
    
      return 0;
  }

    在上述示例中，我们定义了一个全局变量count，并创建了两个线程t1和t2，它们都调用了increment()函数。由于count是一个共享资源，我们需要使用std::mutex来保护它的访问。在increment()函数中，我们使用std::mutex的lock()和unlock()函数来保证对count的访问是互斥的。

    1. std::recursive_mutex：

    std::recursive_mutex是一个递归互斥锁，允许同一个线程多次获取锁，而不会发生死锁。下面是一个使用std::recursive_mutex的示例：

    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 <iostream>
  #include <thread>
  #include <mutex>
    
  std::recursive_mutex mtx;
    
  void foo() {
      mtx.lock();
      std::cout << "foo" << std::endl;
      mtx.unlock();
  }
    
  void bar() {
      mtx.lock();
      foo();
      std::cout << "bar" << std::endl;
      mtx.unlock();
  }
    
  int main() {
      std::thread t(bar);
      t.join();
    
      return 0;
  }

    在上述示例中，我们定义了一个递归互斥锁std::recursive_mutex，并创建了两个函数foo()和bar()，它们都使用了该锁来保护共享资源。在bar()函数中，我们首先获取mtx的锁，然后调用foo()函数。在foo()函数中，我们再次获取相同的锁，输出”foo”，然后释放锁。最后在bar()函数中输出”bar”，并释放锁。

    需要注意的是，如果在foo()函数中使用了非递归互斥锁来保护共享资源，那么在bar()函数中再次获取该锁时就会发生死锁，因为尝试获取已经被当前线程占用的锁会导致线程阻塞。而使用std::recursive_mutex可以避免这种情况，因为它允许同一个线程多次获取锁，而不会发生死锁。

    1. std::timed_mutex和std::unique_lock：

    std::timed_mutex是一个带有超时时间的互斥锁，允许等待一段时间后自动释放锁。std::unique_lock是一个RAII锁封装，提供了更灵活的锁定方式。下面是一个使用std::timed_mutex和std::unique_lock的示例，演示了如何等待一段时间后自动释放锁：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

      #include <iostream>
  #include <thread>
  #include <mutex>
  #include <chrono>
    
  std::timed_mutex mtx;
    
  void foo() {
      std::unique_lock<std::timed_mutex> lock(mtx, std::chrono::seconds(1));
      if (lock.owns_lock()) {
          std::cout << "foo" << std::endl;
      } else {
          std::cout << "foo failed to acquire lock" << std::endl;
      }
  }
    
  int main() {
      std::thread t(foo);
      t.join();
    
      return 0;
  }

    在上述示例中，我们定义了一个函数foo()，它尝试获取锁并在1秒钟后自动释放锁。在foo()函数中，我们使用std::unique_lock的构造函数，指定超时时间为1秒。如果在1秒钟内成功获取锁，则输出”foo”，否则输出”foo failed to acquire lock”。

    1. std::shared_mutex：

    std::shared_mutex是一个读写锁，允许多个线程同时读取共享资源，但只允许一个线程写入共享资源。下面是一个使用std::shared_mutex的示例：

    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

      #include <iostream>
  #include <thread>
  #include <mutex>
  #include <shared_mutex>
    
  std::shared_mutex mtx;
  int count =0;
    
  void read() {
      std::shared_lock<std::shared_mutex> lock(mtx);
      std::cout << "read: " << count << std::endl;
  }
    
  void write() {
      std::unique_lock<std::shared_mutex> lock(mtx);
      count++;
      std::cout << "write: " << count << std::endl;
  }
    
  int main() {
      std::thread t1(read);
      std::thread t2(read);
      std::thread t3(write);
    
      t1.join();
      t2.join();
      t3.join();
    
      return 0;
  }

    在上述示例中，我们定义了两个读线程和一个写线程，它们都使用了std::shared_mutex来保护共享资源count的访问。在读线程中，我们使用std::shared_lock来获取读锁，允许多个线程同时读取共享资源。而在写线程中，我们使用std::unique_lock来获取写锁，只允许一个线程写入共享资源。

    1. 自旋锁：

    自旋锁是一种基于忙等待的锁，它避免了线程切换的开销，但会消耗CPU资源。C++标准库中提供了std::atomic_flag来实现自旋锁。下面是一个使用std::atomic_flag实现自旋锁的示例：

    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 <iostream>
  #include <thread>
  #include <atomic>
    
  std::atomic_flag flag = ATOMIC_FLAG_INIT;
  int count = 0;
    
  void increment() {
      while (flag.test_and_set(std::memory_order_acquire));
      count++;
      flag.clear(std::memory_order_release);
  }
    
  int main() {
      std::thread t1(increment);
      std::thread t2(increment);
    
      t1.join();
      t2.join();
    
      std::cout << "count: " << count << std::endl;
    
      return 0;
  }

    在上述示例中，我们使用std::atomic_flag来实现自旋锁。在increment()函数中，我们使用test_and_set()函数获取锁，然后执行增加操作，最后使用clear()函数释放锁。需要注意的是，自旋锁会消耗大量的CPU资源，因此在使用自旋锁时需要谨慎。

    • 自旋锁的进一步示例

      概念：

      自旋锁是一种基于忙等待的锁，即线程不断地尝试获取锁，直到锁可用为止。在自旋锁中，如果线程尝试获取锁时发现锁已经被占用，那么它会不断地循环检查锁的状态，直到锁被释放。自旋锁的优点是避免了线程切换的开销，但会消耗CPU资源。

      函数：

      C++标准库中提供了std::atomic_flag来实现自旋锁。std::atomic_flag是一个原子布尔标志，支持原子测试和设置操作。在使用自旋锁时，我们可以使用std::atomic_flag的test_and_set()函数获取锁，clear()函数释放锁。

      使用场景：

      自旋锁通常用于保护非常短的代码段，这些代码段不需要等待太长时间就可以完成。如果需要保护的代码段执行时间较长，那么自旋锁会消耗大量的CPU资源，影响系统的性能。因此，在使用自旋锁时需要根据具体情况选择合适的锁类型。

      下面是一个使用自旋锁的示例，演示了如何使用std::atomic_flag实现自旋锁：

      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 <iostream>
  #include <thread>
  #include <atomic>
        
  std::atomic_flag flag = ATOMIC_FLAG_INIT;
  int count = 0;
        
  void increment() {
      while (flag.test_and_set(std::memory_order_acquire));
      count++;
      flag.clear(std::memory_order_release);
  }
        
  int main() {
      std::thread t1(increment);
      std::thread t2(increment);
        
      t1.join();
      t2.join();
        
      std::cout << "count: " << count << std::endl;
        
      return 0;
  }

      在上述示例中，我们定义了一个std::atomic_flag类型的变量flag，并创建了两个线程t1和t2，它们都调用了increment()函数。在increment()函数中，我们使用test_and_set()函数获取锁，然后执行增加操作，最后使用clear()函数释放锁。

      除了std::atomic_flag，还有一些其他的自旋锁实现，如std::atomic<int>、std::atomic<bool>、std::atomic<intptr_t>等等。此外，一些操作系统也提供了自旋锁的实现，如Linux内核中的spinlock_t。

      对于高并发的情况，可以使用更高级的自旋锁实现，如Ticket Spinlock、MCS Spinlock等。这些自旋锁实现可以更好地支持多核CPU，避免竞争和锁争用等问题。

      下面给出一个使用Ticket Spinlock的示例：

      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

        #include <iostream>
  #include <thread>
  #include <atomic>
        
  class TicketSpinLock {
  public:
      TicketSpinLock() : m_next(0), m_now_serving(0) {}
        
      void lock() {
          unsigned my_ticket = m_next.fetch_add(1, std::memory_order_relaxed);
          while (my_ticket != m_now_serving.load(std::memory_order_acquire));
      }
        
      void unlock() {
          m_now_serving.fetch_add(1, std::memory_order_release);
      }
        
  private:
      std::atomic<unsigned> m_next;
      std::atomic<unsigned> m_now_serving;
  };
        
  TicketSpinLock lock;
  int count = 0;
        
  void increment() {
      lock.lock();
      count++;
      lock.unlock();
  }
        
  int main() {
      std::thread t1(increment);
      std::thread t2(increment);
        
      t1.join();
      t2.join();
        
      std::cout << "count: " << count << std::endl;
        
      return 0;
  }

      在上述示例中，我们定义了一个Ticket Spinlock类，并创建了两个线程t1和t2，它们都调用了increment()函数来增加计数器count的值。在TicketSpinLock类中，我们使用两个原子变量m_next和m_now_serving来实现自旋锁。在lock()函数中，我们首先获取当前的票号my_ticket，然后不断循环检查m_now_serving的值，直到它等于my_ticket，表示当前线程获取到了锁。在unlock()函数中，我们将当前服务的票号加1，表示当前线程已经完成了对共享资源的操作，可以释放锁。

      需要注意的是，实际使用自旋锁时需要根据具体情况选择合适的锁类型，并考虑到锁的开销和线程切换的开销，以及竞争和锁争用等问题。

C++11中的移动语义

11中的移动语义。声明一个类，将其一个对象move到另一个指针，可以吗，发生了什么。

在C++中，移动语义（Move Semantics）是C++11标准中引入的新特性，主要是为了减少不必要的内存拷贝。如果你有一个大的对象，你可以“移动”它而不是复制它，这样可以节省大量的时间和内存。

C++中的移动语义主要通过特殊的类型的引用实现，称为右值引用（rvalue reference）。右值引用是一种特殊类型的引用，它可以绑定到临时对象（也就是右值）。右值引用主要用来支持移动语义和完美转发。

让我们定义一个简单的类，然后演示如何将其一个对象”移动”到另一个对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
#include <utility>

class MyClass {
public:
    MyClass() { std::cout << "Default constructor\\n"; }
    MyClass(const MyClass&) { std::cout << "Copy constructor\\n"; }
    MyClass(MyClass&&) { std::cout << "Move constructor\\n"; }
    ~MyClass() { std::cout << "Destructor\\n"; }
};

int main() {
    MyClass a; // 调用默认构造函数
    MyClass b(std::move(a)); // 调用移动构造函数
    return 0;
}

在这个例子中，MyClass有一个移动构造函数，它接受一个右值引用参数。在main函数中，我们创建了一个MyClass对象a，然后我们使用std::move将a转化为右值，并传递给b的构造函数。这里，std::move(a)不会移动a，而只是返回一个a的右值引用，这样就可以调用移动构造函数了。这个过程中并没有进行任何的复制操作，所以比复制构造函数更高效。

然而，需要注意的是，移动一个对象可能会使它处于一个有效但未定义的状态。在上面的例子中，a被移动后就不应再被使用。

进一步地。移动语义（std::move）主要就是将一个对象转换为右值，然后就可以相应地调用一个对象的移动构造函数（特殊情况下，如何未定义移动构造函数，就会转而选择拷贝构造函数）。

移动构造函数和拷贝构造函数的主要区别在于它们处理对象数据的方式不同。当你拷贝一个对象时，你实际上是创建了该对象的一个新副本，这个过程需要分配内存并复制数据，这可能会非常消耗资源。而当你移动一个对象时，你实际上是将原对象的数据“转移”给新对象，而不是复制这些数据。这个过程不需要复制数据，因此通常更有效率。

这是一个例子，可以帮助理解移动和复制的区别：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class MyClass {
public:
    int* data;
    int size;

    // 拷贝构造函数
    MyClass(const MyClass& other) : size(other.size), data(new int[other.size]) {
        std::copy(other.data, other.data + other.size, data);
    }

    // 移动构造函数
    MyClass(MyClass&& other) noexcept : size(other.size), data(other.data) {
        other.size = 0;
        other.data = nullptr;
    }
};

在这个例子中，拷贝构造函数会创建一个新的data数组，并将other.data的数据复制到这个新数组。而移动构造函数则直接将other.data的所有权转移给新对象，然后将other.data设为nullptr，这样other就不再拥有任何数据。

这就解释了为什么移动后的对象通常不能再使用：移动构造函数会将原对象的数据“窃取”给新对象，所以原对象可能会处于一个空的、无效的状态。在上面的例子中，如果你试图访问移动后的other.data，你会得到一个空指针，这通常会导致运行时错误。

然而，虽然移动后的对象通常不能再使用，但是它仍然是一个有效的对象，你可以给它赋予新的值，或者让它调用不依赖于其内部数据的成员函数。你也可以让它调用那些能够处理空状态的成员函数，例如析构函数。

总的来说，如果你需要创建一个对象的副本，并且你需要保留原对象的状态，那么你应该使用拷贝构造函数。如果你不再需要原对象，或者你想要避免代价高昂的数据复制，那么你应该使用移动构造函数。

  • 测试代码

    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
51
52
53
54
55
56

      #include <iostream>
    
  class MyClass
  {
  public:
      int *data;
      int size;
      MyClass() : size(10), data(new int[10])
      {
          for (int i = 0; i < 10; i++)
          {
              data[i] = i;
          }
          std::cout << "constructor" << std::endl;
      }
      // 拷贝构造函数
      MyClass(const MyClass &other) : size(other.size), data(new int[other.size])
      {
          std::cout << "copy constructor" << std::endl;
    
          std::copy(other.data, other.data + other.size, data);
      }
    
      ~MyClass()
      {
          std::cout << "destructor" << std::endl;
          delete[] data;
      }
  };
    
  int main()
  {
      auto obj1 = new MyClass();
      MyClass *obj2 = std::move(obj1);
    
      std::cout << obj1 << std::endl;
      std::cout << obj2 << std::endl;
      std::cout << &obj1 << std::endl;
      std::cout << &obj2 << std::endl;
      // *obj1->a = 100;
    
      std::cout << *obj1->data << std::endl;
      std::cout << *obj2->data << std::endl;
    
      std::cout << obj1->data << std::endl;
      std::cout << obj2->data << std::endl;
    
      auto obj3(std::move(*obj2));
      std::cout << &obj3 << std::endl;
      std::cout << obj3.data << std::endl;
      std::cout << *obj3.data << std::endl;
      std::cout << obj2->data << std::endl;
    
      delete obj1;
      return 0;
  }

    结果：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

      constructor
  0xfd1400
  0xfd1400
  0x62fe08
  0x62fe00
  0
  0
  0xfd1420
  0xfd1420
  copy constructor
  0x62fdf0
  0xfd1450
  0
  0xfd1420
  destructor
  destructor

总结：

结合测试用例，可以看出如果直接std::move一个普通指针的话，只是简单把这个指针变成右值，赋值给一个新的指针变量，普通指针没有移动构造函数。就相当于定义了一个新的指针变量，里面指向地址是原指针的内容。

一般情况不会这么这么使用。

扩展：结合unique_ptr和std::move一起使用

结合移动语义和 unique_ptr 可以实现资源的高效管理，避免资源泄漏或重复释放等问题。unique_ptr 是一个独占所有权的智能指针，它通过 RAII（资源获取即初始化）机制来确保在离开作用域时释放所管理的资源。同时，unique_ptr 支持移动语义，可以实现资源的高效转移。

下面是一个使用 unique_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 <iostream>
#include <memory>

class Object {
public:
    Object() { std::cout << "Object constructed\\n"; }
    ~Object() { std::cout << "Object destroyed\\n"; }
};

int main() {
    // 创建一个 unique_ptr，管理一个 Object 对象
    std::unique_ptr<Object> ptr(new Object);

    // 使用移动语义将 ptr 转移给另一个 unique_ptr
    std::unique_ptr<Object> ptr2(std::move(ptr));

    // 此时 ptr 不再管理 Object 对象，可以被释放或重用
    if (ptr == nullptr) {
        std::cout << "ptr is nullptr\\n";
    }

    // ptr2 管理 Object 对象，会在离开作用域时自动释放
    return 0;
}

在上面的示例中，我们首先创建了一个 unique_ptr 对象 ptr，并将其初始化为指向一个 Object 对象。然后，我们使用移动语义将 ptr 转移给另一个 unique_ptr 对象 ptr2，此时 ptr 不再管理 Object 对象，可以被释放或重用。最后，ptr2 管理 Object 对象，会在离开作用域时自动释放。

需要注意的是，由于 unique_ptr 使用了独占所有权模型，因此我们应该尽量避免直接使用裸指针来操作被 unique_ptr 管理的对象。如果必须使用裸指针，也应该将其转换为智能指针，以确保资源的正确管理。例如：

1
2
3
4
5
6
7
8

void do_something(Object* ptr) {
    // 将裸指针转换为 unique_ptr，以确保资源的正确管理
    std::unique_ptr<Object> obj(ptr);

    // 在 obj 管理的 Object 对象上进行操作
    // ...
}

在上面的示例中，我们将一个裸指针转换为 unique_ptr，以确保在离开函数作用域时正确释放所管理的资源。

C++中基类的析构函数调用虚函数

在C++中，基类的析构函数可以调用虚函数，但在实际执行析构过程中，虚函数调用不会派发到派生类的覆盖版本。也就是说，如果在基类的析构函数中调用一个虚函数，那么将会调用基类的版本，而不是派生类的版本。这是因为在执行析构函数时，对象的派生部分已经被析构，派生类的数据成员可能已经不存在了，所以C++规定在析构函数中，虚函数调用不会下沉到派生类。

以下是一个例子来展示这个行为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

class Base {
public:
    virtual ~Base() {
        std::cout << "Base destructor.\\n";
        print();   // 调用虚函数
    }
    virtual void print() const { std::cout << "Base print.\\n"; }
};

class Derived : public Base {
public:
    ~Derived() { std::cout << "Derived destructor.\\n"; }
    void print() const override { std::cout << "Derived print.\\n"; }
};

int main() {
    Base* b = new Derived();
    delete b;
    return 0;
}

在这个例子中，在析构Base对象时，Base的析构函数会调用print函数。但是，尽管Derived类覆盖了print函数，Base的析构函数中的print调用仍然会调用Base类的版本，而不是Derived类的版本。这是因为在Base的析构函数开始执行时，Derived的析构函数已经完成，Derived的部分已经不存在了。如果print函数依赖于Derived的任何数据成员，那么在此时调用Derived的版本可能会导致未定义的行为。

因此，一般来说，应该避免在析构函数中调用虚函数，因为这可能导致意外的行为。

C++计算结构体成员偏移量

构建一个宏函数，提供结构体类型和成员变量名称，计算该变量在结构体中的偏移量。

在C++中，你可以使用offsetof宏来获取结构体中成员的偏移量。这是一个预处理器宏，它接受两个参数：一个类型和该类型的成员名称，然后返回该成员在该类型对象中的字节偏移量。

下面是如何使用offsetof宏的一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <cstddef>

struct MyStruct {
    int a;
    double b;
    char c;
};

int main() {
    std::cout << "Offset of 'a' : " << offsetof(MyStruct, a) << "\\n";
    std::cout << "Offset of 'b' : " << offsetof(MyStruct, b) << "\\n";
    std::cout << "Offset of 'c' : " << offsetof(MyStruct, c) << "\\n";
    return 0;
}

在这个例子中，offsetof(MyStruct, a)返回的是a成员在MyStruct中的偏移量，这通常是0，因为a是结构体的第一个成员。offsetof(MyStruct, b)和offsetof(MyStruct, c)分别返回b和c成员的偏移量。

注意，offsetof宏只能用于POD（Plain Old Data）类型。如果你尝试使用它来获取非POD类型的成员偏移量，那么结果是未定义的。在C++中，POD类型是简单的、可以通过复制内存来复制其值的类型，例如内置类型、数组和结构。

offsetof宏的具体实现可能因编译器的不同而有所不同，但通常，它基于一个事实，那就是在C++中，一个结构体或类的实例的地址就是它的首个数据成员的地址。offsetof宏通常定义如下：

1

#define offsetof(type, member) ((size_t) &((type*)0)->member)

这个宏首先将0强制转换为type指针，这样得到的就是一个指向地址0的type指针，然后它通过指针访问成员member的地址。由于type的实例在地址0，所以访问的地址就是member的偏移量。

注意，虽然这个宏在许多情况下可以正常工作，但是它实际上是未定义的行为，因为它试图访问空指针的成员。然而，由于offsetof宏只是计算地址而不是真正访问成员，所以在实际中，这通常不会造成问题。

至于POD（Plain Old Data）类型，它包括了C++中一些简单的类型，这些类型可以通过复制内存来复制其值，例如：

  • 所有基本数据类型，例如int、char、double等。
  • 指针类型。
  • POD类型的数组。
  • 不包含构造函数、析构函数、或虚函数的结构体或类，其所有非静态成员都是POD类型，且没有任何基类或私有或保护成员。

简单来说，POD类型是那些可以用简单的内存复制来完全复制其值的类型，这使得它们可以兼容C语言的数据类型和结构。

Linux socket编程

Linux中socket编程时，有一个复用的API，setaddr啥。阻塞和非阻塞编程。

socket地址复用

在Linux中，为了使得一个socket地址（IP地址和端口号）可以被多个socket同时使用，我们通常需要设置socket的SO_REUSEADDR选项。这在服务器程序中尤其有用，因为它允许服务器在重启后立即重新绑定到相同的地址，而不是等待系统清理之前服务器使用的地址。

你可以使用setsockopt函数来设置这个选项。下面是一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <sys/types.h>
#include <sys/socket.h>

int sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0) {
    perror("socket");
    return -1;
}

int optval = 1;
if (setsockopt(sockfd, SOL_SOCKET, SO_REUSEADDR, &optval, sizeof(optval)) < 0) {
    perror("setsockopt");
    close(sockfd);
    return -1;
}

// now the socket can be bound to an address that is already in use

在这个例子中，我们首先创建了一个socket，然后使用setsockopt函数来设置SO_REUSEADDR选项。这意味着这个socket现在可以被绑定到一个已经在使用的地址。

注意，SO_REUSEADDR选项只允许在同一台机器上的多个socket同时绑定到同一个地址。如果你想在不同的机器上的socket能够绑定到同一个地址，你可能需要查看SO_REUSEPORT选项，这是一个在Linux 3.9及以后的版本中支持的特性。

阻塞和非阻塞编程

在Linux的socket编程中，阻塞和非阻塞模式是两种不同的IO处理方式。

  • 阻塞模式（Blocking mode）：在阻塞模式中，调用IO操作的线程会被操作系统挂起，直到IO操作完成为止。例如，当你调用read()函数时，如果没有数据可以读取，线程会被挂起，直到有数据可以读取为止。
  • 非阻塞模式（Non-blocking mode）：在非阻塞模式中，如果IO操作不能立即完成，函数会立即返回，并通常返回一个错误码表示“资源不可用”（在Linux中，这个错误码通常是EAGAIN或EWOULDBLOCK）。调用线程可以在稍后再次尝试IO操作，或者进行其他的工作。

以下是两种模式的代码示例：

阻塞模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <sys/types.h>
#include <sys/socket.h>
#include <unistd.h>

char buffer[1024];

int sockfd = socket(AF_INET, SOCK_STREAM, 0);
// Assume sockfd is connected...

ssize_t bytes_read = read(sockfd, buffer, sizeof(buffer));
if (bytes_read < 0) {
    perror("read");
    close(sockfd);
    return -1;
}

// If there was no data available when read() was called,
// the call blocked until there was data available.

非阻塞模式：

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

#include <sys/types.h>
#include <sys/socket.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>

char buffer[1024];

int sockfd = socket(AF_INET, SOCK_STREAM, 0);
// Assume sockfd is connected...

// Set the socket to non-blocking mode
int flags = fcntl(sockfd, F_GETFL, 0);
fcntl(sockfd, F_SETFL, flags | O_NONBLOCK);

ssize_t bytes_read = read(sockfd, buffer, sizeof(buffer));
if (bytes_read < 0) {
    if (errno == EAGAIN || errno == EWOULDBLOCK) {
        // The read would have blocked. We can try again later.
    } else {
        perror("read");
        close(sockfd);
        return -1;
    }
}

// If there was no data available when read() was called,
// the call returned immediately with an error.

使用非阻塞IO可以在单个线程中处理多个socket，这在开发高性能的网络服务器时非常有用。然而，非阻塞IO也会带来更复杂的编程模型，因为你需要处理”资源不可用”的情况，并且可能需要使用某种形式的事件驱动编程或异步IO。

  • 非阻塞模式扩展

    在非阻塞模式下，如果资源不可用（例如，socket的接收缓冲区没有数据可读，或发送缓冲区已满无法写入更多数据），read()或write()函数会立即返回，并设置错误码为EAGAIN或EWOULDBLOCK。

    对于这种情况，一种常见的处理策略是：记录下这种状态，并在稍后再次尝试进行IO操作。

    以下是一个处理非阻塞写的示例：

    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 <sys/types.h>
  #include <sys/socket.h>
  #include <unistd.h>
  #include <fcntl.h>
  #include <errno.h>
    
  char buffer[1024] = "Hello, world!";
  size_t buffer_len = sizeof(buffer);
  size_t buffer_pos = 0;
    
  int sockfd = socket(AF_INET, SOCK_STREAM, 0);
  // Assume sockfd is connected...
    
  // Set the socket to non-blocking mode
  int flags = fcntl(sockfd, F_GETFL, 0);
  fcntl(sockfd, F_SETFL, flags | O_NONBLOCK);
    
  while (buffer_pos < buffer_len) {
      ssize_t bytes_written = write(sockfd, buffer + buffer_pos, buffer_len - buffer_pos);
      if (bytes_written >= 0) {
          buffer_pos += bytes_written;
      } else if (errno == EAGAIN || errno == EWOULDBLOCK) {
          // The write would have blocked. We can try again later.
          // Here you might want to use select(), poll(), or epoll()
          // to wait until the socket becomes writable again.
      } else {
          perror("write");
          close(sockfd);
          return -1;
      }
  }

    在这个例子中，如果write()操作因为资源不可用而不能立即完成，我们简单地退出循环，并在稍后再次尝试。

    在实际的应用中，你可能会使用select()，poll()或epoll()等函数来等待socket变为可写，这样可以避免无效的循环，并能在同一线程中处理多个socket。此外，如果写入的数据量大，你可能需要将未写完的数据保存到一个队列或缓冲区中，然后在socket可写时再从队列或缓冲区中取出数据进行写入。

fork 内存空间

fork使用，父进程中一个指针指向一个地址，子进程中该指针是同样的地址，指向同样的空间吗。

在调用 fork() 后，子进程会获得一份与父进程完全相同的内存副本，也就是说，子进程会拥有与父进程相同的变量、指针和地址空间。因此，如果在父进程中有一个指针指向某个地址，那么在子进程中这个指针也会指向同样的地址。

但是，需要注意的是，虽然指针的值在子进程中和父进程中相同，但是它们指向的内存空间并不是同一个。在子进程中，指针指向的内存空间是父进程中对应空间的副本，两个进程分别拥有各自独立的内存空间。因此，在父进程或子进程中修改指针指向的内存空间，不会影响到另一个进程中指针所指向的内存空间。

以下是一个简单的示例代码，展示了父进程和子进程中指针的情况：

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 <stdio.h>
#include <unistd.h>

int main() {
    int a = 42;
    int *ptr = &a;
    pid_t pid = fork();

    if (pid == 0) {
        // child process
        printf("Child process:\\n");
        printf("ptr value: %d\\n", *ptr);
        printf("ptr address: %p\\n", ptr);
        *ptr = 24;
        printf("ptr value after modification: %d\\n", *ptr);
        printf("ptr address after modification: %p\\n", ptr);
    } else if (pid > 0) {
        // parent process
        printf("Parent process:\\n");
        printf("ptr value: %d\\n", *ptr);
        printf("ptr address: %p\\n", ptr);
        *ptr = 72;
        printf("ptr value after modification: %d\\n", *ptr);
        printf("ptr address after modification: %p\\n", ptr);
    } else {
        printf("fork failed\\n");
        return 1;
    }

    return 0;
}

在这个例子中，首先在父进程中定义了一个变量 a 和一个指针 ptr，并将指针指向变量 a 的地址。然后调用 fork() 创建子进程，子进程中会输出指针的值和地址，并进行一些修改，父进程也会输出指针的值和地址并进行一些修改。

运行这个程序后，可以看到子进程和父进程中指针的值和地址是相同的，但是它们指向的内存空间并不是同一个。因此，子进程和父进程中的修改不会相互影响。

注意

父进程和子进程中的相同的指针变量指向的实际上是不同的内存空间。也就是说，如果父进程改变了该指针指向的内存内容，这个改变不会影响到子进程，反之亦然。

这是由于操作系统使用了一种称为写时复制（Copy-on-Write, CoW）的技术。在fork()系统调用时，并不会立即复制父进程的内存，而是等到父进程或子进程试图修改内存时，操作系统才会复制那部分内存。这样可以提高fork()的效率，并节省内存资源。

c++中继承的区别

C++中的类可以以三种不同的方式继承基类：public、protected和private。这些访问修饰符决定了基类成员在派生类中的访问级别：

  1. Public 继承：基类中的公有成员在派生类中仍然是公有的，基类中的保护成员在派生类中仍然是保护的，基类中的私有成员在派生类中不可访问。
  2. Protected 继承：基类中的公有成员和保护成员在派生类中都变为保护的，基类中的私有成员在派生类中不可访问。
  3. Private 继承：基类中的公有成员和保护成员在派生类中都变为私有的，基类中的私有成员在派生类中不可访问。

下面是一个示例来说明这些差异：

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

class Base {
public:
    int public_member;
protected:
    int protected_member;
private:
    int private_member;
};

class PublicDerived : public Base {
    // public_member is public
    // protected_member is protected
    // private_member is not accessible
};

class ProtectedDerived : protected Base {
    // public_member is protected
    // protected_member is protected
    // private_member is not accessible
};

class PrivateDerived : private Base {
    // public_member is private
    // protected_member is private
    // private_member is not accessible
};

注意，无论基类成员在派生类中的访问级别如何，都不会影响它们在基类中的访问级别。也就是说，基类中的私有成员总是只能在基类中访问，而不论继承方式如何。

同时，这些访问修饰符（public、protected、private）也决定了派生类的类型与基类类型的转换方式。对于public继承，任何地方都可以将派生类对象视为基类对象。对于protected和private继承，只有在派生类的成员函数中才可以将派生类对象视为基类对象。

进一步解释上面最后一句话。

在派生类的成员函数中，可以将派生类的对象转换为基类类型的指针或引用。这种转换是基于”是一个（is-a）”的关系，因为派生类的实例也是基类的实例。但是，这种转换的可见性受到继承方式的限制。具体来说，如果是public继承，那么在任何地方都可以把派生类的对象转换为基类类型的指针或引用；如果是protected或private继承，那么只有在派生类的成员函数中才可以进行这种转换。

下面是一个例子：

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

class Base {
public:
    int x;
};

class PublicDerived : public Base {
};

class PrivateDerived : private Base {
};

void test() {
    PublicDerived pd;
    pd.x = 1; // OK
    Base* b1 = &pd; // OK

    PrivateDerived prd;
    //prd.x = 1; // Error: 'x' is not accessible
    //Base* b2 = &prd; // Error: Cannot convert 'PrivateDerived*' to 'Base*'
}

class DerivedFromPrivate : private Base {
    void foo() {
        x = 1; // OK
        Base* b = this; // OK
    }
};

在这个例子中，PublicDerived是公开继承Base的，所以我们可以在test函数中访问pd.x，并且可以将PublicDerived对象的地址赋给Base指针。但是，PrivateDerived是私有继承Base的，所以我们不能在test函数中访问prd.x，也不能将PrivateDerived对象的地址赋给Base指针。然而，在DerivedFromPrivate的成员函数foo中，我们可以访问基类的x成员，并且可以将this指针赋给Base指针，因为这些操作都发生在派生类的成员函数中。

C++运算符重载

在C++中，你可以重载大多数的运算符，包括[](取数组)、%(取模)、&(位运算)。但不能重载&&(逻辑与),下面是具体的例子：

[]运算符的重载：

这通常在实现自定义数组或集合类时使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class MyArray {
    int arr[10];

public:
    MyArray() {
        for(int i=0; i<10; i++) {
            arr[i] = i;
        }
    }

    int& operator[](int index) {
        return arr[index];
    }
};

// 使用：
MyArray a;
a[3] = 10;  // 使用重载的[]运算符

%运算符的重载：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class MyClass {
    int val;

public:
    MyClass(int v) : val(v) {}

    int operator%(int other) {
        return val % other;
    }
};

// 使用：
MyClass a(10);
int remainder = a % 3;  // 使用重载的%运算符

&运算符的重载：

这通常在实现自定义的位操作时使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class MyClass {
    int val;

public:
    MyClass(int v) : val(v) {}

    int operator&(int other) {
        return val & other;
    }
};

// 使用：
MyClass a(10);
int result = a & 3;  // 使用重载的&运算符

&&运算符的重载：

在C++中，你不能重载逻辑运算符&&。这是因为这些运算符涉及到短路求值（short-circuit evaluation），也就是说，如果左操作数已经足够确定整个表达式的值，那么右操作数就不会被求值。如果你尝试重载这些运算符，你就无法保证这种行为。因此，为了避免混淆，C++禁止重载这些运算符。

  • 进一步解释短路求值

    逻辑运算符 &&（逻辑与）和 ||（逻辑或）在 C++ 中是不能被重载的，主要原因是它们涉及到了“短路求值”（Short-circuit evaluation）的特性。

    “短路求值”是指在计算逻辑表达式时，一旦表达式的值可以确定，就不再计算后面的部分。这是因为在逻辑运算中，“与”运算 && 和 “或”运算 || 具有如下的特性：

    • 对于 && 运算，如果左边的表达式结果为 false，那么无论右边的表达式的值是 true 还是 false，整个表达式的结果都是 false。所以，如果左边的表达式值为 false，就没有必要再计算右边的表达式，可以直接确定整个表达式的值为 false。
    • 对于 || 运算，如果左边的表达式结果为 true，那么无论右边的表达式的值是 true 还是 false，整个表达式的结果都是 true。所以，如果左边的表达式值为 true，就没有必要再计算右边的表达式，可以直接确定整个表达式的值为 true。

    如果允许重载 && 和 || 运算符，那么这两个运算符的短路求值特性就无法得到保证，因为运算符重载实际上是函数调用，所有的参数在调用前都需要被求值，无法做到“短路”。这可能会导致程序的行为与预期不符，因此 C++ 不允许重载这两个运算符。

    例如，假设我们有一个表达式 a && b，其中 a 和 b 都是函数调用，如果 a 返回 false，那么根据短路求值，b 应该不会被调用。但是，如果我们重载了 && 运算符，那么 a 和 b 都会被调用，这可能会改变程序的行为。

以上是C++中关于运算符重载的一些基本规则和例子。在实际编程中，运算符重载应当谨慎使用，以避免混淆和误解。一般来说，只有当重载的运算符的行为与其原始的行为非常接近时，才应该使用运算符重载。

文件系统

et2、3、4、NTFS

1. ext2

ext2（second extended filesystem）是Linux下使用的一种文件系统。它是Linux最早的文件系统之一，由Rémy Card在1993年开发，以取代原始的ext文件系统。

ext2不支持日志功能，这意味着如果系统在写入数据时崩溃或意外关闭，文件系统可能会处于不一致的状态。此时需要使用fsck（文件系统检查和修复）工具进行修复，这可能需要较长的时间。然而，ext2的性能很好，且结构简单，使其成为许多嵌入式系统和闪存驱动设备的理想选择。

2. ext3

ext3（third extended filesystem）是ext2的直接升级版本，由Stephen Tweedie在2001年开发。它在ext2的基础上添加了日志功能，这使得在系统崩溃或意外关闭后能够快速恢复到一致的状态，而无需进行耗时的fsck操作。

ext3完全向后兼容ext2，这意味着你可以在不损失数据的情况下将ext2文件系统升级为ext3，反之亦然。

3. ext4

ext4（fourth extended filesystem）是ext3的一个更新版本，于2008年发布。它增加了许多新特性，如更大的单个文件大小（最大可以达到16TB），更大的总文件系统大小（最大可以达到1EB），更多的子目录（单个目录下可以有超过65000个子目录），以及更快的文件系统检查等。

和ext3一样，ext4也向后兼容ext3和ext2，你可以在不损失数据的情况下将ext2或ext3文件系统升级为ext4。

4. NTFS

NTFS（New Technology File System）是Microsoft开发的文件系统，最早在Windows NT 3.1中引入。它提供了许多高级功能，如日志功能（使文件系统能够快速恢复到一致的状态）、文件和目录权限管理、硬链接和软链接、压缩、加密等。

NTFS的一个重要特性是它对metadata的完整性支持。这意味着如果系统在写入数据时崩溃或意外关闭，文件系统的元数据（如文件大小、位置等）仍然保持一致。

NTFS是Windows操作系统的默认文件系统，但在Linux和其他Unix-like系统中也可以通过NTFS-3G等工具进行读写。

KMP

假设我们有一个文本串 “ABABABCAB”，我们想在其中找到模式串 “ABABC”。使用 KMP 算法的话，首先我们需要创建一个部分匹配表。

部分匹配表的创建方法是：对于模式串的每个位置，找出该位置左侧的所有前缀和后缀的最长公共元素长度。我们先假定模式串 “ABABC” 的部分匹配表如下：

ABABC
00120

我们开始从文本串的第一个字符开始匹配。每当字符匹配，我们就将文本串和模式串的位置都向后移动一位。一旦出现不匹配的字符，我们就查看模式串中最后一个匹配字符的部分匹配值。

例如，当我们在文本串的第5位 ‘A’ 和模式串的第5位 ‘C’ 不匹配时，我们看到模式串的前4位 ‘ABAB’ 的最后一个字符 ‘B’ 的部分匹配值为2。这意味着 ‘ABAB’ 的最长前缀和后缀公共元素是 ‘AB’，长度为2。

因此，我们将模式串向右移动2位，使得 ‘AB’ 与文本串中的 ‘AB’ 对齐。然后，我们继续比较文本串的下一个字符 ‘A’ 和模式串的当前字符 ‘A’，由于它们匹配，所以我们继续进行。

这样，每当字符不匹配，我们就利用部分匹配表跳过一些已知不会匹配的字符，从而提高了搜索效率。

匹配表构建：

对于模式串的每个位置，计算该位置左侧的所有前缀和后缀的最长公共元素长度，可以通过以下步骤进行：

以模式串 “ABABC” 为例，我们为每个字符构建部分匹配表。

  1. 字符 ‘A’：这是模式串的第一个字符，所以其左侧没有其他字符，因此它的部分匹配值为 0。
  2. 字符 ‘B’：它的左侧只有一个字符 ‘A’。既然 ‘A’ 没有前缀和后缀，所以它的部分匹配值也是 0。
  3. 字符 ‘A’：它的左侧有两个字符 ‘AB’。’AB’ 的所有前缀有：’A’，所有后缀有：’B’。它们没有公共元素，因此这个位置的部分匹配值为 0。
  4. 字符 ‘B’：它的左侧有三个字符 ‘ABA’。’ABA’ 的所有前缀有：’A’, ‘AB’，所有后缀有：’A’, ‘BA’。它们的最长公共元素是 ‘A’，长度为1，因此这个位置的部分匹配值为 1。
  5. 字符 ‘C’：它的左侧有四个字符 ‘ABAB’。’ABAB’ 的所有前缀有：’A’, ‘AB’, ‘ABA’，所有后缀有：’B’, ‘AB’, ‘BAB’。它们的最长公共元素是 ‘AB’，长度为2，因此这个位置的部分匹配值为 2。

通过上述步骤，我们就得到了模式串 “ABABC” 的部分匹配表：

ABABC
00120

实际上，计算部分匹配表是一个动态规划的过程，可以通过一些优化的方法来提高效率，但基本思想是一样的。

代码实现：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

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

// 这是我们之前定义的函数，用于计算部分匹配表
vector<int> computePrefixFunction(string pattern)
{
    int m = pattern.length();
    vector<int> pi(m);
    pi[0] = 0;
    int j = 0;

    for (int i = 1; i < m; ++i)
    {
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        if (pattern[i] == pattern[j])
        {
            ++j;
        }

        pi[i] = j;
    }

    return pi;
}

// KMP 字符串匹配函数
void KMP(string text, string pattern)
{
    int n = text.length();
    int m = pattern.length();
    vector<int> pi = computePrefixFunction(pattern);
    cout << "部分匹配表为：" << endl;
    for (auto i : pi)
    {
        cout << i << " ";
    }
    cout << endl;

    int j = 0;

    for (int i = 0; i < n; ++i)
    {
        while (j > 0 && text[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        if (text[i] == pattern[j])
        {
            ++j;
        }

        if (j == m)
        {
            cout << "Pattern found at index: " << i - m + 1 << endl;
            j = pi[j - 1];
        }
    }
}

int main()
{
    string text = "ABABABCAB";
    string pattern = "ABABC";
    KMP(text, pattern);

    return 0;
}

扩展

  • RAII

    RAII是Resource Acquisition Is Initialization的缩写，意为“资源获取即初始化”，是一种C++编程技巧，用于管理资源的生命周期。在RAII中，资源的获取和释放是与对象的生命周期绑定在一起的，即资源的获取在对象构造时进行，资源的释放在对象析构时进行，从而确保资源的正确获取和释放，避免资源泄漏和使用错误。

    RAII的核心思想是将资源的管理和对象的生命周期绑定在一起，利用对象的构造和析构函数管理资源，从而保证资源的正确获取和释放。在C++中，可以使用智能指针、容器、锁等RAII封装类来管理资源。

    例如，我们可以使用std::unique_ptr来管理动态分配的内存，如下所示：

    1
2
3
4
5
6
7
8
9
10
11
12
13

      #include <memory>
    
  int main() {
      // 使用unique_ptr管理动态分配的内存
      std::unique_ptr<int> ptr(new int(10));
    
      // 使用ptr指向的内存
      int value = *ptr;
    
      // 当ptr离开作用域时，会自动释放它所管理的内存
      return 0;
  }

    在上述示例中，我们使用std::unique_ptr来管理动态分配的内存。当ptr离开作用域时，会自动调用析构函数，释放它所管理的内存，从而避免了内存泄漏的问题。

    另外，RAII还可以用于管理其他资源，如文件句柄、网络连接、锁等，例如使用std::lock_guard来管理std::mutex的锁，如下所示：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

      #include <mutex>
  #include <thread>
    
  std::mutex mtx;
    
  void foo() {
      // 创建一个lock_guard对象，自动获取mtx的锁
      std::lock_guard<std::mutex> lock(mtx);
    
      // 在临界区域执行操作
      // ...
  }
    
  int main() {
      std::thread t1(foo);
      std::thread t2(foo);
    
      t1.join();
      t2.join();
    
      return 0;
  }

    在上述示例中，我们使用std::lock_guard来管理std::mutex的锁，它会在构造函数中获取锁，在析构函数中释放锁，从而避免了忘记释放锁的问题。

    总之，RAII是一种重要的C++编程技巧，可以有效地管理资源的生命周期，避免资源泄漏和使用错误，提高代码的可靠性和安全性。

  • 内存布局

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

      struct MyStruct
  {
      int a;
      double b;
      char c;
      void test() { std::cout << "test" << std::endl; }
  };
    
  int main()
  {
      std::cout << "Offset of 'a' : " << offsetof(MyStruct, a) << "\n";
      std::cout << "Offset of 'b' : " << offsetof(MyStruct, b) << "\n";
      std::cout << "Offset of 'c' : " << offsetof(MyStruct, c) << "\n";
      std::cout << "size " << sizeof(MyStruct) << std::endl;
    
      return 0;
  }

    输出：

    1
2
3
4

      Offset of 'a' : 0
  Offset of 'b' : 8
  Offset of 'c' : 16
  size 24

    成员函数：

    成员函数（或者称为方法）不像数据成员那样存储在对象的内存布局中。这是因为无论你创建多少个对象，每个对象都会有自己的数据成员的副本，但它们共享同一个成员函数的代码。

    成员函数的代码通常存储在程序的文本段（也称为代码段）。这是程序内存布局的一部分，主要用于存储程序的机器代码。每个成员函数只有一份代码，由所有对象共享。这意味着，无论你创建多少个对象，成员函数的代码只存储一次。

    当你调用一个对象的成员函数时，这个函数知道它正在操作哪个对象，是通过在调用时隐式地传递一个指向对象的this指针实现的。这就是为什么你可以在成员函数中访问调用它的对象的数据成员，即使这个函数的代码是由所有对象共享的。

    因此，你在代码中看到的sizeof(MyStruct)只计算了数据成员的大小，而没有计算成员函数的大小，因为成员函数并不是对象的一部分。同时，offsetof也只能用于数据成员，不能用于成员函数，因为成员函数并不占据对象的存储空间。

    内存对齐

    内存对齐是一种优化内存访问的技术。一些特定的硬件平台只能在特定地址边界上访问特定类型的数据。例如，一个常见的情况是，一个int可能需要在4字节的边界上进行访问，而一个double可能需要在8字节的边界上进行访问。这种限制是由硬件的内存访问机制决定的。

    对于你的示例：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

      struct MyStruct1
  {
      int a;    // 4 bytes
      double b; // 8 bytes
      char c;   // 1 byte
  };
    
  struct MyStruct2
  {
      int a;    // 4 bytes
      char c;   // 1 byte
      double b; // 8 bytes
  };

    在许多平台上，MyStruct1和MyStruct2的内存布局将是不同的，因为编译器会插入填充字节以满足对齐要求。

    对于MyStruct1，int a后面可能会插入4个填充字节，以确保double b在8字节边界上。然后，char c后面可能会插入7个填充字节，以确保整个结构体的大小是最大对齐要求的倍数（这里是8）。所以，sizeof(MyStruct1)可能是24。

    对于MyStruct2，int a后面不需要插入填充字节，因为char c可以放在紧随int a后面的字节中。但是，char c后面可能会插入7个填充字节，以确保double b在8字节边界上。所以，sizeof(MyStruct2)可能是16。

    这只是一个可能的结果，实际的结果取决于具体的编译器和硬件平台。你可以使用sizeof()函数和offsetof()宏来查看实际的结果。

    请注意，一般来说，我们不应该依赖特定的内存布局，除非有特殊的需要，例如与硬件或网络协议进行交互。对于这种情况，可以使用字符数组或std::byte数组，并手动进行序列化和反序列化。

随笔
总结 招聘
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容

网络

C++ NEW FEATURE