C++ const & static
const
const编译时特性
const变量
- 根据是否可以在编译期间确定,可以分为编译时常量和运行时常量
const int a = 10; // 编译时常量
const int a = function(); // 运行时常量,无法在编译时使用该变量
const与指针
- 指向常量的指针
const int * a
或int const * a
:指向可以变化,但只能指向const对象
- 指针常量
int * const a
:指向不能变化,指向的对象可以变化
- 编译期间确定or运行时确定根据是否可以从编译期间确定常量值决定
const与函数
- 函数在编译时确定函数签名(包括返回类型、参数类型和数量),运行时确定函数的行为(即它如何操作传入的参数以及它返回什么)
const int& func(int& a)
int& func(const int& a)
int& func(int& a) const{}
:const成员函数- 不允许修改类的成员的值,但可以修改a的值
const与类
const修饰类成员变量
- 在对象的声明周期内是常量,对整个类而言是可以改变的。
- 不能在类内初始化const成员变量,在初始化列表中初始化。
const类对象成员函数
- 不允许修改类的成员的值
const对象
- 只能调用const函数
const -> #define
不同
- 类型
- 宏定义是字符替换,没有数据类型的区别
- const常量是常量的声明,有类型区别
- 安全检查
- 可能产生边际效应等错误
- 在编译阶段进行类型检查
- 编译器处理
- 宏定义是一个”编译时”概念
- const常量是一个”运行时”概念
- 存储方式
- 宏定义:代码段
- const常量:data区
- 是否可以做函数参数
- 可以在函数的参数列表中出现
static
static与局部变量
特点
- 存储位置data区
- 生命周期保持不变
- 局部作用域退出时,数据仍然暂存data区
static与全局变量
特点
- 加入static后,源程序的其他源文件不能再使用该变量(不使用static可以用extern扩展)
static与函数
特点
- 跟全局变量相同,限制作用域,只能在该文件中使用(与全局变量用法也相同)
static与类对象成员变量
特点
- 变量会变成类的全局变量,只能在类外初始化
- 但如果加入const修饰,则可以在类内初始化
static与类对象成员函数
特点
- 类只存在一份函数,所有对象共享,不含this指针,无需创建实例即可访问
- 不可同时用const和static修饰对象的成员函数
static与const总结
static的作用是表示该函数只作用在类型的静态变量上,与类的实例没有关系
const的作用是确保函数不能修改类的实例的状态 static和const不可同时修饰成员函数
C++ 预编译关键字
C++ 预编译
本部分主要介绍两部分:C++文件预编译处理策略与常用预编译命令。在C++预编译文件处理策略中,将介绍文件处理的策略和对C++预编译的循环依赖产生问题的解决方案。在常用预编译命令中,将介绍常用的预编译命令。
C++ philosophy
C++ philosophy
1. express ideas directly in code
- 如果能使用const,则使用const保证代码健壮性。【use const consistently, check if member functions modify their object; check if functions modify arguments passed by pointer or reference】
#include <iostream>
class MyClass {
private:
int value;
public:
// Constructor
MyClass(int val) : value(val) {}
// Getter function, does not modify the object, should be marked as const
int getValue() const {
return value;
}
// Setter function, modifies the object
void setValue(int newVal) {
value = newVal;
}
// Function that does not modify the object, should be marked as const
void printValue() const {
std::cout << "Value: " << value << std::endl;
}
// Function that modifies the object
void incrementValue() {
value++;
}
};
// Function that takes a pointer to MyClass and modifies it
void modifyObject(MyClass* obj) {
obj->setValue(42);
}
int main() {
const MyClass obj1(10); // obj1 is const, can only call const member functions
obj1.printValue(); // OK
// obj1.setValue(20); // Error: cannot modify const object
MyClass obj2(30);
obj2.printValue(); // OK
obj2.incrementValue();
obj2.printValue(); // Value: 31
modifyObject(&obj2);
obj2.printValue(); // Value: 42
return 0;
}
- 返回类型应保证可懂。【flag uses of casts, casts neuter the type system】
class Date {
public:
Month month() const; // do
int month(); // don't
// ...
};
- 建议使用标准lib库。【detect code that mimics the standard lib】
// bad code example
void f(vector<string>& v)
{
string val;
cin >> val;
// ...
int index = -1; // bad, plus should use gsl::index
for (int i = 0; i < v.size(); ++i) {
if (v[i] == val) {
index = i;
break;
}
}
// ...
}
// good code example
void f(vector<string>& v)
{
string val;
cin >> val;
// ...
auto p = find(begin(v), end(v), val); // better
// ...
}
- 有量纲的使用变化量。【for number change, use delta type rather then double or int】
// bad code example
change_speed(double s);// bad: what does s signify?
// ...
change_speed(2.3);
// good code example
change_speed(Speed s);// better: the meaning of s is specified
// ...
change_speed(2.3);// error: no unit
change_speed(23_m/ 10s);// meters per second
2. Say what should be done, rather than just how it should be done.
- 建议使用范围for循环。【simple for loops vs. range-for loops】
// bad code example
gsl::index i= 0;
while (i< v.size()) {
// ... do something with v[i] ...
}
// good code example
for (constauto& x : v) {/* do something with the value of x */ }
// good code example
for (auto& x : v) {/* modify x */ }
// good code example
for_each(v, [](int x) {/* do something with the value of x */ });
for_each(par, v, [](int x) {/* do something with the value of x */ });
- 建议封装指针。【f(T*, int) interfaces vs. **f(span
)** interfaces】
// bad code example
template<typename T>void f(T* ptr,int size) {
for (int i= 0; i< size;++i) {
std::cout<< ptr[i]<< " ";
}
std::cout<< std::endl;
}
// good code example
template<typename T>void f(std::span<T> arr) {
for (constauto& element : arr) {
std::cout<< element<< " ";
}
std::cout<< std::endl;
}
- 变量有效空间问题。【loop variables in too large a scope(avoid)】
#include <iostream>
int main() {
// Example 1: Loop variable i has too large a scope
int sum1 = 0;
for (int i = 1; i <= 5; ++i) {
sum1 += i;
}
std::cout << "Sum1: " << sum1 << std::endl;
// Later in the code, you might accidentally reuse the same loop variable name
// This could lead to confusion or unintended behavior
for (int i = 6; i <= 10; ++i) {
sum1 += i;
}
std::cout << "Sum1 after reusing i: " << sum1 << std::endl;
// Example 2: Properly scoping the loop variable
int sum2 = 0;
for (int j = 1; j <= 5; ++j) {
sum2 += j;
}
std::cout << "Sum2: " << sum2 << std::endl;
// This would result in a compilation error since j is not visible here
// j += 1; // Error: 'j' was not declared in this scope
return 0;
}
- 建议不使用原生内存管理方法。【naked new and delete(avoid)】
#include <iostream>
class MyClass {
public:
MyClass() {
std::cout << "MyClass Constructor" << std::endl;
}
~MyClass() {
std::cout << "MyClass Destructor" << std::endl;
}
void doSomething() {
std::cout << "Doing something..." << std::endl;
}
};
int main() {
// Example with naked new and delete (avoid)
MyClass* obj1 = new MyClass();
obj1->doSomething();
// Missing delete can lead to memory leak
// delete obj1;
// Improved version using std::unique_ptr
std::unique_ptr<MyClass> obj2 = std::make_unique<MyClass>();
obj2->doSomething(); // No need for explicit delete
// obj2 will be automatically deleted when it goes out of scope
return 0;
}
- 建议不使用太多参数构造,使用多个函数。【functions with many parameters of built-in types(avoid)】
#include <iostream>
// Function with many parameters of built-in types (avoid)
void processUserData(std::string name, int age, double height, bool isStudent) {
// Function body - processing user data
std::cout << "Name: " << name << ", Age: " << age
<< ", Height: " << height << ", Is Student: " << isStudent << std::endl;
// Additional processing...
}
// Improved version using a structure to encapsulate parameters
struct UserData {
std::string name;
int age;
double height;
bool isStudent;
};
void processUserDataImproved(const UserData& userData) {
// Function body - processing user data
std::cout << "Name: " << userData.name << ", Age: " << userData.age
<< ", Height: " << userData.height << ", Is Student: " << userData.isStudent << std::endl;
// Additional processing...
}
int main() {
// Example of using the original function
processUserData("John Doe", 25, 1.75, true);
// Example of using the improved function with a structure
UserData user1 = {"Jane Smith", 30, 1.68, false};
processUserDataImproved(user1);
return 0;
}
3. a program would be completely compile-time type safe
- unions vs. variant
union MyUnion {
int intValue;
float floatValue;
};
int main() {
union MyUnion myUnion;
myUnion.intValue = 42;
// 以下代码尝试以浮点数的方式读取整数值,这可能导致不确定的行为
float result = myUnion.floatValue;
printf("%f\n", result);
return 0;
}
using MyVariant = std::variant<int, double, std::string>;
int main() {
// 创建一个包含 int 类型的 variant
MyVariant myVar = 42;
// 使用 std::get 来获取 variant 中的值
if (std::holds_alternative<int>(myVar)) {
std::cout << "The variant contains an int: " << std::get<int>(myVar) << std::endl;
} else if (std::holds_alternative<double>(myVar)) {
std::cout << "The variant contains a double: " << std::get<double>(myVar) << std::endl;
} else if (std::holds_alternative<std::string>(myVar)) {
std::cout << "The variant contains a string: " << std::get<std::string>(myVar) << std::endl;
}
// 修改 variant 中的值
myVar = 3.14;
// 再次使用 std::get 获取新的值
if (std::holds_alternative<double>(myVar)) {
std::cout << "The variant now contains a double: " << std::get<double>(myVar) << std::endl;
}
return 0;
}
- 建议使用template替代casts。【casts(avoid or minimize using) vs. template】
#include <iostream>
void processInteger(int value) {
// Attempting to cast to double
double doubleValue = static_cast<double>(value);
std::cout << "Processed Integer as Double: " << doubleValue << std::endl;
}
int main() {
int integerValue = 42;
processInteger(integerValue);
return 0;
}
template <typename T>
void processValue(const T& value) {
// Processing the value without explicit cast
std::cout << "Processed Value: " << value << std::endl;
}
int main() {
int integerValue = 42;
double doubleValue = 3.14;
processValue(integerValue);
processValue(doubleValue);
return 0;
}
- 建议使用span用以解决数组遍历等问题。【array decay vs. span】
int main() {
int arr[5] = {1, 2, 3, 4, 5};
// 在函数调用中,数组名 arr 发生衰减,被解释为指向数组第一个元素的指针
printArray(arr, 5);
return 0;
}
void printArray(int *ptr, int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", ptr[i]);
}
printf("\n");
}
void printSpan(std::span<int> arr) {
for (int value : arr) {
std::cout << value << " ";
}
std::cout << std::endl;
}
int main() {
int arr[5] = {1, 2, 3, 4, 5};
// 使用 std::span 避免数组衰减
printSpan(arr);
return 0;
}
- 建议使用span用以解决数组范围问题【range errors vs. span】
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Attempting to access an element out of range
int value = numbers[10]; // This can lead to undefined behavior
std::cout << "Value: " << value << std::endl; // Undefined behavior, may crash
return 0;
}
#include <iostream>
#include <span>
int main() {
int numbers[] = {1, 2, 3, 4, 5};
// Using std::span to represent a view of the array
std::span<int> numbersSpan(numbers);
// Accessing elements without risk of range error
for (int value : numbersSpan) {
std::cout << "Value: " << value << std::endl;
}
return 0;
}
- 在要求精度较高的场景,使用narrow_cast在精度降低时,可以抛出异常【narrowing conversions(avoid or minimize using) vs. narrow or narrow_cast(GSL)】
double largeValue = 123456789.123;
int intValue = largeValue; // 缩窄转换,可能导致精度损失或溢出
int main() {
int intValue = 42;
short shortValue = gsl::narrow_cast<short>(intValue);
std::cout << "Original value: " << intValue << std::endl;
std::cout << "Narrowed value: " << shortValue << std::endl;
return 0;
}
4. Don’t postpone to run time what can be done well at compile time
- 使用span解决遍历索引等问题【look for pointer arguments span】
#include <iostream>
#include <cstddef> // For std::ptrdiff_t
// Function using pointer and size for array processing
void processArray(const int* ptr, std::size_t size) {
for (std::size_t i = 0; i < size; ++i) {
std::cout << "Value: " << ptr[i] << std::endl;
}
}
int main() {
int numbers[] = {1, 2, 3, 4, 5};
// Using pointer and size to represent a view of the array
const int* ptr = numbers;
std::size_t size = sizeof(numbers) / sizeof(numbers[0]);
// Calling the function with pointer and size
processArray(ptr, size);
return 0;
}
#include <iostream>
#include <span>
// Function using std::span for array processing
void processArray(std::span<const int> numbers) {
for (int value : numbers) {
std::cout << "Value: " << value << std::endl;
}
}
int main() {
int numbers[] = {1, 2, 3, 4, 5};
// Using std::span to represent a view of the array
std::span<const int> numbersSpan(numbers);
// Calling the function with std::span
processArray(numbersSpan);
return 0;
}
- look for run-time checks for range violations
- 检查程序中是否有对数组范围进行检查的代码
- 静态分析工具检查程序是否有潜在的范围越界
- 软件测试中,尝试故意超过范围的值,看程序是否会正确处理
5. 一些无法在编译器确定的错误需要在运行时能够检测错误
should endeavor to write programs that in principle can be checked, given sufficient resources(analysis programs, run-time checks, machine resources, time)
- compile & run-time checkable with ownership and /or imformation
存在无法通过静态与动态检测其中的内存指针分配
// separately compiled, possibly dynamically loaded
extern void f(int* p);
void g(int n)
{
// bad: the number of elements is not passed to f()
f(new int[n]);
}
大小传递不符合参数规范
// separately compiled, possibly dynamically loaded
extern void f2(int* p, int n);
void g2(int n)
{
f2(new int[n], m); // bad: a wrong number of elements can be passed to f()
}
C++ lib的资源管理无法传递空间大小
// separately compiled, possibly dynamically loaded
// NB: this assumes the calling code is ABI-compatible, using a
// compatible C++ compiler and the same stdlib implementation
extern void f3(unique_ptr<int[]>, int n);
void g3(int n)
{
f3(make_unique<int[]>(n), m); // bad: pass ownership and size separately
}
传递指针和大小作为整体进行传递
extern void f4(vector<int>&); // separately compiled, possibly dynamically loaded
extern void f4(span<int>); // separately compiled, possibly dynamically loaded
// NB: this assumes the calling code is ABI-compatible, using a
// compatible C++ compiler and the same stdlib implementation
void g3(int n)
{
vector<int> v(n);
f4(v); // pass a reference, retain ownership
f4(span<int>{v}); // pass a view, retain ownership
}
将所有权和所有信息进行传递
vector<int> f5(int n) // OK: move
{
vector<int> v(n);
// ... initialize v ...
return v;
}
unique_ptr<int[]> f6(int n) // bad: loses n
{
auto p = make_unique<int[]>(n);
// ... initialize *p ...
return p;
}
owner<int*> f7(int n) // bad: loses n and we might forget to delete
{
owner<int*> p = new int[n];
// ... initialize *p ...
return p;
}
- 当接口使用字符串参数表示各种选项时,它可能直接在内部知道这些选项的有效性。这种情况下,可以避免不必要的检查,因为实现已经了解可能的选项,并且不需要显式验证每个字符串
- Flag(pointer, count) style interfaces 与 安全的容器类或标准容器库
6. catch run-time errors early
- Look at pointers and arrays: Do range-checking early and not repeatedly
void increment1(int* p, int n) // bad: error-prone
{
for (int i = 0; i < n; ++i) ++p[i];
}
// 应该更早地去检测代码,而不是在runtime去检测
void use1(int m)
{
const int n = 10;
int a[n] = {};
// ...
increment1(a, m); // maybe typo, maybe m <= n is supposed
// but assume that m == 20
// ...
}
void increment2(span<int> p)
{
for (int& x : p) ++x;
}
// 根据m与n的关系对函数结果进行判断并输出
void use2(int m)
{
const int n = 10;
int a[n] = {};
// ...
increment2({a, m}); // maybe typo, maybe m <= n is supposed
// ...
}
void use3(int m)
{
const int n = 10;
int a[n] = {};
// ...
increment2(a); // the number of elements of a need not be repeated
// ...
}
- Look at conversions: Eliminate or mark narrowing conversions
动态检查中dynamic_cast和typeid一般只用于处理多态类型,一般不用于检查转换的精度和范围,对于精度检查,一般通过条件语句来检查
int main() {
try {
int largeValue = 1000;
short smallValue = largeValue; // Narrowing conversion
if (smallValue != largeValue) {
throw std::runtime_error("Narrowing conversion occurred! Data loss or overflow might have happened.");
}
} catch (const std::runtime_error& e) {
std::cerr << "Exception caught: " << e.what() << std::endl;
}
return 0;
}
- Look for unchecked values coming from input
在runtime检查unchecked values coming from input是在程序runtime时,检查程序中的unchecked输入。这种检查通常是为了确保程序在处理输入时不会出现意外情况或漏洞。如对用户登录系统,检查用户名是否符合输入要求。
int main() {
std::string username;
std::string password;
// Simulating user input
std::cout << "Enter your username: ";
std::getline(std::cin, username); // Assuming the user enters nothing and just presses enter
// Runtime check for unchecked values coming from input
if (username.empty()) {
std::cerr << "Error: Username cannot be empty." << std::endl;
// Take appropriate action, such as terminating the program or prompting for input again
return 1; // Exiting the program with an error code
}
// Further checks such as password strength, etc.
return 0;
}
- Look for structured data (objects of classes with invariants) being converted into strings(avoid)
Date read_date(istream& is); // read date from istream
Date extract_date(const string& s); // extract date from string
void user1(const string& date) // manipulate date
{
auto d = extract_date(date);
// ...
}
void user2()
{
Date d = read_date(cin);
// ...
user1(d.to_string());
// ...
}
- don‘t add validity checks that change the asymptotic hebavior of the interface. O(n) check added into average complexity of O(1)
class Jet { // Physics says: e * e < x * x + y * y + z * z
float x;
float y;
float z;
float e;
public:
Jet(float x, float y, float z, float e)
:x(x), y(y), z(z), e(e)
{
// 不需要检查该变量的范围,因为计算复杂度
}
float m() const
{
// Should I handle the degenerate case here?
return sqrt(x * x + y * y + z * z - e * e);
}
???
};
Don’t leak any resources
leak与cleanable
void createVector() {
std::vector<int>* ptr = new std::vector<int>(); // 分配一个vector<int>的动态数组
// 这个动态数组被创建,但在函数结束后,指针ptr将会丢失,没有办法释放对应的内存
// 假设这里发生了一些其他的逻辑操作,但最终函数结束时,ptr仍然没有被释放
}
int main() {
createVector(); // 调用createVector函数
// 假设这里是程序的其他部分,这部分不会访问createVector函数中分配的内存
// 在程序结束时,操作系统会回收createVector函数中分配的内存,
// 所以这个例子中的内存泄漏是可以被清理的,但它是一种泄漏,因为程序员忘记了释放资源。
return 0;
}
void f(char* name)
{
FILE* input = fopen(name, "r");
// ...
if (something) return; // bad: if something == true, a file handle is leaked
// ...
fclose(input);
}
void f(char* name)
{
ifstream input {name};
// ...
if (something) return; // OK: no leak
// ...
}
上述被称为RAII技术,可以保证无泄漏。同时如果保证 type and bounds profiles 那么会保证type和resources safety
- 需要明确pointer的owner【pointers: non-owners and owners, for non-owners pointers, mark and owner as such using owner from the GSL】
void processArray(int* arr, int size) {
// 处理数组
}
int main() {
int* ptr = new int(10); // 使用new在堆上分配一个整数,并将指针赋给ptr,ptr是所有者指针
std::cout << *ptr << std::endl;
delete ptr; // 手动释放资源,避免内存泄漏
return 0;
}
int main() {
std::unique_ptr<int> ptr(new int(10)); // 使用std::unique_ptr替代所有者指针
std::cout << *ptr << std::endl;
// 不需要手动释放资源,当ptr超出作用域时,资源会自动释放
return 0;
}
void processArray(gsl::owner<int*> arr, int size) {
// 处理数组
delete[] arr; // 手动释放资源
}
-
look for naked new and delete
-
look for known resource allocating functions return raw pointers(such as fopen()【file open】, malloc()【空间分配】 and strdup()【空间复制】)
// 函数声明:返回原始指针的资源分配函数
char* allocateMemory() {
char* ptr = strdup("Hello, world!"); // strdup 函数用于复制字符串,返回动态分配的内存的指针
return ptr;
}
int main() {
char* ptr = allocateMemory(); // 调用返回原始指针的资源分配函数
// 使用返回的指针
if (ptr != nullptr) {
std::cout << ptr << std::endl;
free(ptr); // 手动释放内存,因为 strdup 返回的是动态分配的内存
}
return 0;
}
Don’t waste time or space
// bad
struct X {
char ch;
int i;
string s;
char ch2;
X& operator=(const X& a);
X(const X&);
};
X waste(const char* p)
{
if (!p) throw Nullptr_error{};
int n = strlen(p);
auto buf = new char[n];
if (!buf) throw Allocation_error{};
for (int i = 0; i < n; ++i) buf[i] = p[i];
// ... manipulate buffer ...
X x;
x.ch = 'a';
x.s = string(n); // give x.s space for *p
for (gsl::index i = 0; i < x.s.size(); ++i) x.s[i] = buf[i]; // copy buf into x.s
delete[] buf;
return x;
}
void driver()
{
X x = waste("Typical argument");
// ...
}
问题:
- X struct空间过大,数据有冗余
- copy构造(X&&)无法使用
- new delete 冗余
- 函数复杂
// good
#include <string>
#include <stdexcept> // For exception handling
struct X {
char ch;
int i;
std::string s;
char ch2;
X& operator=(const X& a) {
// Implementation of copy assignment operator
if (this != &a) {
ch = a.ch;
i = a.i;
s = a.s;
ch2 = a.ch2;
}
return *this;
}
X(const X& other) {
// Implementation of copy constructor
ch = other.ch;
i = other.i;
s = other.s;
ch2 = other.ch2;
}
// Move constructor
X(X&& other) noexcept : ch(other.ch), i(other.i), s(std::move(other.s)), ch2(other.ch2) {}
// Move assignment operator
X& operator=(X&& other) noexcept {
if (this != &other) {
ch = other.ch;
i = other.i;
s = std::move(other.s);
ch2 = other.ch2;
}
return *this;
}
};
X waste(const char* p) {
if (!p) throw std::invalid_argument("Null pointer exception");
int n = strlen(p);
// Directly use std::string instead of manual memory allocation
std::string buf(p);
X x;
x.ch = 'a';
// Use std::string constructor to allocate space for p
x.s = std::move(buf);
return x;
}
void driver() {
X x = waste("Typical argument");
// ...
}
void lower(zstring s)
{
for (int i = 0; i < strlen(s); ++i) s[i] = tolower(s[i]);
}
// good
void lower(zstring s)
{
int len = strlen(s);
for(int i = 0; i < len; i++)
s[i] = tolower(s[i]);
}
对非user-defined postfix++和prefix++建议使用prefix
prefer immutable data to mutable data
immutable vs. mutable
It is easier to reason about constants than about variables.
Something immutable cannot change unexpectedly.
Sometimes immutability enables better optimization.
#include <iostream>
#include <vector>
// 使用常量定义数组大小
const int ARRAY_SIZE = 5;
// 使用常量引用传递参数
void printVector(const std::vector<int>& vec) {
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
// 定义一个常量
const int MAX_VALUE = 100;
// 常量数组
int array[ARRAY_SIZE] = {1, 2, 3, 4, 5};
// 常量向量
std::vector<int> vec = {10, 20, 30, 40, 50};
// 使用常量
std::cout << "Max value: " << MAX_VALUE << std::endl;
// 修改常量的值,编译器将报错
// MAX_VALUE = 200; // Error: assignment of read-only variable 'MAX_VALUE'
// 使用常量数组
std::cout << "Array elements: ";
for (int i = 0; i < ARRAY_SIZE; ++i) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
// 使用常量引用传递参数
std::cout << "Vector elements: ";
printVector(vec);
// 修改常量向量,编译器将报错
// vec.push_back(60); // Error: passing 'const std::vector<int>' as 'this' argument discards qualifiers [-fpermissive]
return 0;
}
Encapsulate messy constructs, rather than spreading through the code
int sz = 100;
int* p = (int*) malloc(sizeof(int) * sz);
int count = 0;
// ...
for (;;) {
// ... read an int into x, exit loop if end of file is reached ...
// ... check that x is valid ...
if (count == sz)
p = (int*) realloc(p, sizeof(int) * sz * 2);
p[count++] = x;
// ...
}
// 建议使用STL或者GSL实现的方法
vector<int> v;
v.reserve(100);
// ...
for (int x; cin >> x; ) {
// ... check that x is valid ...
v.push_back(x);
}
Use supporting tools as appropriate
静态分析工具
动态分析工具
测试工具
Use support libraries as appropriate
ISO c++ standard lib(SL the standard library)
guideline suuport lib(GSL)
C++ 运行时关键字
++i与i++
++i
++i 不会产生临时对象
int& int::operator++ (){
*this +=1;
return *this;
}
i++
i++ 产生临时对象,会导致效率降低
const int int::operator(int){
int oldValue = *this;
++(*this);
return oldValue;
}
正则表达式
常用的C++正则表达式特殊字符与含义
.
:匹配任意单个字符(除了换行符)。hello\nworld\nhello again
中的.e
^
:匹配输入字符串的开始位置。如果用在多行模式里,它还可以匹配每一行的开头。hello\nworld\nhello again
中的^hello
$
:匹配输入字符串的结束位置。如果用在多行模式里,它还可以匹配每一行的结尾。This is line 1.\nThis is line 2.\nThis is line 3.
中的\\n$
*
:匹配前面的子表达式零次或多次。例如,zo*
能匹配z
以及zoo
+
:匹配前面的子表达式一次或多次。例如,zo+
能匹配zo
以及zoo
,但不能匹配z
?
:匹配前面的子表达式零次或一次。例如,do(es)?
可以匹配do
或does
{n}
:n 是一个非负整数。匹配确定的 n 次。例如,o{2}
不能匹配Bob
中的o
,但是能匹配food
中的两个o
{n,}
:n 是一个非负整数。匹配至少 n 次。例如,o{2,}
不能匹配Bob
中的o
,但能匹配foooood
中的所有o
{n,m}
:m 和 n 均为非负整数,其中 n <= m。匹配至少 n 次,但不超过 m 次。例如,o{1,3}
将匹配fooooood
中的前三个o
[...]
:字符集。匹配方括号内的任意一个字符。例如,[abc]
将匹配plain
中的a
[^...]
:否定字符集。匹配任何不在方括号内的字符。例如,[^abc]
将匹配plain
中的p
,l
,i
和n
\
:转义字符。用于匹配具有特殊含义的字符,或者将特殊字符转义为普通字符。例如,\.
匹配句点字符-
|
:或者。匹配符号前后的任意一个表达式。例如, zoo|dog
能匹配zoo
或dog
(...)
:捕获括号。用于将匹配到的子串分组,并可以在后续的正则表达式或替换操作中引用。\d
:匹配任意数字字符,等价于[0-9]
。\D
:匹配任意非数字字符,等价于[^0-9]
。\s
:匹配任意空白字符,包括空格、制表符、换页符等。\S
:匹配任意非空白字符。\w
:匹配任意字母、数字或下划线字符,等价于[a-zA-Z0-9_]
\W
:匹配任意非字母、非数字、非下划线字符。
应用
- 一种文本处理工具,通过定义一种模式,在一个字符串中搜索匹配该模式的子串。
- 验证数据格式:验证用户输入是否符合预期格式,如电子邮件地址、电话号码、社会安全号码等;验证文件路径或URL的格式是否正确。
- 文本搜索和替换:在大量文本中查找特定的模式或单词,并进行替换;在源代码或日志文件中搜索特定的错误或警告信息。
- 词法分析:在编译器或解释器的词法分析阶段,使用正则表达式来识别编程语言中的关键字、标识符、数字、运算符等。
- 分割字符串:使用正则表达式作为分隔符来分割字符串,这比传统的基于固定字符的分割方法更灵活。
- 数据清洗:清理HTML或XML标签,从文本中移除不必要的字符或格式;去除文本中的特殊字符或空格。
- 模式匹配:在生物学中,用于匹配DNA或RNA序列;在网络安全领域,用于识别恶意代码或网络流量中的异常模式。
- 提取信息:从日志文件中提取日期、时间、事件类型等信息;从网页或文本文件中提取特定的数据字段。
// 验证电子邮箱格式
#include <iostream>
#include <regex>
#include <string>
bool isValidEmail(const std::string& email) {
std::regex e ("^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$");
return std::regex_match(email, e);
}
int main() {
std::string email = "example@example.com";
if (isValidEmail(email)) {
std::cout << email << " is a valid email address." << std::endl;
} else {
std::cout << email << " is not a valid email address." << std::endl;
}
return 0;
}
// 文本替换
#include <iostream>
#include <regex>
#include <string>
std::string replaceNumbersWithStars(const std::string& text) {
std::regex e ("\\d+"); // 匹配一个或多个数字
return std::regex_replace(text, e, "*");
}
int main() {
std::string text = "There are 123 apples and 456 oranges.";
std::string result = replaceNumbersWithStars(text);
std::cout << result << std::endl; // 输出: There are *** apples and *** oranges.
return 0;
}
// 词法分析,识别文本种的数字
#include <iostream>
#include <regex>
#include <string>
#include <vector>
std::vector<std::string> tokenizeNumbers(const std::string& text) {
std::regex e ("\\d+"); // 匹配一个或多个数字
std::sregex_token_iterator iter(text.begin(), text.end(), e);
std::sregex_token_iterator end;
std::vector<std::string> tokens(iter, end);
return tokens;
}
int main() {
std::string text = "The price is 123 dollars.";
auto tokens = tokenizeNumbers(text);
for (const auto& token : tokens) {
std::cout << token << std::endl; // 输出: 123
}
return 0;
}
// 分割字符串
#include <iostream>
#include <regex>
#include <string>
#include <vector>
std::vector<std::string> splitString(const std::string& text, const std::string& delimiter) {
std::regex e (delimiter);
std::sregex_token_iterator iter(text.begin(), text.end(), e, -1);
std::sregex_token_iterator end;
std::vector<std::string> tokens(iter, end);
return tokens;
}
int main() {
std::string text = "apple,banana,cherry";
auto tokens = splitString(text, ",");
for (const auto& token : tokens) {
std::cout << token << std::endl; // 输出: apple, banana, cherry
}
return 0;
}
// 数据清洗,清除HTML标签
#include <iostream>
#include <regex>
#include <string>
std::string removeHtmlTags(const std::string& html) {
std::regex e ("<[^>]*>"); // 匹配所有HTML标签
return std::regex_replace(html, e, "");
}
int main() {
std::string html = "<p>Hello, <b>world</b>!</p>";
std::string text = removeHtmlTags(html);
std::cout << text << std::endl; // 输出: Hello, world!
return 0;
}
// 模式匹配
#include <iostream>
#include <regex>
#include <string>
int main() {
// 假设我们有一些可能包含恶意内容的文本
std::string text = "This is a normal text. However, it contains some BAD_STUFF that we need to detect.";
// 定义一个正则表达式来匹配恶意内容
// 这个例子中,我们简单地查找"BAD_STUFF"这个字符串
std::regex pattern("BAD_STUFF");
// 使用std::sregex_search来搜索匹配项
if (std::sregex_search(text, pattern)) {
std::cout << "Malicious content detected!" << std::endl;
} else {
std::cout << "No malicious content found." << std::endl;
}
return 0;
}
// 提取信息
#include <iostream>
#include <regex>
#include <string>
#include <sstream>
int main() {
// 假设我们有一个包含姓名和年龄的字符串
std::string input = "John Doe, 30 years old";
// 定义一个正则表达式来匹配姓名和年龄
std::regex pattern(R"((\w+)\s+(\w+),\s+(\d+)\s+years\s+old)");
// 创建一个smatch对象来保存匹配结果
std::smatch match;
// 尝试匹配字符串
if (std::regex_search(input, match, pattern)) {
// 提取姓名和年龄
std::string name = match[1].str() + " " + match[2].str();
int age = std::stoi(match[3].str());
// 输出提取的信息
std::cout << "Name: " << name << std::endl;
std::cout << "Age: " << age << std::endl;
} else {
std::cout << "No match found." << std::endl;
}
return 0;
}
assert断言
一般用于debug程序的逻辑,不用于release版本
- assert宏
assert(x >0)
- #error方法
#if defined(DEBUG)
// 在调试模式下执行某些操作
#else
#error "DEBUG macro is not defined. Please define DEBUG for release builds."
#endif
- 模板的assert
template< class T >
struct Check {
static_assert( sizeof(int) <= sizeof(T), "T is not big enough!" ) ;
} ;
this指针使用
作用
- 指向非静态成员函数所作用的对象
什么时候创建
- 调用非静态函数时才会使用的
delete this
- 为将被释放的内存调用一个或多个析构函数(因此不能在析构中调用delete this),类对象的内存空间被释放,之后不能涉及this指针,如操作数据成员,调用虚函数等
lambda 表达式
lambda表达式是一种匿名函数对象,可以捕获所在作用域中的变量,并在需要时执行特定的操作。 提供了一种匿名函数的特性,可以编写内嵌的匿名函数,用于替换独立函数,而且更可读 本质上来讲, lambda 表达式只是一种语法糖,因为所有其能完成的⼯作都可以⽤其它稍微复杂的代码来实现。
从[]开始,结束于{},{}内定义的是lambda表达式体
auto basicLambda = [] { cout << "Hello, world!" << endl; };
basicLambda();
带返回值类型的
auto add[](int a, int b) -> int{return a+b;};
auto multiply = [](int a, int b)-> {return a*b;};
int sum = add(2,3);
int product = multiply(2, 5);
[]闭包: 实现原理是每次定义lambda表达式后,都会自动生成匿名类,称为闭包类型。运行时候,lambda表达式会返回一个匿名闭包实例,实际是右值。其可以通过传值或引用的方式捕捉封装作用域的变量
int main() {
int x = 10;
auto add_x = [x](int a) { return a + x; };
auto multiply_x = [&x](int a) { return a * x; };
cout << add_x(10) << " " << multiply_x(10) << endl;
// 输出:20 100
return 0;
}
[]:默认不捕获任何变量 [=]:默认以值捕获所有变量; [&]:默认以引⽤捕获所有变量; [x]:仅以值捕获x,其它变量不捕获; [&x]:仅以引⽤捕获x,其它变量不捕获; [=, &x]:默认以值捕获所有变量,但是x是例外,通过引⽤捕获; [&, x]:默认以引⽤捕获所有变量,但是x是例外,通过值捕获; [this]:通过引⽤捕获当前对象(其实是复制指针); [*this]:通过传值⽅式捕获当前对象
应用于函数的参数,实现回调
int val = 3;
vector<int> v{1,8,3,4,7,3};
int count = std::count_if(v.begin(), v.end(), [val](int x) {return x >3;});
类型转换
static_cast 派生->基类安全,反向不安全
- 基本数据类型之间的转换
- void*和其他类型指针之间的转换
- 子类对象的指针转换成父类对象指针
- 最好所有隐式转换都用static_cast代替
dynamic_cast
- 用于安全的向下转型
- 转换成功会返回引用或者指针,失败返回null,否则会抛出一个
bad_cast
的异常类型
- 转换成功会返回引用或者指针,失败返回null,否则会抛出一个
const_cast
- 用于移除指针和引用的常量性,但是不能改变原来常量的常量性
- 指向常量的指针被转化成非常量指针
- 常量引用被转换成非常量引用
- 常量对象被转换成非常量对象
reinterpret_cast
高危险性操作
reinpreter_cast<type-id> (expression)
- 可以将任意类型指针转换为其他类型的指针。所以他的type-id必须是一个指针、引用、算术类型。
- 能够在非相关的类型之间转换。它可以把一个指针转换成一个整数,也可以把一个整数转换成一个指针。
应用
- 一般不要使用dynamic_cast、reinterpret_cast
类型检查
用于检查变量或表达式的类型。例如:
int n = 10;
if (typeid(n) == typeid(int)) {
// n 是 int 类型
}
动态分配和释放内存
new/delete与malloc/free
相同
- 申请动态内存和释放动态内存
不同 new/delete带构造析构部分
- 返回类型安全性 (new返回安全,malloc返回
void *
) - 返回失败后返回值 (new失败后要捕获异常
bad_alloc
,malloc返回nullptr) - 是否指定内存大小(new不,malloc需要)
- 后续内存分配(new 没有配备,malloc如果不够,使用realloc进行扩充)
应用上共存
- 对于需要初始化的场景,使用new更合适
- 对于c程序需要使用malloc/free管理内存
配对 new和delete、malloc和free、new[]和delete[]要配对使用
free原理
- glibc中的free,空间的大小记录在参数指针指向地址的前面,free的时候通过这个记录即可知道要释放的内存有多大。
- 同时free(p)表示释放p对应的空间,但p这个pointer仍然存在,只是不能操作
- free后的内存会使用双链表保存,供下次使用,避免频繁系统调用,同时有合并功能,避免内存碎片
使用
char* p = (char*) malloc(10);
free(p);
p = NULL;
非静态this指针的处理
见编译中的静态thie指针的处理
##
C++封装继承与多态
与其他语言的区别
与C区别
区别 | C | C++ |
---|---|---|
头文件 | .h | .h .hpp |
命名空间 | 不支持 | 支持 |
空间分配 | malloc、free、calloc、realloc | new、delete、malloc、free |
引用 | 不支持 | 支持 |
struct | 仅为变量;为private;无法初始化、定义别名与使用模板 | 支持函数;为public;支持初始化、定义别名与使用模板 |
auto、explicit | 不支持 | 支持 |
重载与虚函数 | 不支持 | 支持 |
dynamic_cast | 不支持 | 支持 |
模板 | 不支持 | 支持、STL |
与Java区别
区别 | Java | C++ |
---|---|---|
指针 | 无法访问 | 支持访问 |
继承 | 不支持多重继承、但支持多个接口 | 支持多重继承,接口类似虚函数概念 |
函数与变量 | 除基本类型外,都是类的函数 | 支持类外函数与变量 |
struct与union | 不支持 | 支持 |
内存管理 | 均为new出来的,回收自动 | 支持malloc、free、new、delete |
操作符重载 | 不支持 | 支持 |
预编译 | 不支持 | 支持 |
字符串 | 类对象实现 | 结尾以null为终止符 |
异常处理机制 | try-catch-finally、类型确定、无返回码 | try-catch、类型不确定、有返回码 |
类的封装、继承与多态
类的封装
封装原因
- 结合:将属性与方法结合;
- 接口:利用接口机制隐藏内部实现细节,只留下接口供外部调用;
- 复用:实现代码复用
类的大小
class A{}; sizeof(A) = 1;
class A{virtual Fun(){} }; sizeof(A) = 4(32bit)/8(64bit)
class A{static int a; }; sizeof(A) = 1;
class A{int a; }; sizeof(A) = 4;
class A{static int a; int b; }; sizeof(A) = 4;
类的构造函数
构造类型
- 默认构造:无参构造
- 一般构造:包含各种参数,参数顺序个数不同,可以有不同构造
- 拷贝构造:
- 出现环境:对象以值传递方式进入函数体、以值传递的方式从函数返回、一个对象需要另外对象初始化
- 函数参数必须为引用
- 如果是值传递,作为参数需要构造生成副本,再次调用拷贝构造,形成无限递归
- 浅拷贝,存在问题(当有指针的时候,会有两个指针指向相同的位置),进行重写(申请空间存储数据)
- 移动构造
- 避免分配新空间,将原来的对象直接拿过来使用
- 赋值运算符的重载
- 类似构造函数,将右边的对象赋值给左边的对象,但不属于构造函数
- 要求两边对象创建
- 类型转换构造
- 根据指定类型的对象,构造一个本类的对象。
- 如果不想默认转换,需要使用explicit阻止隐式转换
构造中构造与析构函数是否可抛出异常
构造函数
- C++ 只会析构已经完成的对象,对象只有在其构造函数执⾏完毕才算是完全构造妥当。在构造函数中发⽣异常,控制权转出构造函数之外。
- 因此,在对象 b 的构造函数中发⽣异常,对象b的析构函数不会被调⽤。因此会造成内存泄漏
- ⽤ auto_ptr 对象来取代指针类成员,便对构造函数做了强化,免除了抛出异常时发⽣资源泄漏的危机,不再需要在析构函数中⼿动释放资源;
析构函数
- 如果控制权基于异常的因素离开析构函数,⽽此时正有另⼀个异常处于作⽤状态,C++ 会调⽤ terminate 函数让程序结束;
- 如果异常从析构函数抛出,⽽且没有在当地进⾏捕捉,那个析构函数便是执⾏不全的。如果析构函数执⾏不全,就是没有完成他应该执⾏的每⼀件事情。
构造中的问题
构造中的内存泄漏问题
- 原因:c++只会析构已经完成的对象。
- 出现:如果构造函数中发生异常,不会调用析构函数。如果在构造函数中申请了内存操作,则会造成内存泄漏。
- 派生类有问题:如果有继承关系,派生类中的构造函数抛出异常,那么基类的构造函数和析构函数可以照常执行的。
- 解决办法:用智能指针来管理内存
拷贝构造中的浅拷贝和深拷贝
使用深拷贝的场景
- 在copy构造中,copy的对象是否存在指针,如果有需要重写copy构造,因为浅拷贝不会存储数据,相同指针指向同一对象,当数据成员中有指针时,必须要用深拷贝。
系统默认
系统默认的拷贝函数——即浅拷贝。当数据成员中没有指针时,浅拷贝是可行的;
原因 如果没有自定义拷贝构造函数,会调用默认拷贝构造函数,这样就会调用两次析构函数。第一次析构函数delete了内存,第二次的就指针悬挂了。所以,此时,必须采用深拷贝。
操作
- 深拷贝在堆内存中另外申请空间来储存数据,从而也就解决了指针悬挂的问题。 简而言之,当数据成员中有指针时,必须要用深拷贝。
类的析构函数
析构与构造不同的是,构造只用于初始化参数,析构除了撤销对象外,一般还用于解决对象分配的内存空间等。 析构中的问题
- 析构函数不能、也不应该抛出异常
- 析构函数抛出异常,则异常点之后的程序不会执行,造成资源泄露
- 异常发生时,异的传播过程中会进行栈展开。调用已经在栈构造好的对象的析构函数来释放资源,此时若其他析构函数本身也抛出异常,则前一个异常尚未处理,又有新的异常,会造成程序崩溃。
- 解决办法:把异常完全封装在析构函数内部,决不让异常抛出函数之外
继承
继承原因
- 接口:使用所有非私有方法
- 复用:继承属性与方法,减少代码的书写
- 重写:重写父类的方法以增加子类的功能
继承类型
- 单一继承:继承一个父类,最多使用
- 多重继承:一个类有多个基类,类之间使用逗号隔开
- 菱形继承:BC继承自A,D继承自BC
继承缺点
- 耦合:耦合性太大
- 封装:破坏了类的封装性
- 解决:使用抽象方法的继承和接口
computional alg
算法
常用算法方法
- 凸包算法:凸包是指一组点在平面上的最小凸多边形,也就是说,它包含了所有的点,并且没有任何一个点在它的内部或边界上。计算凸包的算法有很多,比如Graham扫描法,Jarvis步进法,分治法等
- 线段相交算法:线段相交是指给定平面上的一些线段,求出它们之间的所有交点。线段相交的算法有很多,比如扫描线法,平面扫描法,弯曲扫描法等
- 最近点对算法:最近点对是指给定平面上的一些点,求出距离最近的两个点。最近点对的算法有很多,比如分治法,旋转卡壳法,随机化增量法等。
- 最大空圆算法:最大空圆是指给定平面上的一些点,求出一个圆,使得它不包含任何一个点,并且它的半径最大。最大空圆的算法有很多,比如随机化增量法,Voronoi图法,Delaunay三角剖分法等。
知道两个点,求直线方程
#include <iostream>
#include <tuple>
#include <optional>
#include <format>
using namespace std;
const double epsilon = 1e-6;
struct Point{
double x;
double y;
};
std::optional<std::tuple<double,double,double>> line_equation(const Point& p1, const Point& p2){
bool x_equal = abs(p1.x - p2.x) < epsilon;
bool y_equal = abs(p1.y - p2.y) < epsilon;
if(x_equal && y_equal){
return std::nullopt;
}
double a = p2.y - p1.y;
double b = p1.x - p2.x;
double c = p2.x * p1.y - p1.x * p2.y;
return std::make_tuple(a,b,c);
}
点到直线的距离
#include <cmath>
//定义一个函数,接收点的坐标和直线的系数作为参数,返回点到直线的距离
constexpr double distance(double x0, double y0, double A, double B, double C) noexcept
{
//判断A和B是否同时为0
if (A == 0 && B == 0)
{
//抛出异常
throw std::invalid_argument("A and B cannot be both zero");
}
//计算分子
double numerator = std::abs(A * x0 + B * y0 + C);
//计算分母
double denominator = std::hypot(A, B);
//计算并返回距离
return numerator / denominator;
}
点到直线的投影
#include <cmath>
struct Point
{
double x;
double y;
};
//定义一个函数,接收点的坐标和直线的系数作为参数,返回点到直线的投影点的坐标
constexpr Point projection(double x0, double y0, double A, double B, double C) noexcept
{
//判断A和B是否同时为0
if (A == 0 && B == 0)
{
//抛出异常
throw std::invalid_argument("A and B cannot be both zero");
}
//取直线上任意一点Q,可以令x1=0, y1=-C/B
double x1 = 0;
double y1 = -C / B;
//计算向量PQ和n的内积
double dot = (x0 - x1) * A + (y0 - y1) * B;
//计算向量n的模长
double norm = std::hypot(A, B);
//计算投影点R的坐标
double x2 = x0 - dot / norm * A;
double y2 = y0 - dot / norm * B;
//返回投影点R
return Point{x2, y2};
}
点关于直线的对称点
#include <cmath>
//定义一个结构体,表示一个点的坐标
struct Point
{
double x;
double y;
};
//定义一个函数,接收点的坐标和直线的系数作为参数,返回点关于直线的对称点的坐标
constexpr Point symmetric_point(double x0, double y0, double A, double B, double C) noexcept
{
//判断A和B是否同时为0
if (A == 0 && B == 0)
{
//抛出异常
throw std::invalid_argument("A and B cannot be both zero");
}
//计算k和b
double k = -A / B;
double b = -C / B;
//计算d
double d = std::abs(k * x0 - y0 + b) / std::sqrt(k * k + 1);
//计算d'
double d_prime = d * std::abs(k) / std::sqrt(k * k + 1);
//计算n的模长
double norm = std::hypot(A, B);
//计算R的坐标
double x2 = x0 - 2 * d_prime * (-B) / norm;
double y2 = y0 - 2 * d_prime * A / norm;
//返回R
return Point{x2, y2};
}
两条直线的位置关系
#include <cmath>
//定义一个结构体,表示一个二维平面上的点
struct Point
{
double x; // x坐标
double y; // y坐标
};
//定义一个结构体,表示一个二维平面上的直线
struct Line
{
double A; // 直线方程的系数A
double B; // 直线方程的系数B
double C; // 直线方程的系数C
// 构造函数,通过两个点来确定一条直线
Line (const Point& p1, const Point& p2)
{
A = p2.y - p1.y;
B = p1.x - p2.x;
C = p2.x * p1.y - p1.x * p2.y;
}
// 构造函数,通过直线方程的系数来确定一条直线
Line (double A, double B, double C)
{
this->A = A;
this->B = B;
this->C = C;
}
// 判断两条直线是否相交,如果相交,返回true,并计算出交点
constexpr bool intersect (const Line& l, Point& p) const noexcept
{
// 计算两条直线方程的行列式
double D = std::hypot(A * l.B, B * l.A);
// 如果行列式为零,说明两条直线平行或重合
if (D == 0)
{
return false;
}
// 否则,计算出交点的坐标
p.x = (B * l.C - C * l.B) / D;
p.y = (C * l.A - A * l.C) / D;
return true;
}
// 判断两条直线是否平行,如果平行,返回true,并计算出平行距离
constexpr bool parallel (const Line& l, double& d) const noexcept
{
// 计算两条直线方程的行列式
double D = std::hypot(A * l.B, B * l.A);
// 如果行列式不为零,说明两条直线不平行
if (D != 0)
{
return false;
}
// 否则,计算出平行距离
d = std::abs (C - l.C) / std::hypot (A, B);
return true;
}
// 判断两条直线是否重合,如果重合,返回true
constexpr bool coincide (const Line& l) const noexcept
{
// 计算两条直线方程的行列式
double D = std::hypot(A * l.B, B * l.A);
// 如果行列式不为零,说明两条直线不重合
if (D != 0)
{
return false;
}
// 否则,判断常数项是否相等
return C == l.C;
}
};
判断点是否在多边形内部
#include <cmath>
#include <vector>
//定义一个结构体,表示一个二维平面上的点
struct Point
{
double x; // x坐标
double y; // y坐标
};
//定义一个函数,接收一个点和一个多边形(用std::vector表示)作为参数,返回这个点是否在多边形内部
constexpr bool point_in_polygon(const Point& p, const std::vector<Point>& polygon) noexcept
{
bool inside = false; // 初始化结果为false
for (std::size_t i = 0, j = polygon.size() - 1; i < polygon.size(); j = i++) // 遍历多边形的每条边
{
// 判断p的y坐标是否在边的y坐标范围内
if ((polygon[i].y > p.y) != (polygon[j].y > p.y))
{
// 计算p在边上的投影点的x坐标
auto x = (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x;
// 判断p是否在投影点的左侧
if (p.x < x)
{
// 如果是,说明射线与边相交,结果取反
inside = !inside;
}
}
}
return inside; // 返回结果
}
给定平面内n个点,构造一个多边形
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
// 定义一个二维点的结构体
struct Point {
double x, y; // 点的横纵坐标
Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数
};
// 计算两个向量的叉积
double cross(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}
// 计算两个向量的夹角
double angle(const Point& a, const Point& b) {
return atan2(cross(a, b), a.x * b.x + a.y * b.y);
}
// 比较两个点的极角大小,如果相等则比较距离大小
bool cmp(const Point& p1, const Point& p2) {
double ang = angle(p1, p2);
if (ang == 0) { // 极角相等,比较距离
return p1.x * p1.x + p1.y * p1.y < p2.x * p2.x + p2.y * p2.y;
}
return ang > 0; // 极角大于0,说明p1在p2的逆时针方向
}
// 求给定平面内n个点的凸包
vector<Point> convexHull(vector<Point>& points) {
int n = points.size(); // 点的个数
if (n <= 3) return points; // 如果点数小于等于3,直接返回
// 找到最左下角的点,并将其交换到第一个位置
int minIndex = 0;
for (int i = 1; i < n; i++) {
if (points[i].y < points[minIndex].y || (points[i].y == points[minIndex].y && points[i].x < points[minIndex].x)) {
minIndex = i;
}
}
swap(points[0], points[minIndex]);
// 将其他点按照极角排序
sort(points.begin() + 1, points.end(), cmp);
// 用一个栈来存储凸包上的点
stack<Point> s;
s.push(points[0]); // 先将极点入栈
s.push(points[1]); // 再将第二个点入栈
// 从第三个点开始遍历
for (int i = 2; i < n; i++) {
// 如果栈顶的两个点和当前点不构成逆时针旋转,则出栈
while (s.size() > 1) {
Point top = s.top(); // 栈顶元素
s.pop(); // 出栈
Point nextToTop = s.top(); // 出栈后的栈顶元素
if (cross(top - nextToTop, points[i] - top) > 0) { // 构成逆时针旋转
s.push(top); // 将原来的栈顶元素再入栈
break; // 跳出循环
}
}
s.push(points[i]); // 将当前点入栈
}
// 将栈中的点放入结果向量中
vector<Point> res;
while (!s.empty()) {
res.push_back(s.top());
s.pop();
}
return res;
}
给定n个点,找出距离最小的点
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
// 定义一个点结构体
struct Point {
double x, y; // 点的坐标
Point(double x = 0, double y = 0): x(x), y(y) {} // 构造函数
};
// 定义一个比较函数,按照x坐标升序排序
bool cmp_x(const Point& a, const Point& b) {
return a.x < b.x;
}
// 定义一个比较函数,按照y坐标升序排序
bool cmp_y(const Point& a, const Point& b) {
return a.y < b.y;
}
// 定义一个计算两点之间距离的函数
double dist(const Point& a, const Point& b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
// 定义一个求解给定点集中最小距离的函数
double solve(vector<Point>& points, int left, int right) {
// 如果只有一个点,返回无穷大
if (left == right) return 1e9;
// 如果只有两个点,返回它们之间的距离
if (left + 1 == right) return dist(points[left], points[right]);
// 如果有三个点,返回任意两点之间最小的距离
if (left + 2 == right) return min(dist(points[left], points[left + 1]), min(dist(points[left], points[right]), dist(points[left + 1], points[right])));
// 否则,将点集分成两部分
int mid = (left + right) / 2;
// 分别求解左右两部分的最小距离
double d1 = solve(points, left, mid);
double d2 = solve(points, mid + 1, right);
// 取两者中较小的值作为当前最小距离
double d = min(d1, d2);
// 找出所有距离中线不超过最小距离的点,并按照y坐标排序
vector<Point> temp;
for (int i = left; i <= right; i++) {
if (fabs(points[i].x - points[mid].x) <= d) {
temp.push_back(points[i]);
}
}
sort(temp.begin(), temp.end(), cmp_y);
// 遍历这些点,检查是否有更小的距离
for (int i = 0; i < temp.size(); i++) {
for (int j = i + 1; j < temp.size() && j <= i + 7; j++) {
d = min(d, dist(temp[i], temp[j]));
}
}
// 返回最小距离
return d;
}
对于平面内n条水平线,m条竖直线,求交点集合
// 定义点的数据类型
struct Point {
int x; // 横坐标
int y; // 纵坐标
Point(int x = 0, int y = 0) : x(x), y(y) {} // 构造函数
// 重载比较运算符
bool operator < (const Point& p) const {
return x < p.x || (x == p.x && y < p.y);
}
bool operator == (const Point& p) const {
return x == p.x && y == p.y;
}
bool operator != (const Point& p) const {
return !(*this == p);
}
// 重载加法运算符
Point operator + (const Point& p) const {
return Point(x + p.x, y + p.y);
}
};
// 定义线段的数据类型
struct Segment {
Point a; // 端点a
Point b; // 端点b
Segment(Point a = Point(), Point b = Point()) : a(a), b(b) {} // 构造函数
};
// 定义端点类型的枚举类型
enum EndpointType {
LEFT, // 左端点
RIGHT, // 右端点
UP, // 上端点
DOWN // 下端点
};
// 定义横纵坐标范围的常量
const int MIN_X = -10000; // 最小横坐标
const int MAX_X = 10000; // 最大横坐标
const int MIN_Y = -10000; // 最小纵坐标
const int MAX_Y = 10000; // 最大纵坐标
// 定义一个比较函数,用于优先队列的排序规则
struct CompareEndpoint {
bool operator () (const Endpoint& e1, const Endpoint& e2) const {
return e1.first > e2.first || (e1.first == e2.first && e1.second > e2.second);
}
};
// 定义一个优先队列,存储所有的端点,并按照横坐标从小到大排序
priority_queue<Endpoint, vector<Endpoint>, CompareEndpoint> pq;
// 定义一个比较函数,用于set的排序规则
struct CompareHorizontal {
bool operator () (const int& y1, const int& y2) const {
return y1 < y2;
}
};
// 定义一个set,存储当前活跃的水平线,并按照纵坐标从小到大排序
set<int, CompareHorizontal> horizontal;
// 定义一个map,存储当前活跃的竖直线,并记录它们的横坐标
map<int, bool> vertical;
// 定义一个函数,实现扫描线算法的主要逻辑
vector<Point> scanLine(vector<Segment>& horizontalLines, vector<Segment>& verticalLines) {
// 定义一个向量,存储所有的交点集合
vector<Point> intersections;
// 将所有的水平线和竖直线的端点放入优先队列中,并按照横坐标从小到大排序
for (auto& l : horizontalLines) {
pq.push({l.a, LEFT});
pq.push({l.b, RIGHT});
}
for (auto& l : verticalLines) {
pq.push({l.a, UP});
pq.push({l.b, DOWN});
}
// 从左到右扫描平面上的所有线段的端点
while (!pq.empty()) {
Endpoint p = pq.top();
pq.pop();
// 根据端点的类型和所属的线段,更新活跃集合,并检查是否有新的交点产生
switch (p.second) {
case LEFT: // 如果p是水平线l的左端点
horizontal.insert(p.first.y); // 将l插入到平衡二叉树中
for (auto& v : vertical) { // 遍历哈希表中所有竖直线
if (v.second && v.first >= p.first.x && v.first <= p.first.x + 1) { // 如果v存在且与l有交点(假设水平线和竖直线都是单位长度)
intersections.push_back(Point(v.first, p.first.y)); // 将交点加入到向量中
}
}
break;
case RIGHT: // 如果p是水平线l的右端点
horizontal.erase(p.first.y); // 将l从平衡二叉树中删除
break;
case UP: // 如果p是竖直线v的上端点
vertical[p.first.x] = true; // 将v插入到哈希表中,并标记为存在
auto it = horizontal.lower_bound(p.first.y); // 找到平衡二叉树中第一个大于等于p纵坐标的水平线y1
if (it != horizontal.end() && *it <= p.first.y + 1) { // 如果y1存在且与v有交点(假设水平线和竖直线都是单位长度)
intersections.push_back(Point(p.first.x, *it)); // 将交点加入到向量中
}
if (it != horizontal.begin()) { // 如果y1不是第一个水平线
it--; // 找到前一个水平线y2
if (*it >= p.first.y - 1) { // 如果y2与v有交点(假设水平线和竖直线都是单位长度)
intersections.push_back(Point(p.first.x, *it)); // 将交点加入到向量中
}
}
break;
case DOWN: // 如果p是竖直线v的下端点
vertical[p.first.x] = false; // 将v从哈希表中删除,并标记为不存在
break;
}
}
// 返回交点集合
return intersections;
}
// 定义一个函数,生成n条随机的水平线
vector<Segment> generateHorizontalLines(int n) {
vector<Segment> horizontalLines;
srand(time(NULL)); // 设置随机数种子
for (int i = 0; i < n; i++) {
int x1 = rand() % (MAX_X - MIN_X + 1) + MIN_X; // 随机生成左端点的横坐标
int x2 = x1 + 1; // 右端点的横坐标为左端点加1(假设水平线都是单位长度)
int y = rand() % (MAX_Y - MIN_Y + 1) + MIN_Y; // 随机生成纵坐标
horizontalLines.push_back(Segment(Point(x1, y), Point(x2, y))); // 将水平线加入到向量中
}
return horizontalLines;
}
// 定义一个函数,生成m条随机的竖直线
vector<Segment> generateVerticalLines(int m) {
vector<Segment> verticalLines;
srand(time(NULL)); // 设置随机数种子
for (int i = 0; i < m; i++) {
int x = rand() % (MAX_X - MIN_X + 1) + MIN_X; // 随机生成横坐标
int y1 = rand() % (MAX_Y - MIN_Y + 1) + MIN_Y; // 随机生成下端点的纵坐标
int y2 = y1 + 1; // 上端点的纵坐标为下端点加1(假设竖直线都是单位长度)
verticalLines.push_back(Segment(Point(x, y1), Point(x, y2))); // 将竖直线加入到向量中
}
return verticalLines;
}
求凸包的直径算法
旋转卡壳方法是一种求解凸包的直径的高效算法,它的基本思想是:从凸包上任意选取两个点作为初始对踵点,然后沿着凸包的边界逆时针旋转这两个点,直到找到最远的一对点,这就是凸包的直径。旋转卡壳方法的时间复杂度是O(n),其中n是凸包上的点的个数。
用C++实现旋转卡壳方法的代码如下:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 定义一个二维点的结构体
struct Point {
double x, y; // 点的坐标
Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数
};
//定义一个向量结构体
struct Vector {
double x, y; //向量的坐标
Vector(double x = 0, double y = 0): x(x), y(y) {} //构造函数
Vector(Point a, Point b): x(b.x - a.x), y(b.y - a.y) {} //由两点构造向量
};
// 计算两个点之间的距离
double dist(const Point& a, const Point& b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
//计算向量的叉积
double cross(Vector a, Vector b) {
return a.x * b.y - a.y * b.x;
}
//计算向量的模长
double length(Vector v) {
return sqrt(v.x * v.x + v.y * v.y);
}
//旋转卡壳方法求凸包的直径
double rotating_calipers(vector<Point>& points) {
int n = points.size(); //凸包上的点数
if (n == 2) return dist(points[0], points[1]); //如果只有两个点,直接返回距离
double ans = 0; //记录最大距离
int j = 2; //第二个指针,初始指向第三个点
for (int i = 0; i < n; i++) { //第一个指针,从第一个点开始逆时针旋转
Point a = points[i]; //第一个顶点
Point b = points[(i + 1) % n]; //第二个顶点,如果超过n,取余数
while (cross(Vector(a, b), Vector(a, points[j])) < cross(Vector(a, b), Vector(a, points[(j + 1) % n]))) { //如果叉积变小,说明第二个指针需要继续旋转
j = (j + 1) % n; //第二个指针逆时针旋转一步
}
ans = max(ans, max(dist(a, points[j]), dist(b, points[j]))); //更新最大距离,比较当前两对顶点的距离
}
return ans; //返回最大距离
}
共计 41 篇文章,6 页。