Perf
0%

发表于 阅读次数： Changyan：

多线程编程

image-20230315184531017

  • C语言处理时间

long t0 = time(NULL); 获取从1970年1月1日到当前经过的秒数。

sleep(3);休眠3秒

long t1 = t0 + 3; t0时间的3秒后

usleep(3000000); 休眠3000000微秒

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

signed main(){
    auto t0 = std::chrono::steady_clock::now(); //获取当前时间点
    auto t1 = t0 + std::chrono::seconds(30);
    auto dt = t1 - t0; //获取两个时间点的时间差
    std::int64_t sec = std::chrono::duration_cast<std::chrono::seconds>(dt).count(); //时间差的秒数
    std :: cout << "time sep=" << sec << "ms\n";
    return 0;
}

time sep=30ms

  • 跨平台的sleep:
    • std::this_thread::sleep_for(std::chrono::milliseconds(400));
    • 当前线程休眠400ms

多线程

  • 现代C++中的多线程：std::thread
1
2
3
4
5
6
7
8
#include<thread>
main(){
    std::thread t1([&]{
        download("hello.zip");
    });
    interact();
    return 0;
}
  • 由于std::thread的实现背后是基于pthreads的，而且CMake提供了Threads包：
1
2
3
4
5
6
7
8
9
10
cmake_minimum_required(VERSION 3.10)

set(CMAKE_CXX_STANDARD 17)

project(cpptest LANGUAGES CXX)

add_executable(cpptest main.cpp)

find_package(Threads REQUIRED)
target_link_libraries(cpptest PUBLIC Threads::Threads)
  • 主线程等待子线程结束t1.join()：会等待t1进程结束
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<chrono>
#include<thread>
#include<string>

void download(std::string file){
    for(int i=0;i<10;++i){
        std::cout << "Downloading " << file 
                  << " (" << i*10 << "%)..." << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(300));
    }
    std::cout<<"Download complete: " << file << std::endl;
}

void interact(){
    std::string name;
    std::cout << "Please enter your name: " << std::endl;
    std::cin >> name;
    std::cout << "Hi, " << name << std::endl;
}

signed main(){
    std::thread t1([&]{
        download("hello.zip");
    });
    interact();
    std::cout<<"Waiting for child thread ... " << std::endl;
    t1.join();
    std::cout << "Child thread exited!" << std::endl;
    return 0;
}
  • 输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Please enter your name: Downloading hello.zip (
0%)...
Downloading hello.zip (10%)...
wyDownloading hello.zip (20%)...
h
Hi, wyh
Waiting for child thread ...
Downloading hello.zip (30%)...
Downloading hello.zip (40%)...
Downloading hello.zip (50%)...
Downloading hello.zip (60%)...
Downloading hello.zip (70%)...
Downloading hello.zip (80%)...
Downloading hello.zip (90%)...
Download complete: hello.zip
Child thread exited!

  • std::thread的析构函数会销毁线程

    • 遵循三五法则，std::thread同样遵循RAII思想和三五法则，自定义了析构函数，删除了拷贝构造/赋值函数，保留了移动构造/赋值函数
    • 所以会出现一个函数中某个线程在运行时，函数结束，线程调用其析构函数，会导致正在运行的线程出错

  • thread.detach():分离线程

    • 线程的声明周期不再由当前std::thread管理，而是在线程退出以后自动销毁
    • 但是进程结束后线程还是会自动退出的

  • 另外一种方法：在某个函数创建线程后用std::move()提交到全局变量vector<std::thread>中，然后在进程结束之前每个都join()一遍。

  • 还可以使用单例模式：

    • image-20230316094158213

异步

std::async接受一个带返回值的lambda函数

1
2
3
4
5
main(){
    std::function<int> fret = std::sync([&] {
       return download("hello.zip"); 
    });
}

自身返回一个std::future对象

  • lambda的函数体在另一个线程里执行
  • 最后调用furt.get()方法。如果此时线程没有运行完，会等待线程运行完后获取其返回值。

显示的等待:futr.wait();

std::wait_for(std::chrono::milliseconds(1000));

  • std::mutex互斥锁

std::lock_guard :符合RAII思想的上锁和解锁

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>
#include<vector>
#include<string>

signed main(){
    std::vector<int> arr;
    std::mutex mtx;
    std::thread t1 ([&]{
        for(int i=0;i<1000;++i){
            std::lock_guard grd(mtx);
            arr.push_back(i);
        }
    });
    std::thread t2([&]{
        for(int i=0;i<1000;++i){
            std::lock_guard grd(mtx);
            arr.push_back(i);
        }
    });
    t1.join();
    t2.join();
    return 0;
}
  • 析构函数会调用grd.unlock();

一个自由度更高的锁sdt::unique_lock()接受一个参数std::defer_lock,指定了这个参数之后不会在构造函数中调用mtx.lock()。需要之后自己手动进行grd.lock()

  • mtx.try_lock()

返回true表示上锁成功，否则上锁失败

  • mtx.try_lock_for(std::chrono::milliseconds());

尝试在一个时间内等待是否上锁成功

  • 在之前已经上过锁的情况下：mtx.lock()可以使用如下参数：std::unique_lock grd(mtx, std::adopt_lock);

  • std::unique_lock grd(mtx, std::try_to_lock);

  • 任何具有lock()和unlock()的类都可以作为std::lock_guard类型的参数，例如std::lock_guard grd2(grd1);可以这样嵌套

    python中的鸭子类型，C++称为concept

死锁解决

AB和BA的上锁会导致死锁问题，C++提供std::lock(mtx1, mtx2)来避免死锁问题。

  • std::lock的RAII版本std::scoped_lock

同一个线程重复调用lock()也会导致死锁问题。

  • 解决方法：std::recursive_mutex，会自动进行识别，如果是同一个线程对这个锁进行重复上锁，会计数器+1，解锁后计数器-1.但是会有性能损失。

数据结构的多线程安全

互斥量
  • vector<int>不是多线程安全的容器
  • 因此需要封装一个多线程安全的MyVector
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
#include<iostream>
#include<thread>
#include<mutex>
#include<vector>
#include<string>

struct MyVector{
    std::vector<int> m_arr;
    mutable std::mutex m_mtx;
public:
    void push_back(int x){
        m_mtx.lock();
        m_arr.push_back(x);
        m_mtx.unlock();
    }
    size_t size() const{
        m_mtx.lock();
        size_t res = m_arr.size();
        m_mtx.unlock();
        return res;
    }
};

signed main(){
    MyVector arr;
    std::thread t1([&](){
        for(int i=0;i<1000;++i){
            arr.push_back(i);
        }
    });
    std::thread t2([&](){
        for(int i=0;i<1000;++i){
            arr.push_back(i+1000);
        }
    });
    t1.join();
    t2.join();
    std::cout<<arr.size() <<std::endl; 
    return 0;
}

  • 如上为代理模式（设计模式）

  • 由于size()函数为了与vector保持一致使用了const，但是函数内对锁的内容有修改，因此需要在mtx之前加入mutable

  • std::shared_mutex读写锁

    • 对于读操作，使用mtx.lock_shared()，mtx.unlock_shared()
    • 对于写操作，使用mtx.lock()，mtx.unlock()

  • 符合RAII的lock_shared()

    • std::unique_lock针对lock()
    • std::shared_lock针对lock_shared()
      • shared_lock()支持参数defer_lock和owns_lock()

  • 符合RAII思想的访问者模式

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
#include<iostream>
#include<thread>
#include<mutex>
#include<vector>
#include<string>

struct MyVector{
    std::vector<int> m_arr;
    std::mutex m_mtx;
public:
    class Accessor{
        MyVector &m_that;
        std::unique_lock<std::mutex> m_guard;
    public:
        Accessor(MyVector &that) :
            m_that(that),m_guard(that.m_mtx) {}
        void push_back(int x)const{
            return (void)(m_that.m_arr.push_back(x));
        }   
        size_t size()const{
            return m_that.m_arr.size();
        }     
    };
    Accessor access(){
        return {*this};
    }
};

signed main(){
    MyVector arr;
    std::thread t1([&](){
        auto tmp = arr.access();
        for(int i=0;i<1000;++i){
            tmp.push_back(i);
        }
    });
    std::thread t2([&](){
        auto tmp = arr.access();
        for(int i=0;i<1000;++i){
            tmp.push_back(i+1000);    
        }
    });
    t1.join();
    t2.join();
    std::cout<<arr.access().size() <<std::endl; 
    return 0;
}
  • 分离存储类和访问类，通过存储类的访问类进行访问。
条件变量
  • 等待被唤醒
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<thread>
#include<mutex>
#include<vector>
#include<string>
#include<condition_variable>

signed main(){
    std::condition_variable cv;
    std::mutex mtx;

    std::thread t1([&]{
        std::unique_lock lck(mtx);
        cv.wait(lck);
        std::cout<<"t1 is awake"<<std::endl;
    }); 
    std::this_thread::sleep_for(std::chrono::milliseconds(400));
    std::cout<<"notifying"<<std::endl;
    cv.notify_one();
    t1.join();
    return 0;
}
  • notify_all()唤醒全部在等待的锁

原子操作

避免多线程使用同一个变量导致的错误：

  • 上锁：影响效率
  • std::atomic<T>,对其的操作+=,-= &= |= *= /=会被编译器转换为专门的指令。

std::atomic<int> counter

  • counter.store(0); 赋值的原子操作
  • counter.fetch_add(1); +=的原子操作，而且还能返回旧值
  • counter.load();获取值的原子操作；
  • counter.exchange(x); 读取的同时写入，返回的是旧值
  • counter.exchange_strong(old, value);读取原子变量的值和old进行比较，如果不相等将old值写入变量，否则将value值写入变量

发表于 阅读次数： Changyan：

模板元编程与函数式编程

模板元编程

  • 模板函数：默认参数类型
1
2
3
4
5
6
7
8
9
10
11
template <class T=int>
T two(){
    return 2;
}

template <int N>
void show_time(std::string s){
    for(int i=0;i<N;++i){
        std::cout<<s<<std::endl;
    }
}

​

  • 编译器优化案例
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
#include<iostream>
#include <time.h>

int sum(int n,bool debug){
	int res=0;
	for(int i=0;i<n;++i){
		res += i;
		if(debug)
			std::cout<<i<<"-th: "<<res<<std::endl;
	}
	return res;
}

template <bool debug>
int sum(int n){
	int res=0;
	for(int i=0;i<n;++i){
		res += i;
		if(debug)
			std::cout<<i<<"-th: "<<res<<std::endl;
	}
	return res;
}

int main(){
	int n;
	std::cin >> n;
	auto st=clock();
	std::cout<<sum(n ,true)<<std::endl;
	std::cout<<sum(n,false)<<std::endl;
	auto ed=clock();
	std::cout<<ed-st<<"ms"<<std::endl;
	st=ed;
	std::cout<<sum<true>(n)<<std::endl;
	std::cout<<sum<false>(n)<<std::endl;
	ed=clock();
	std::cout<<ed-st<<"ms"<<std::endl;
	return 0;
}

第一种sum每次循环的时候都需要做判断，对于性能有影响，而且编译器不好优化。后者(第二种sum)在编译器看来就是 if(false)，显然会被自动优化掉。

更进一步，可以用C++17的if constexpr保证编译器确定的分支。

  • 模板的惰性：延迟编译

假如有一个函数(有可能是错误的)，暂时未被调用，我们可以采用模板的惰性，只要没有被调用就不会实例化，因此可以加快编译速度。

  • 懒汉单例模式
1
2
3
4
auto &product_table(){
    static std::map<string,int> instance;
    return instance;
}
  • 可以通过decltype获取表达式的类型，typeid只有在有虚函数的时候才会起作用。

对于我想定义一个和之前定义过的函数一样的变量/函数，可以使用

declgtype(auto) p=func();

decltype(func()) p=func();

  • using
    • typedef std::vector<int> VecInt;和using VecInt=std::vector<int>;等价
    • typedef int (*PFunc)(int);和using PFunc=int(*)(int)等价
1
2
3
4
5
6
7
8
9
template<class T1,class T2>
auto add(std::vector<T1> const& a, std::vector<T2> const& b){
	using T0=decltype(T1{}+T2{});
	std::vector<T0> vec;
	for(int _=0;_<a.size();++_){
		vec.push_back(vec[_]);
	}
	return vec;
}
  • type_traits

函数式编程

函数也可以作为另一个函数的参数

  • 在lambda表达式中[&]用于捕获同一作用域中的变量。(闭包)此外还可以修改同一作用域下的变量
  • 但是可能会出现如下问题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#define debug(x) std::cout<<#x<<": "<<x<<std::endl

template<class Func>
void call_twice(Func const& func){
	debug(func(0));
	debug(func(1));
	debug(sizeof(Func));
}

auto make_twice(int fac){
	return [&](int n){
		return n*fac;
	};
}

int main(){
	auto twice = make_twice(2);
	call_twice(twice);
	return 0;
}

输出为

1
2
3
func(0): 0
func(1): 6422040
sizeof(Func): 8

这是因为make_twice函数在调用之后会对fac进行销毁，但是之前传入的是函数的引用，所在在fac销毁之后其指针会随意指向某处，导致输出很怪。

小彭老师的建议是对make_twice()函数进行修改：

1
2
3
4
5
auto make_twice(int fac){
	return [=](int n){
		return n*fac;
	};
}

这样输出就没有问题了

1
2
3
func(0): 0
func(1): 2
sizeof(Func): 4

此时可以把fac作为一个值存下来，而不是存下fac的指针。

因此，[&]需要保证lambda对象的声明周期不超过其捕获的所有引用的声明周期

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>
#define debug(x) std::cout<<#x<<": "<<x<<std::endl

// template<class Func>
void call_twice(std::function<int(int)> const& func){
	debug(func(0));
	debug(func(1));
	debug(sizeof(func));
}

std::function<int(int)> make_twice(int fac){
	return [=](int n){
		return n*fac;
	};
}

int main(){
	auto twice = make_twice(2);
	call_twice(twice);
	return 0;
}

这种形势下function<int(int)>是虚函数，会有额外的开销

1
2
3
func(0): 0
func(1): 2
sizeof(func): 32
  • lambada的用途：yield模式
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 <vector>
#include <type_traits>

template<class Func>
void fetch_data(Func const& func){
	for(int i=0;i<32;++i){
		func(i);
		func(i+0.5f);
	}
}

int main(){
	std::vector<int> res_i;
	std::vector<float> res_f;
	fetch_data([&] (auto const &x){
		using T = std::decay_t<decltype(x)>;
		if constexpr (std::is_same_v<T, int>){
			res_i.push_back(x);
		}else if constexpr (std::is_same_v<T, float>){
			res_f.push_back(x);
		}
	}
	);
	return 0;
}

  • 立即求值

  • 匿名递归

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

int main(){
	std::vector<int> arr={1,4,2,8,5,7,1,4};
	std::set<int> visited;
	auto dfs = [&] (auto const &dfs, int index) ->void{
		if(visited.find(index)==visited.end()){
			visited.insert(index);
			std::cout<<index<<std::endl;
			int next=arr[index];
			dfs(dfs, next);
		}
	};
	dfs(dfs, 0);
	return 0;
}
  • 常用容器tuple

std::tuple<...>可以讲多个不同类型的值打包成一个。尖括号里填各种类型

之后可以使用std::get<0>([tuplename])获取对应索引值

  1. 结构化绑定
1
2
auto tup = std::tuple(3,3.14,"6");
auto [x,y,z] = tup;
  1. tuple还可以使用在有多个返回值的函数
  • 常用容器optional
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 <cmath>
#include <optional>
#include <memory>
#include <vector>

std::optional<float> mysqrt(float x){
	if(x>=0.f) {
		return std::sqrt(x);
	}else{
		return std::nullopt;
	}
}

int main(){
	auto res = mysqrt(-3.f);
	if(res.has_value()){
		std::cout<<"answer: "<<res.value()<<std::endl;
	}else{
		std::cout<<"failed"<<std::endl;
	}
	return 0;
}
  • optional:operator bool()和has_value()等价,是一个更安全的指针
  • variant是更安全的union,存储多个不同类型的值

我的作业:https://github.com/WangYuHang-cmd/hw03

发表于 分类于 阅读次数： Changyan：

RAII与智能指针

  • for_eachdui
1
2
3
4
5
6
7
8
9
10
#include<iostream>
#include<algorithm>
int sum=0;
void func(int x){sum += x;}
signed main(){
    std::vector<int> v={5,4,3,1};
    std::for_each(v.begin(), v.end(), func);
    std::cout<<sum<<std::endl;
    return 0;
}

引用自algorithm的模板函数，可以套用任何迭代器，引用对应参数调用func函数

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
#include<algorithm>
signed main(){
    int sum = 0;
    std::vector<int> v={5,4,3,1};
    std::for_each(v.begin(), v.end(), [&](int x){
        sum += x;
    });
    std::cout<<sum<<std::endl;
    return 0;
}

引用lambda表达式后，sum为一个局部变量。其中lambda表达式中[&]表示可以引用外部变量

  • C++20引入区间(ranges)
1
2
3
4
5
6
7
8
9
10
11
#include<ranges>
main(){
    std::vector v={1,2,3,4}; 
	for(auto &&vi:v
       | std::views::filter([] (auto &&x){return x>=0;})
       | std::views::tranform([] (auto &&x){return sqrtf(x);})
       ){
    	std::cout<<vi<<std::endl;
    }    
}

RAII(异常安全)

  • C++标准中保证当异常发生时会嗲用已经创建的析构函数，因此不需要final

  • 初始化表达式的优势

    1. 对于成员变量是const的时候，只能够在初始化列表中进行初始化

    2. 避免重复初始化(否则是先初始化为0再进行赋值，相当于两个操作)

    3. 避免了参数有 无参构造函数
    4. 若构造函数只有一个参数，可以使用=进行构造，但是如果要规定显示的构造方法，可以再构造函数前加上explicit
  • {}和()调用构造函数时都是显式类型转换，但是{}不是强制类型转换，从高精度向低精度转换不会报错,但是从高精度向低精度转换则会通过不了编译，而()是强制类型转换。

image-20230303104937987

int{3.14f}不可过编译但是float{3}可以

  • 若自己没有写构造函数，编译器默认生成无参构造函数（POD陷阱）
    • POD陷阱：以下类型并不会被初始化为0
      • int,float,double等基础类型
      • void Object等指针类习惯
      • 完全由这些类型组成的类
    • POD（plain-old-data）会被初始化为系统内存中的随机值，其存在是为了兼容C
  • 解决措施struct{int t{0};};或者struct{int t=10;};
  • 如果自己定义构造函数后还想编译器给你生成构造函数，则需要Class() = default;
  • 自定义拷贝赋值函数
1
Pig(Pig const &pegy):name(pegy.name), weight(pegy.weight){}

image-20230303195143615

  • 三五法则

    1. 如果一个类定义了析构函数，那么必须同时定义或删除拷贝构造函数和拷贝赋值函数：
    2. 如果一个类定义了拷贝构造函数，那么您必须同时定义或删除拷贝赋值函数，否则出错，删除可导致低效
    3. 如果一个类定义了移动构造函数，那么您必须同时定义或删除移动赋值函数，否则出错，删除可导致低效
    4. 如果一个类定义了拷贝构造函数或拷贝赋值函数，那么最好同时定义移动构造函数或移动赋值函数

image-20230303195116221

因此建议删除默认的拷贝构造函数Vector(Vector const &)=delete;如果不删除则默认是浅拷贝.

  • 拷贝和移动
1
2
3
4
5
6
7
void test_move(){
    std::vector<int> v1(10);
    std::vector<int> v2(200);
    v1 = std::move(v2);
    std::cout << "v1.size():" << v1.size() << std::endl;
    std::cout << "v2.size():" << v2.size() << std::endl;
}

有的时候需要把一个对象移动到另外一个对象上，然后销毁，有点像浅拷贝，但是并不完全一样(多一个销毁的动作)。因此我们可以靠std::move进行实现。就像上述的例子，v2被移动到v1之后原来的才会被销毁，从而防止双重free。

std::swap()在高性能计算中可以用来实现双缓存（ping-pong buffer）

交换复杂度是O(1)

作为返回值的时候自动默认为右值引用，即移动

三五法则说明不定义移动构造和移动赋值是低效的，但是可以保证不出错。但是最好的方式还是自己定义一个移动构造函数和移动赋值函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
Pig(Pig &&other){
    name=other.name;
    other.name="";
    weight=other.weight;
    other.weight=0;
    son=other.son;
    other.son=nullptr;
}
Pig &operator=(Pig &&other){
    this->~Pig();
    new (this) Pig(std::move(other));
    return *this;
}

RAII解决内存管理：

unique_ptr

#include<memory>

std::unique_ptr<Class> p=std::make_unique<Class>();

在每次return之前会自动调用delete p;

  • unique_ptr在使用的时候因为删除了拷贝函数，因此无法在函数中调用

调用方法：

  1. func()并不需要夺走资源的占有权，只是需要调用某个成员函数而已
1
2
3
4
5
6
void func(Class * p){
	p->do();
}
main(){
    func(p.get()); //p.get()获取指针
}
  1. 需要夺走资源的占有权，比如需要延长对象生命周期，或者将其加入到某个数据结构中
1
2
3
4
5
6
7
8
vector<Class> vec;
void func(std::unique_ptr<Class> p){
	vec.push_back(std::move(p));
}
main(){
    std::unique_ptr<Class> p = std::make_unique<Class>();
    func(std::move(p)); //p.get()获取指针
}

但是按照上述的方法，在std::move()之后原来的指针的方法就无法调用了，因为被释放掉了。一种解决方法：

1
2
3
4
5
6
7
8
9
10
vector<Class> vec;
void func(std::unique_ptr<Class> p){
	vec.push_back(std::move(p));
}
main(){
    std::unique_ptr<Class> p = std::make_unique<Class>();
    Class *raw_p = p.get();
    func(std::move(p)); //p.get()获取指针
	raw_p -> do();
}

但是会出现空悬指针的问题。解决方法：shared_ptr

shared_ptr

利用计数的方式，当一个shred_pre被初始化时，其计数器设为1，当被拷贝时计时器+1，当被析构时计数器-1，减到0时就自动销毁其他指向的对象。

但是由于非原子性操作，在多线程时会有问题。其次是会产生循环引用的问题。（死锁）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Class{
  	std::shared_ptr<Class> m_child;
    std::shared_ptr<Class> m_parent;
};

main(){
    auto parent = std::make_shared<Class>();
    auto child = std::make_shared<Class>();
    
    parent.m_child = child;
    child.m_parent = parent;
    
    parent = nullptr; //不会释放
    child = nullptr;  //不会释放
	return 0; 
}
解决方法1

将m_parent改成weak_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Class{
  	std::shared_ptr<Class> m_child;
    std::weak_ptr<Class> m_parent;
};

main(){
    auto parent = std::make_shared<Class>();
    auto child = std::make_shared<Class>();
    
    parent.m_child = child;
    child.m_parent = parent;
    
    parent = nullptr; //释放
    child = nullptr;  //释放
    
    std::cout << child.expired() << std::endl;
    
	return 0; 
}
  • weak_ptr不会增加shared_ptr的引用计数
  • 父窗口拥有子窗口天经地义，但是子窗口不能拥有父窗口

weak_ptr

weak_ptr被设计为与shared_ptr共同工作，可以从一个shared_ptr或者另一个weak_ptr对象构造，获得资源的观测权。但weak_ptr没有共享资源，它的构造不会引起指针引用计数的增加。同样，在weak_ptr析构时也不会导致引用计数的减少，它只是一个静静地观察者。

weak_ptr没有重载operator*和->，这是特意的，因为它不共享指针，不能操作资源，这是它弱的原因。

但是weak_ptr可以调用lock()函数从被观测的shared_ptr获得一个可用的shared_ptr对象

当创建一个weak_ptr时，要用一个shared_ptr来初始化它。不能使用weak_ptr直接访问对象，而必须调用lock。

此函数检查weak_ptr指向的对象是否仍存在。如果存在，lock返回一个指向共享对象的shared_ptr。与任何其它shared_ptr类似，只要此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
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#include "weak_ptr.hpp"
#include <iostream>
#include <memory>
#include <algorithm>
#include <string>
#include <vector>
 
///
// reference: http://en.cppreference.com/w/cpp/memory/weak_ptr
std::weak_ptr<int> gw;
 
void f()
{
	if (auto spt = gw.lock()) { // Has to be copied into a shared_ptr before usage
		std::cout << *spt << "\n";
	}
	else {
		std::cout << "gw is expired\n";
	}
}
 
int test_weak_ptr1()
{
	{
		auto sp = std::make_shared<int>(42);
		gw = sp;
 
		f();
	}
 
	f();
 
	return 0;
}
 
/
// reference: http://stackoverflow.com/questions/12030650/when-is-stdweak-ptr-useful
int test_weak_ptr2()
{
	// OLD, problem with dangling pointer
	// PROBLEM: ref will point to undefined data!
	int* ptr = new int(10);
	int* ref = ptr;
	delete ptr;
 
	// NEW
	// SOLUTION: check expired() or lock() to determine if pointer is valid
	// empty definition
	std::shared_ptr<int> sptr;
 
	// takes ownership of pointer
	sptr.reset(new int);
	*sptr = 10;
 
	// get pointer to data without taking ownership
	std::weak_ptr<int> weak1 = sptr;
 
	// deletes managed object, acquires new pointer
	sptr.reset(new int);
	*sptr = 5;
 
	// get pointer to new data without taking ownership
	std::weak_ptr<int> weak2 = sptr;
 
	// weak1 is expired!
 
	if (auto tmp = weak1.lock())
		std::cout << *tmp << '\n';
	else
		std::cout << "weak1 is expired\n";
 
	// weak2 points to new data (5)
 
	if (auto tmp = weak2.lock())
		std::cout << *tmp << '\n';
	else
		std::cout << "weak2 is expired\n";
 
	return 0;
}
 
//
// reference: https://msdn.microsoft.com/en-us/library/hh279672.aspx
class Controller
{
public:
	int Num;
	std::string Status;
	std::vector<std::weak_ptr<Controller>> others;
	explicit Controller(int i) : Num(i), Status("On")
	{
		std::cout << "Creating Controller" << Num << std::endl;
	}
 
	~Controller()
	{
		std::cout << "Destroying Controller" << Num << std::endl;
	}
 
	// Demonstrates how to test whether the pointed-to memory still exists or not.
	void CheckStatuses() const
	{
		for_each(others.begin(), others.end(), [](std::weak_ptr<Controller> wp) {
			try {
				auto p = wp.lock();
				std::cout << "Status of " << p->Num << " = " << p->Status << std::endl;
			}
			catch (std::bad_weak_ptr b) {
				std::cout << "Null object" << std::endl;
			}
		});
	}
};
 
void RunTest()
{
	std::vector<std::shared_ptr<Controller>> v;
 
	v.push_back(std::shared_ptr<Controller>(new Controller(0)));
	v.push_back(std::shared_ptr<Controller>(new Controller(1)));
	v.push_back(std::shared_ptr<Controller>(new Controller(2)));
	v.push_back(std::shared_ptr<Controller>(new Controller(3)));
	v.push_back(std::shared_ptr<Controller>(new Controller(4)));
 
	// Each controller depends on all others not being deleted.
	// Give each controller a pointer to all the others. 
	for (int i = 0; i < v.size(); ++i) {
		for_each(v.begin(), v.end(), [v, i](std::shared_ptr<Controller> p) {
			if (p->Num != i) {
				v[i]->others.push_back(std::weak_ptr<Controller>(p));
				std::cout << "push_back to v[" << i << "]: " << p->Num << std::endl;
			}
		});
	}
 
	for_each(v.begin(), v.end(), [](std::shared_ptr<Controller>& p) {
		std::cout << "use_count = " << p.use_count() << std::endl;
		p->CheckStatuses();
	});
}
 
int test_weak_ptr3()
{
	RunTest();
	std::cout << "Press any key" << std::endl;
	char ch;
	std::cin.getline(&ch, 1);
 
	return 0;
}
 
 
// reference: https://oopscenities.net/2014/08/03/c-smart-pointers-part-5-weak_ptr/
struct Child;
struct Parent
{
	std::shared_ptr<Child> child;
 
	~Parent() { std::cout << "Bye Parent" << std::endl; }
 
	void hi() const { std::cout << "Hello" << std::endl; }
};
 
struct Child
{
	std::weak_ptr<Parent> parent;
	//std::shared_ptr<Parent> parent; // memory leak
 
	~Child() { std::cout << "Bye Child" << std::endl; }
};
 
int test_weak_ptr4()
{
	auto parent = std::make_shared<Parent>();
	auto child = std::make_shared<Child>();
 
	parent->child = child;
	child->parent = parent;
	child->parent.lock()->hi();
	// child->parent->hi();
 
	return 0;
}
 
/
// reference: http://thispointer.com/shared_ptr-binary-trees-and-the-problem-of-cyclic-references/
class Node
{
	int value;
public:
	std::shared_ptr<Node> leftPtr;
	std::shared_ptr<Node> rightPtr;
	// Just Changed the shared_ptr to weak_ptr
	std::weak_ptr<Node> parentPtr;
	Node(int val) : value(val)     {
		std::cout << "Contructor" << std::endl;
	}
	~Node()     {
		std::cout << "Destructor" << std::endl;
	}
};
 
int test_weak_ptr5()
{
	std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
	ptr->leftPtr = std::make_shared<Node>(2);
	ptr->leftPtr->parentPtr = ptr;
	ptr->rightPtr = std::make_shared<Node>(5);
	ptr->rightPtr->parentPtr = ptr;
	std::cout << "ptr reference count = " << ptr.use_count() << std::endl;
	std::cout << "ptr->leftPtr reference count = " << ptr->leftPtr.use_count() << std::endl;
	std::cout << "ptr->rightPtr reference count = " << ptr->rightPtr.use_count() << std::endl;
	std::cout << "ptr->rightPtr->parentPtr reference count = " << ptr->rightPtr->parentPtr.lock().use_count() << std::endl;
	std::cout << "ptr->leftPtr->parentPtr reference count = " << ptr->leftPtr->parentPtr.lock().use_count() << std::endl;
 
	return 0;
}
  • 避免不必要的拷贝

函数定义参数的时候建议传参void func(Class const& c);在不改变值得情况下。

  1. P-IMPL 模式

    • 在类中使用Pimpl惯用法，具有如下优点：

    降低耦合
    信息隐藏
    降低编译依赖，提高编译速度
    接口与实现分离

    • Code in cppreference
    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
    #include <iostream>
    #include <memory>
    #include <experimental/propagate_const>

    // interface (widget.h)
    class widget {
        class impl;
        std::experimental::propagate_const<std::unique_ptr<impl>> pImpl;
     public:
        void draw() const; // public API that will be forwarded to the implementation
        void draw();
        bool shown() const { return true; } // public API that implementation has to call
        widget(int);
        ~widget(); // defined in the implementation file, where impl is a complete type
        widget(widget&&) = default;  // Note: calling draw() on moved-from object is UB
        widget(const widget&) = delete;
        widget& operator=(widget&&); // defined in the implementation file
        widget& operator=(const widget&) = delete;
    };

    // implementation (widget.cpp)
    class widget::impl {
        int n; // private data
     public:
        void draw(const widget& w) const {
            if(w.shown()) // this call to public member function requires the back-reference 
                std::cout << "drawing a const widget " << n << '\n';
        }
        void draw(const widget& w) {
            if(w.shown())
                std::cout << "drawing a non-const widget " << n << '\n';
        }
        impl(int n) : n(n) {}
    };
    void widget::draw() const { pImpl->draw(*this); }
    void widget::draw() { pImpl->draw(*this); }
    widget::widget(int n) : pImpl{std::make_unique<impl>(n)} {}
    widget::~widget() = default;
    widget& widget::operator=(widget&&) = default;

    // user (main.cpp)
    int main(){
        widget w(7);
        const widget w2(8);
        w.draw();
        w2.draw();
    }
    • 一个更直观的例子：
    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
    // Book.h
    #ifndef __BOOK_H__
    #define __BOOK_H__
    class Book
    {
        public:
            Book();
            ~Book();
            void print();

        private:
            class BookImpl;
            BookImpl* pimpl;
    };
    #endif

    //BookImpl.h
    #ifndef __BOOKIMPL_H__
    #define __BOOKIMPL_H__
    #include "Book.h"
    #include <iostream>
    #include <string>
    class Book::BookImpl
    {
        public:
            void print();
        private:
            std::string content_;
            std::string titil_;
    };
    #endif

    //Book.cpp
    #include "Book.h"
    #include "BookImpl.h"

    Book::Book()
    {
        pimpl = new BookImpl();
    }
    Book::~Book()
    {
        delete pimpl;
    }
    void Book::print()
    {
        pimpl->print();
    }
    void Book::BookImpl::print()
    {
        std::cout<<"print in imple"<<std::endl;
    }

    //main.cpp
    #include "Book.h"
    int main(){
        Book book;
        book.print();

        return 0;
    }

  1. 虚函数与纯虚函数

    • 虚函数
      • 允许基类指针来调用子类的这个函数 (virtual)
      • 多态的表现
    • 纯虚函数
      • virtual void funtion1()=0
      • 目的是规范所有派生类都要实现这个方法

  2. 拷贝如何作为虚函数

    • 在dynamic_cast被设计之前，C++无法实现从一个虚基类到派生类的强制转换。dynamic_cast就是为解决虚基类到派生类的转换而设计的。

  3. std::unique_ ptr:release()

    • 相当于std::move()，相当于给予当前控制权并清空自身

  4. std::enable_shared_from_this

    • ```cpp

      include

      include

      using namespace std;

      class A : public enable_shared_from_this
      {
      public:

      A()
{

}
void set()
{
    conn = this->shared_from_this();
}
int a;
weak_ptr<A> conn;

      };
      int main()
      {

      std::shared_ptr<A> ptr = std::make_shared<A>();
cout << ptr.use_count() << endl;  // 1
std::shared_ptr<A> ptr1 = ptr->conn.lock();

if (!ptr1)
{
    std::cout << "null\n";        // null
}

ptr->set();
cout << ptr.use_count() << endl;  // 1

ptr1 = ptr->conn.lock();

cout << ptr.use_count() << endl;  // 2

      }

      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

         - 用a.owner_before(b)来举例：如果a与b同为空或者同时指向同一个对象（包含继承关系），就返回false;如果是其它情况，则用指针所指向的对象的地址来比较大小，若a的地址<b的地址，则返回true，若a的地址>b的地址，则返回false。

      6. `dynamic_cast`

         - 从一个虚基类到派生类的强制转换。dynamic_cast就是为解决虚基类到派生类的转换而设计的。
         - `Artist *a1 =  dynamic_cast<Artist*>(p1);`其中p1的类型是Artist的派生类

      7. `std::dynamic_pointer_cast`

      8. 运算符重载

      9. 右值引用&&

         - 同`std::move()`

         - **将亡值**，是C++11为了引入右值引用而提出的概念(因此传统C++中，纯右值和右值是同一个概念)，**也就是即将被销毁、却能够被移动的值**

         - **要拿到一个将亡值，就需要用到右值引用：T&&，其中T是类型**。**右值引用的声明让这个临时值的生命周期得以延长，只要变量还活着，那么将网址将继续存活**

         - **{% asset_img 4.jpg This is an test image %}**

           ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210322132552567.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70)

      10. [`std::shared_ ptr<void>`和 `std::any`](https://www.cnblogs.com/gnivor/p/12793239.html)

          - `std::shared_ptr<void>`

            - 使用`shared_ptr<void>`代替`void*`可以解决声明周期管理的问题。(解决了`void*`需要手动进行内存管理的问题)
            - 但是std::shared_ptr和void*一样不能解决类型安全的问题。使用shared_ptr 需要reinterpreting integral 为void *并直接存储它们来避免内存分配；使用shared_ptr强制我们甚至为诸如int之类的微小对象分配内存。

          - `std::any`

            - 更智能的(`void*` / `shared_ptr<void>`)

            - ```cpp
              #include <iostream>
              #include <memory>
              #include <any>
              #include<vector>
              #include<assert.h>
              struct day {
                // ...things...
                std::shared_ptr<void> user_data;
              };
              
              struct month {
                std::vector<day> days;
                std::shared_ptr<void> user_data;
              };
              #define debug(x) std::cout<<#x<< " " << x<<std::endl
              int main()
              {
              	std::any a0; 
              	std::any a1 = 42; 
              	std::any a3 = a0; // Copies the empty any from the previous snippet
              	std::any a4 = a1; // Copies the "int"-containing any
              	assert(a4.type() == typeid(int));  // type() returns typeid(int) when empty
              	debug(0);
              	a4 = a0;          // copy assignment works, and properly destroys the old value
              	
              	assert(!a0.has_value());            // a0 is still empty
              	debug(1);
              	assert(a1.type() == typeid(int));
              	debug(2);
              	assert(a4.type() == typeid(void));  // type() returns typeid(void) when empty
              	debug(3);
              	assert(a3.type() == typeid(void));  // type() returns typeid(void) when empty
              	debug(4);
              	return 0;
              }

  1. POD

    • Plain old data structure
    • 类型是平凡的（trivial），则可以静态初始化、可以用memcpy直接复制数据而不是必须用copy构造函数。其生存期始于它的对象的存储被定义，无须等到构造函数完成。平凡class或结构必须满足：
      • 有平凡的缺省构造函数，可用这样的默认语法：(SomeConstructor() = default;)
      • 有平凡的copy与move构造函数，可用默认语法.
      • 有平凡的copy与move运算符，可用默认语法.
      • 有平凡的destructor，不能是虚函数.
    • 如果定义了构造函数，哪怕构造函数中什么也没有，即不是平凡的。

课件：https://github.com/parallel101/course

作业：https://github.com/parallel101/hw02

我的作业：https://github.com/WangYuHang-cmd/hw02

参考：https://blog.csdn.net/fengbingchun/article/details/52203825/

发表于 更新于 阅读次数： Changyan：

XCPC

​ 作为一名大二才接触算法竞赛，打了一年就退役的选手，我的XCPC生涯是如此短暂….

​ 由于一开始是大数据专业的，首先掌握的语言也是Python而不是C语言。因此在大一下学期我萌生了转专业的想法之后，我开始去自学C语言，看的是北大郭炜老师的课程：

程序设计与算法（一）C语言程序设计

程序设计与算法（二）算法基础

程序设计与算法（三）C++面向对象程序设计

同时,他配套的POJ(Peking University Online Judge)上面的习题我也带着写完了，同时我也上了郭炜老师的Python的相关课程。这也使得我从一位编程小白变成了一位会写简单分支循环语句的新生，同时也以优秀的等级通过了计算机二级考试。

然后就到了五月，我感觉这个写编程题还蛮有意思的，我就去洛谷上买了一本《深入浅出程序设计竞赛》平时带着写一写，恰好五月底我校正好举办了NUISTCPC(校程序设计竞赛)，我当时报着刚学完C语言和刷完深基搜索后的去试一试的心态，结果在迅速签完到之后三个小时罚坐后搞出来了一道贪心题，打了一个二十多的好成绩，这也让身为菜鸟的我感到惊奇。也正好在之后一次偶然的讲座中我听到了来自SYF学长关于ACM-ICPC的介绍后，产生了浓厚的兴趣。

在经历过一个多月的期末月，即2021.7.12考完最后一门后，我发现我已经把GPA刷到了足以使我成功转专业的分数，我尝试开始在网上找ACM-ICPC的入门路线。当然这过程中也走了很多弯弯绕绕的路，知道我在学习基础动态规划模型时在搜“背包九讲”时在Bilibili上面搜到了北大闫学灿老师的视频，我了解到了Acwing，并一口气报名了算法基础课和算法提高课。那个暑假我也留校开始学习。由于之前刷完过一本洛谷的《深基》,所以我很快就刷完了基础课(没记错的话好像是两周不到)，然后感觉蛮简单的，我就开始刷提高课了。

刷提高课的收获还是非常多的，各种之前并没有真正掌握的算法随着刷题的进行，开始逐渐熟悉了起来。大概是刷了一个半月我把提高可百分之九十的算法都掌握了。刷提高课的同时，我还进入了Acwing比较有名的提高二群，在里面认识了来自各个学校的Acmer,有：

现在在重邮的光头哥，Bsqaq，安徽工程的啾啾，武昌理工的银牌佬Duck_沙烬，新疆大学的临渊，来自哥大，打进WF的然然，齐鲁工业大学的L神，来自广西的OI爷爽gai，山东理工的那个队名巨长的队伍的ACMer凌乱之风，还有酸菜鱼佬，湖南理工长途，河南大学的程佬，深圳大学喵喵子，湖南科技黄宇轩，南昌理工的lqgg，lqmm，吉林大学的速RitszZ……

虽然大家刚进群都是菜菜的(除了个别佬)，但是经过了一年的训练也都拿到了牌子。

也是在暑假里我开始接触到了Atcoder和Codeforces这两个竞争性编程训练平台，加上之后接触到的出题偏构造和DP的Codechef，我主要的线上比赛网站就是这些。

我有一个非常不好的习惯，那就是喜欢开小号。一旦感觉自己状态有点不太对(比如有点困)，我就会去打小号，但事实证明这样子并不好，不仅严重拖慢了上分速度(以至于我现在只有紫名)，也会拖慢比赛适应能力。

我的所有CF号

总之，对于掌握了知识点后如何快速得提升自己的代码运用水平并提升自己得思维能力，多多刷Atcoder和Codeforces是一个非常高效得做法。

在大一升大二暑假之后，我发现常常自己CF只能做到C题，D难出。学的算法也并不足够满足所有的XCPC知识，于是九月份我接触到了牛客算法平台以及牛客的课程。因此大二上学期，还没有进队，没有比赛打的我的主要任务就是刷完牛客竞赛的课程和配套习题。这一段时间对于我处理常见模型，常规算法题的能力提升是最明显的，也多亏了雨巨的清晰的讲述，对于小白来说非常的友好。在这之后我就基本告别Acwing这个入门级平台，开始使用牛客这个更加专业的竞赛平台了。刷题量也随着陡增，大概是两个月600+的题目。主要集中在中档题。MyNowcoder.在处理完这些常见算法模型之后我的CF到了蓝名1700左右的水平，能保证我在30~50分钟内快速出完CF的ABC题，偶尔能写出来CF的D题。紧接着就是寒假的CF训练，那段时间我也找到了我的队友WZY和GRD，寒假结束之后我们也开始逐渐合练区域赛。此时的我CF大概是1700-1800左右徘徊。反思了一下应该是我学习不够深入导致的。因为比别人晚一年接触XCPC，所以相应的知识点的学习我给自己设置的时间要短很多，这样才能保证快速覆盖一定量的面，但是深度还是不够的。因此大二下学期，在尽量满足课内需求的同时我还需要加深各个算法的应用——VP区域赛就是一个很好的方法，同时我也开始Virtual Participate CF之前的场次。终于到了快要放暑假的啥时候我的CF成功到达了紫名。紧接着就是更多紫名的小号了…（非常不建议开小号）

大二下学期我也开始有比赛打了。一个是昆明区域赛，这个在我之前的博客中有提到，也是之前多出来的名额，但是我打的并不好，最后我们队的模拟题没写出来也导致铁首。这让我感觉到之后的重重困难。紧接着就是JSCPC(CCPC 江苏省省赛)。江苏省省赛是我认为的全中国各个赛区难度相对最大的省赛了.还好上一场打铁并没有怎么影响我们，省赛打了一个银首，差一点金，也结束了这个赛季。

紧接着就是期末月后的多校联赛。多校我们打的一般般，排名也在200左右。大致是保铜争银的定位。我暑假出现的一个失误点在于我去学习了一些字符串进阶算法和计算几何算法，但是实际上这些知识点对我们队伍来说用处并不大。不过就当作知识点学习了。

2022-2023新赛季的时间特别短暂，我们队伍一共有三场比赛任务，队长特地选在了比较靠前，三周连续的，以便我们能够快速打完后准备期末。所以11.26号我就打完了所有比赛，比赛后的小作文我一律没写，因为大部分比赛都是差强人意，仅仅比预估的最坏结果要好一点。由于CCPC广州的卡题，到了三个小时我才把博弈论给想出来，因为我们又铁了。不过此时倒也没有什么心理压力了，因此紧接着下一周的ICPC合肥站我们还是比较轻松的，最终由于J题奇幻的错误勘误卡了我们半个多小时，最后没有调出来J，导致我们距离银牌线只有几名，遗憾拿铜。ICPC济南站也是同样的，做出来五题，但是因为罚时不占优势，在铜首区拿了一块铜牌。

我觉得如果我大一就接触ACM的话应该通过两年的时间拿到银牌不成问题。但是也最后两场比赛没有抓住机会+运气不好只拿到了铜牌。不过也算是我曾经参加算法竞赛的凭证了吧！

发表于 阅读次数： Changyan：

实验二 哈希表的设计

哈希表简介：

实验内容：

1.编写属于2-通用簇的某个哈希函数代码（30 分）

•输入：键值

•输出：哈希值

2.给定一个较大的m值，例如10^9，和一个较小的n值，例如1000，通过实验观察多次插入操作后链表的平均长度（键值随机采样），并与理论结果进行对比分析（40 分）

3.对于（2）的结果，使用 2-通用哈希函数簇中不同的哈希函数，观察并分析结果的差异（30 分）

第一问：

一下是我编写的两个哈希函数：

1
2
3
4
long long get_hash1(long long x){
    assert(mod>0);
    return ((((long long)x<<1)%mod*(long long)x%mod)+x)%mod;  
}
1
2
3
4
long long get_hash2(long long x){
    assert(mod>0);
    return x%mod;
}
第二问：

经过实验发现在m较大，n较小的情况下，平均长度趋于1.0，与理论结果相近

在m，n较为接近的情况下，平均长度因哈希函数而异。

第三问：

如图是哈希函数1的实验结果：

如图是哈希函数2的实验结果：

经过对比可以发现不论是大模数小数据抑或是大模数大数据哈希函数2的表现要优于哈希函数1.

Code

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
75
76
77
78
79
80
81
82
83
84
85
#include<unordered_set>
#include<unordered_map>
#include<functional>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<iterator>
#include<cstring>
#include<numeric> 
#include<assert.h>
#include<random>
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
// using namespace std;
// using long long = long long;
const long long N = 200010;
std::mt19937 rnd(time(0));
namespace MyHash{
    long long mod,idx,hash_number;
    struct Node{
        Node(long long _key,long long _val,long long _next):key(_key),val(_val),next(_next){};
        long long key,val,next;
    };
    std::vector<Node> node; 
    std::vector<long long> head;
    void init(long long _mod){
        assert(_mod!=0);
        hash_number=idx=0,mod=_mod;
        node.clear();
        head.resize(mod, -1);
    }
    long long get_hash1(long long x){
        assert(mod>0);
        return ((((long long)x<<1)%mod*(long long)x%mod)+x)%mod;  
    }
    long long get_hash2(long long x){
        assert(mod>0);
        return x%mod;
    }
    long long get_node(long long key,long long val){
        Node now=Node(key,val,-1);
        node.push_back(now);
        return idx++;
    }
    void insert(long long key, long long val){
        long long _hash = get_hash1(key);
        // long long _hash = get_hash2(key);
        long long now = get_node(key, val);
        if(head[_hash] == -1) hash_number ++;
        node[now].next = head[_hash];
        head[_hash]=now;
    }
    double average_len(){
        if(!hash_number) return 0;
        assert(hash_number);
        return (double)idx/hash_number;
    }
}


void solve(){
    long long n,m;
    std::cout << "请输入n(哈希实验个数) m(模数):" << std::endl;;
    std::cin >> n >> m;
    MyHash::init(m);
    for(long long i=1;i<=n;++i){
        auto key = rnd(),val = rnd();
        MyHash::insert(key, val);
    }
    auto ans = MyHash::average_len();
    if(ans<1e-9) std :: cout << "哈希表为空" << std :: endl;
    else std::cout << ans << std::endl;
}

signed main(){
    solve();
    return 0;
}

发表于 分类于 阅读次数： Changyan：

珂朵莉树ODT

可以较快地实现：

  • 区间加
  • 区间赋值
  • 求区间第k大值
  • 求区间n次方和

珂朵莉树的思想在于随机数据下的区间赋值操作很可能让大量元素变为同一个数。所以我们以三元组的形式保存数据（区间 [l,r] 中的元素的值都是v）

存储形式：

1
2
3
4
5
6
7
struct Node{
	int l,r;
    mutable int c;
    node(int l,int r,int v):l(l),r(r),v(v){};
    bool operator<(const Node& W)const{return l<W.l;}
};
set<Node> ds;

1.split操作，区间分裂

1
2
3
4
5
6
7
8
9
10
11
//断开”的操作，把<l,r,v>断成<l,pos-1,v>和<pos,r,v>：
set<Node>::iterator split(int pos){
    auto now=ds.lower_bound(Node(pos,0,0));// 寻找左端点大于等于pos的第一个节点
    if(now!=ds.end()&&now->l == pos)
        return now;
   	now --; //往前数一个节点
    int l=now->l,r=now->r,v=now->v;
    ds.erase(now);
    ds.insert(Node(l, pos-1, v));
    return ds.insert(Node(pos,r,v)).x; //nsert默认返回值是一个pair，第一个成员是以pos开头的那个节点的迭代器
}

2.assign操作，区间赋值

1
2
3
4
5
void assign(LL l,LL r,LL v){ //将[l,r]赋值为v
    auto end=split(r+1),begin=split(l);
	ds.erase(begin, end);
    ds.insert(Node(l,r,v));
}

例题：https://codeforces.com/problemset/problem/915/E

从现在到学期结束还有 n 天(从 1 到 n 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 q 个指令，每个指令可以用三个参数 l,r,k 描述：
如果 k=1 ，那么从 l 到 r （包含端点）的所有日子都变成非工作日。
如果 k=2 ，那么从 l 到 r （包含端点）的所有日子都变成工作日。

将assign()修改一下，暴力统计即可

1
2
3
4
5
6
7
8
9
10
11
void assign(int l,int r,int v){
	int tot = 0;
	auto end=split(r+1),begin=split(l),now=begin;
	for(;now!=end;now++){
		tot += (now->v)*(now->r-now->l+1);
	}
	ds.erase(begin, end);
    ds.insert(Node(l,r,v));
	sum -= tot;
	sum += (r - l + 1) * v;
}

3.add()区间加

直接暴力加法即可

1
2
3
4
5
void add(int l,int r,int v){
    auto begin=split(l),end=split(r+1);
    for(;begin!=end;begin++)
        begin->v += v;
}

4.rank()区间第k小

1
2
3
4
5
6
7
8
9
10
11
12
int rank(int l,int r,int k){
    vector<pair<int,int>> tmp;
    auto begin=split(l),end=split(r+1);
    for(;begin!=end;begin++)
        tmp.push_back({begin->v, begin->r-begin->l+1});
	sort(tmp.begin(), tmp.end());
    for(auto u:tmp){
        k -= u.y;
        if(k<=0) return u.x;
    }
    return -1; 
}

5.sum_of_pow()区间n次方的和

1
2
3
4
5
6
7
8
int sum_of_pow(int l,int r,int x,int y){
	int tot=0;
	auto begin=split(l),end=split(r+1);
	for(;begin!=end;begin++){
		tot = (tot + fpower(begin->v, x, y) * (begin->r-begin->l+1) % y)%y;
	}
	return tot;
}

ODT经典题：https://codeforces.com/problemset/problem/896/C

  • 区间加
  • 区间赋值
  • 求区间第k大值
  • 求区间n次方和
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#define int LL
const int N=200010,M=N*2,mod=1e9+7;
struct Node{
	int l,r;
	mutable int v;
	Node(int _l,int _r,int _v):l(_l),r(_r),v(_v){};
	bool operator<(const Node &W)const{return l<W.l;}
};
set<Node> ds;
int n,m,seed,vmx;
int sum=n;

set<Node>::iterator split(int pos){
	auto now=ds.lower_bound(Node(pos,0,0));
	if(now!=ds.end() && now->l == pos)
		return now;
	now --;
	int l=now->l,r=now->r,v=now->v;;
	ds.erase(now);
	ds.insert(Node(l,pos-1,v));
	return ds.insert(Node(pos, r, v)).x;
}

void assign(int l,int r,int v){
	int tot = 0;
	auto end=split(r+1),begin=split(l);
	ds.erase(begin, end);
    ds.insert(Node(l,r,v));
}

void add(int l,int r,int v){
    auto begin=split(l),end=split(r+1);
    for(;begin!=end;begin++)
        begin->v += v;
}

int kth(int l,int r,int k){
    vector<pair<int,int>> tmp;
    auto begin=split(l),end=split(r+1);
    for(;begin!=end;begin++)
        tmp.push_back({begin->v, begin->r-begin->l+1});
	sort(tmp.begin(), tmp.end());
    for(auto u:tmp){
        k -= u.y;
        if(k<=0) return u.x;
    }
    return -1; 
}

int sum_of_pow(int l,int r,int x,int y){
	int tot=0;
	auto begin=split(l),end=split(r+1);
	for(;begin!=end;begin++){
		tot = (tot + fpower(begin->v, x, y) * (begin->r-begin->l+1) % y)%y;
	}
	return tot;
}
LL rnd()
{
    LL ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}
void solve(){
	n=read(),m=read(),seed=read(),vmx=read();
	rep(i,1,n){
		int r=rnd();
		ds.insert(Node(i, i, r%vmx+1));
	} 
	while(m--){
		//input
		LL ty=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1,x,y;
		if(l>r) swap(l,r);
		if(ty==3) x=rnd()%(r-l+1)+1;
		else x=rnd()%vmx+1;
		if(ty==4) y=rnd()%vmx+1;

		if(ty==1){
			add(l,r,x);
		}
		else if(ty==2){
			assign(l,r,x);
		}
		else if(ty==3){
			print(kth(l, r, x));
		}
		else{
			print(sum_of_pow(l ,r, x, y));
		}
	}
}

发表于 分类于 阅读次数： Changyan：

积性函数

定义：

如果函数$f:N \to R$满足于任意一对互质的正整数p,q.都有$f(pq)=f(p)f(q)$则称f为积性函数

命题：

如果$f(n)$坏人$g(n)$为积性函数，则$h(n)=f(n)g(n)$也为积性函数

设f为积性函数，假设$n=p_1^{q_1}…p_k^{q_k}$,$f(n)=f(p_1^{q_1})…f(p_k^{q_k})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
f[1] = 1;
for (int i = 2; i <= n; i++) {
	if (!not prime[i]) p[++tot] = i, cnt[i] = 1, f[i] = calc_f(i, 1);
	for (int j = 1; j <= tot && i * p[j] <= n; j++) {
		not prime[i * p[j]] = 1;
        if (i % p[j] == 0) {
        cnt[i * p[j]] = cnt[i] + 1;
        f[i * p[j]] = f[i]/calc_f(p[j], cnt[i])*calc_f(p[j], cnt[i]+1);
        break;
        }
        cnt[i * p[j]] = 1
        f[i * p[j]] = f[i] * calc_f(p[j], 1);
	} 
}

线性筛求n个数的正因子个数

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
const int N=10000010,M=N*2,mod=1e9+7;
int n,m,k;
LL Cnt[N],d[N];
bool numlist[N];
int prime[N],cnt;
void Eular(int n=10000000){
    Cnt[1]=1;
    for(int i=2;i<=n;i++){
        if(!numlist[i]){
            prime[++cnt]=i;
            Cnt[i]=2;
            d[i]=1;
        }
        for(int j=1;prime[j]<=n/i;j++){
            numlist[i*prime[j]] =true;
            if(i%prime[j]==0){
                Cnt[i*prime[j]]=Cnt[i]/(d[i]+1)*(d[i]+2);
                d[i*prime[j]]=d[i]+1;
                break;
            }
            d[i*prime[j]]=1;
            Cnt[i*prime[j]]=Cnt[i]*Cnt[prime[j]];
        }
    }
    return ;
}

例题

E. Bash Plays with Functions

很容易观察出$f(x)$是积性函数，因此我们先预处理出所有的$f_r(1-20)$因为1e6以内分解质因数后最多的质数的指数为20.然后logn内分解并可以乘得答案。

莫比乌斯反演

作用：

已知$g(n)$的因数和$f(n)=\sum_{d|n}g(d)$,通过f反求g

实际上只要记住如果能够推到成如$f(n)=\sum_{d|n}g(d)$形式后都能通过反演得到:

其中$\mu()$为莫比乌斯函数。

例子 环计数问题

假设 n 个元组成一个环，每个元都是 1, 2, …,**r 中的一个数，两个环是不同的环当且仅当它们不能通过旋转使得两个环中对应的每个元素都相等。求有多少个这样的环。

首先我们构造一个无限长的序列，假设此序列的周期为d，其中d为n的因子。有$r^n=\sum_{d|n}d*f(d)$,因此由反演得$f(n)=\frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})r^d$

反演2

设$f:N \to R$，$g:N \to R$ 是两个函数，且存在正整数N，对于所有n>N, f(n)=g(n)=0,则:

$f(n)=\sum_{n|m}g(m)$等价于$g(n)=\sum_{n|m}\mu (\frac{m}{n} )f(m)$当$m \le N$

例题

两个长度为 n 的序列 a, b，求满足 $gcd(x, y) = 1$ 且有$a_{b_x} = b_{a_y}$的对 (x, y) 的数量。$(1 ≤ n ≤ 10^5, 1 ≤ a_i, b_i ≤ n)$

令$f(d)=\sum_{1\le x,y \le n}[a_{b_x}=b_{a_y}][gcd(x,y)=d]$ , $g(d)=\sum_{d|x,d|y}[a_{b_x}=b_{a_y}]$

由反演2得:$f(d)=\sum_{d|d’}g(d’)\mu (\frac{d’}{d})$，因此答案为$f(1)=\sum_{d=1}^ng(d)\mu (d)$

其中g(d)是可以轻松算出来的，总时间复杂度为$O(nlogn)$

迪利克雷卷积

定理：

设$f:N \to R$,$g: N\to R$是两个函数，则它们的迪利克雷卷积为$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

通过迪利克雷卷积可以将莫比乌斯反演写成：

$f=g1$ <==> $g = f\mu$

一些公式

$\frac{\phi(n)}{n}=\sum_{d|n}\mu(d)\frac{n}{d}$

应用：快速求$M(n)=\sum_{i=1}^{n}\mu(i)$，其中$n \le 10^{11}$ (杜教筛)

$M(n)=1-\sum_{i=2}^{n}M(\lfloor \frac{n}{i} \rfloor)$,使用整除分块

广义莫比乌斯反演

设$(X, \le)$是下有限的偏序集，$f,g:X \to R$则$f(x)=\sum_{y \le x}g(y)$等价于$g(x)=\sum_{y \le x}\mu(y,x)f(y)$

其中$\mu(x.y)$满足

发表于 分类于 阅读次数： Changyan：

Codecherf START51 Div4 Chef & Cook Game

Problem

There is a non-negative integer array AA of length NN. Chef and Cook will play a game on the array with Chef starting first.

In one turn the player will perform the following operation:

  • Choose two indices i,j such that $1 \le i \lt j \le N$ and $A_i \gt 0$.
  • Set $A_i \gets A_i-1$ and $A_j \gets A_j+1$,subtract 1 from $A_i$ and add 1 to $A_j$

The player who is unable to perform the operation loses. If both Chef and Cook play optimally, who will win?

解法：

首先，对于a[i]是偶数的位置，我们很容易想出来对照操作:只要你选了这个位置，我也选，因此对于偶数的位置我们不需要考虑。因此单独考虑a[i]为奇数的位置，我们可以将其转化为Nim游戏，对于i位置，可以移动到大于i的任意位置，因此可以看作可以取1~N-i个石子,所以我们把奇数位置的所有N-i异或起来，如果异或和不为0，则为先手必胜，否则先手必败。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
	cin>>n;
	rep(i,1,n) cin>>a[i];
	if(n==1){
		cout << "Cook\n";
		return ;
	}
	LL sum=0;
	rep(i,1,n){
		if(a[i]&1) sum^=(n-i);
	}
	cout << (sum?"Chef":"Cook") << "\n";
}

发表于 分类于 阅读次数： Changyan：

维护序列:插入首部问题

经常能做到一些数据结构维护的，将一个序列中的某个位置的东西插入首部的问题。有些只需要简单用set或者其他基本的数据结构维护一下信息就行了，但是有些需要经过一些变化，一般需要树状数组或者线段树在变换后的基础上进行维护。

例如：

E. Messenger Simulator

大意就是一个n排列，m次操作把排列中的某个数字放到开头，你要维护每一个数字在序列中出现过的最左端和最右端。

方法：

预先留出n+m个空，n排列初始化到n+m最后n个位置。然后用BIT维护每个位置上是否有东西。每次更新的时候只需要修改左端点并查询当前位置前面有数的个数和右端点取max即可。

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
const int N=600010,M=N*2,mod=1e9+7;
int n,m,k,a[N],l[N],r[N],pos[N];
struct BIT{
	#define lowbit(x) ((x)&(-x))
	int tr[N],n;
	void resize(int _n){n=_n;}
	inline void add(int x,int d){for(;x<=n;x+=lowbit(x)) tr[x]+=d;}
	inline int ask(int x){int ans=0;for(;x;x-=lowbit(x)) ans+=tr[x];return ans;}
}T;

void solve(){
	n=read(),m=read();
	rep(i,1,n) l[i]=r[i]=i,pos[i]=m+i;
	T.resize(n+m+2);
	rep(i,1,n) T.add(i+m,1);
	for(int i=m;i>=1;--i){
		int x=read();
		l[x]=1;
		int pl=pos[x];
		int num=T.ask(pl);
		r[x]=max(r[x], num);
		T.add(pl,-1);
		pos[x]=i;
		T.add(i, 1);
	}
	for(int i=1;i<=n;++i){
		int pl=pos[i];
		int num=T.ask(pl);
		r[i]=max(r[i], num);
	}
	rep(i,1,n) printf("%d %d\n",l[i],r[i]);
}

发表于 分类于 阅读次数： Changyan：

杭电多校第一场

A.string

We define F_G as the number of positive integers x that satisfy the following conditions:

$1≤x≤G$

$G[1,x]=G[Glen−x+1,Glen]$

The length of the common part of the intervals $[1,x]$and $[G_{len}-x+1,G_{len}]$is greater than 0 and is divisible by k.

做法：

首先我们用exkmp处理出z[i]数组，表示[1,n]和[i,n]的LCP，然后如果这个LCP的长度满足大于等于i的时候,就会对[1, n*(i-1)+k]….会产生贡献.因此做一个前缀和就行了

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
const int N=1000010,M=N*2,mod=998244353;
int n,m,k,a[N],z[N];
char s[N];

void exkmp(){
	for(int i=2,l=0,r=0; i<=n;++i){
		if(i<l+z[l]) z[i]=min(z[i-l+1],l+z[l]-i);
		while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]])z[i]++;
		if(i+z[i]>l+z[l])l=i;
	}
	z[1]=n;
}

void solve(){
	scanf("%s",s+1);
	n=strlen(s+1);
	k=read();
	exkmp();
	for(int i=0;i<n;++i){
		int len=z[i+1];
		if(len>=i+k){
			len = ((len-i)/k)*k;;
			a[2*i+k] ++;
			if(2*i+len+k<=n) a[2*i+len+k] --;
		}
	}
	LL ans=1;
	for(int i=1;i<=n;++i){
		if(i+k<=n)a[i+k]+=a[i]; 
		ans=ans*(a[i]+1)%mod;
	}
	rep(i,0,n) z[i]=a[i]=0;
	print(ans);
}