0%

安装

pip install openpyxl
需要在文件中包含图片:pip install pillow

打开保存

创建工作簿并保存

1
2
3
4
5
6
7
8
9
from openpyxl import Workbook
# 创建工作簿,包含一张默认工作表
wb = Workbook()
# active默认值为0,默认的工作表
ws = wb.active
print(ws.title) #...Sheet
# 保存工作簿,参数:路径
wb.save("test.xlsx")

加载已有的工作簿

1
2
3
4
5
from openpyxl import Workbook, load_workbook
# load_workbook加载工作簿
wb = load_workbook("test.xlsx")
ws = wb.active
print(ws.title)

操作工作表

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
from openpyxl import Workbook, load_workbook

wb = Workbook()
ws = wb.active

# Workbook.create_sheet创建新的工作簿
ws1 = wb.create_sheet("test1") # 默认在最后生成
ws2 = wb.create_sheet("test2", 0) # 在第一个位置生成
ws3 = wb.create_sheet("test3", -1) # 在倒数第二个生成
# 工作簿自动生成名字Sheeti,还可以通过title属性命名
ws.title = "New Title"
# 标题选项卡背景默认白色,可更改颜色
ws.sheet_properties.tabColor = "1072BA"
# 名字可以作为工作表的键,获取已有的表
ws4 = wb["test1"]
# wb.sheetnames获取所有表格
print(wb.sheetnames)
# 遍历工作表
for sheet in wb:
print(sheet.title)
# 改变位置
# 参数:工作表,偏移量(原地为0,向前为负,向后为正)
wb.move_sheet(ws3, -1)
# 删除
del wb["New Title"]
# 复制工作表
cp_sheet = wb.copy_worksheet(ws1)
print(cp_sheet.title) # ...test1 Copy

访问单元格

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
from openpyxl import Workbook

wb = Workbook()
ws = wb.active
# 单元格赋值
ws["a1"] = "test"
cell = ws.cell(6, 1, "test") # cell(行,列)获取对应单元格、cell(行,列,值)修改对应单元格的值
cell.value = "test1" # 单元格的value属性——>访问/修改

print(cell.value)
print(cell.coordinate) # 单元格坐标
print(cell.row) # 行
print(cell.column) # 列
print(cell.col_idx)
print(cell.column_letter)# 字母形式的列

x = 1
for i in range(1, 11): # range左闭右开,1~10
for j in range(1, 6):# 1~5
ws.cell(i, j, x) # 单元格赋值
x += 1
# a到c列
print(ws["a:c"])
'''元组套元组的形式
((<Cell 'Sheet'.A1>,....<Cell 'Sheet'.A10>),
(<Cell 'Sheet'.B1>,....<Cell 'Sheet'.B10>),
(<Cell 'Sheet'.C1>,....<Cell 'Sheet'.C10>))
'''
#1~5行
print(ws[1:5])
'''
((<Cell 'Sheet'.A1>, <Cell 'Sheet'.B1>, <Cell 'Sheet'.C1>, <Cell 'Sheet'.D1>, <Cell 'Sheet'.E1>),
......
(<Cell 'Sheet'.A5>, <Cell 'Sheet'.B5>, <Cell 'Sheet'.C5>, <Cell 'Sheet'.D5>, <Cell 'Sheet'.E5>))
'''
print(ws["a1:c4"])
'''
((<Cell 'Sheet'.A1>, <Cell 'Sheet'.B1>, <Cell 'Sheet'.C1>),
(<Cell 'Sheet'.A2>, <Cell 'Sheet'.B2>, <Cell 'Sheet'.C2>),
(<Cell 'Sheet'.A3>, <Cell 'Sheet'.B3>, <Cell 'Sheet'.C3>),
(<Cell 'Sheet'.A4>, <Cell 'Sheet'.B4>, <Cell 'Sheet'.C4>))
'''
print(ws["b"]) # 第b列
# 遍历:ws["a1:c4"]结果是元组的元组
for cells in ws["a1:c4"]:
for cell in cells:
print(cell.value)

操作单元格

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
from openpyxl import Workbook

wb = Workbook()
ws = wb.active

x = 1
for i in range(1, 11): # 1~10
for j in range(1, 11):
ws.cell(i, j, x)
x += 1

# 合并:只保留左上角的值
ws.merge_cells("b2:d4")
# 取消合并
ws.unmerge_cells("b2:d4")

# 插入
ws.insert_cols(2, 3) # 从第二列开始插入三列
ws.insert_rows(1, 2) # 从第一行开始插入两行
# 删除
ws.delete_cols(2, 3) # 从第二列开始删除三列
ws.delete_rows(2, 3) # 从第二行开始删除三行

# 移动
ws.move_range("c4:d5", 2, -2) # 向下移动两行,向左移动两列,下、右:正数,上、左:负数
wb.save("test5.xlsx")

使用公式

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
from openpyxl import Workbook
from openpyxl.utils import FORMULAE
from openpyxl.formula.translate import Translator

wb = Workbook()
ws = wb.active

# 添加一行,参数:可迭代的对象
ws.append(["price1", "price2", "sum", "average"])
ws.append([54, 21])
ws.append([12, 45])
ws.append([45, 78])
# 直接使用公式
ws["c2"] = "=SUM(a2:b2)"
ws["d2"] = "=AVERAGE(a2:b2)"

# 翻译源单元格的行为,参数:Translator(公式,复制源).(目标单元格)
ws["c3"] = Translator(formula="=SUM(a2:b2)", origin="c2").translate_formula("c3")
ws["c4"] = Translator(formula="=SUM(a2:b2)", origin="c2").translate_formula("c4")
ws["d3"] = Translator(formula="=AVERAGE(a2:b2)", origin="d2").translate_formula("d3")
ws["d4"] = Translator(formula="=AVERAGE(a2:b2)", origin="d2").translate_formula("d4")

# 通过遍历翻译单元格的行为
for cell in ws["c3:d4"]:
cell[0].value = Translator(formula="=SUM(a2:b2)", origin="c2").translate_formula(cell[0].coordinate)

for cell in ws["d3:d4"]:
cell[0].value = Translator(formula="=AVERAGE(a2:b2)", origin="d2").translate_formula(cell[0].coordinate)

wb.save("test6.xlsx")

排序

使用pandas
pip install pandas

1
2
3
4
5
6
7
8
9
10
import pandas as pd

# 获取工作簿的工作表
df = pd.read_excel("test7.xlsx", sheet_name="Sheet")
# 参数:排序依据(先按桃子排,桃子一样再按西瓜排),升序/降序
df_value = df.sort_values(by=["桃子", "西瓜"], ascending=False)
# 保存
writer = pd.ExcelWriter("test7_sort.xlsx")
df_value.to_excel(writer, sheet_name="Sheet_sort", index=False)
writer._save()

插入图表

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
from openpyxl import Workbook
from openpyxl.chart import Reference, LineChart

wb = Workbook()
ws = wb.active

rows = [
['月份', '桃子', '西瓜', '龙眼'],
[1, 23, 23, 56],
[2, 56, 56, 28],
[3, 58, 45, 74],
[4, 23, 23, 56],
[5, 56, 56, 28],
[6, 58, 45, 74],
]

for row in rows:
ws.append(row)

c1 = LineChart() # 实例化
c1.title = "水果销量折线图"
c1.style = 13
c1.y_axis.title = "销量"
c1.x_axis.title = "月份"

data = Reference(ws, min_row=1, max_row=7, min_col=2, max_col=4) # data范围
c1.add_data(data, titles_from_data=True) # true:范围表示包括title

s0 = c1.series[0]
# 样式
s0.marker.symbol = "triangle"
s0.marker.graphicalProperties.solidFill = "FF0000"
s0.marker.graphicalProperties.line.solidFill = "0000FF"

s1 = c1.series[1]
s2 = c1.series[2]
s2.smooth = True # 线条平滑
ws.add_chart(c1, "A8")
wb.save("test8.xlsx")

只读只写

把excel读到内存当中,大小是原来的50倍左右

只读模式

只读模式,如果需要读取很大的Excel文件,但是又不改变和保存,例如只读取数值用于其他数据分析,可以使用只读模式提供性能

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

# 加载Excel文件时使用read_only指定只读模式
'''
load_workbook参数说明:
定义:
def load_workbook(filename, read_only=False, keep_vba=KEEP_VBA, data_only=False, keep_links=True)
参数:
read_only:是否只读,默认False
keep_vba:是否使用VBA编程,默认False
data_only:是否只加载数据值,即丢弃公式、排序等操作,默认False
keep_links:是否保留超链接,默认True
'''
wb = load_workbook(filename='large_file.xlsx', read_only=True)
ws = wb['big_data']

# 可以正常读取值
for row in ws.rows:
for cell in row:
print(cell.value)

# 注意:读取完之后需要手动关闭避免内存泄露
wb.close()

只写模式

如果文件是以写为主,可以在创建工作簿的时候指定为只写模式以便提高性能,不管文件有多大,都可以把内存保持在10M以下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from openpyxl import Workbook
from openpyxl.cell import WriteOnlyCell
from openpyxl.comments import Comment
from openpyxl.styles import Font

wb = Workbook(write_only=True) # 创建工作簿时指定只写模式
ws = wb.create_sheet() # 需要通过create_sheet创建一个sheet

# 可以正常保存数据
for _ in range(100):
ws.append([i for i in range(200)]) # 只能通过append写

# 如果需要保留公式、注释等操作,可以使用WriteOnlyCell
cell = WriteOnlyCell(ws, value="test")
cell.font = Font(name='黑体', size=15)
cell.comment = Comment(text="这是注释", author="pan")

ws.append([cell])

wb.save('openpyxl/test.xlsx')

只写模式注意点:

  1. 需要通过create_sheet()创建表
  2. 只能通过append()增加数据,不能通过cell或iter_rows()
  3. wb.save()之后不能再修改,否则抛出WorkbookAlreadySaved异常

XML 树和元素

XML 是一种继承性的分层数据格式,最自然的表示方法是使用树。

为此, ET 有两个类

  1. ElementTree 将整个XML文档表示为一个树
  2. Element 表示该树中的单个节点

与整个文档的交互(读写文件)通常在 ElementTree 级别完成。 与单个 XML 元素及其子元素的交互是在 Element 级别完成的。

解析XML

  1. 从文件中读取来导入数据

    1
    2
    3
    import xml.etree.ElementTree as ET
    tree = ET.parse('country_data.xml')
    root = tree.getroot()

    parse()方法用来解析xml文档

  2. 直接从字符串中解析

    fromstring() 将 XML 从字符串直接解析为 Element ,该元素是已解析树的根元素

    1
    root = ET.fromstring(country_data_as_string)

    作为 Elementroot 具有标签和属性字典:

    1
    2
    3
    4
    >>> root.tag
    'data'
    >>> root.attrib
    {}

    还有可以迭代的子节点:

    1
    2
    3
    4
    5
    6
    for child in root:
    print(child.tag, child.attrib)

    country {'name': 'Liechtenstein'}
    country {'name': 'Singapore'}
    country {'name': 'Panama'}

    子级是可以嵌套的,我们可以通过索引访问特定的子级节点:

    1
    2
    >>> root[0][1].text
    '2008'

用于非阻塞解析的拉取 API

大多数解析函数都要求在返回任何结果之前一次性读取整个文档。

XMLParser :以增量方式添加数据,但这是在回调目标上调用方法的推送式 API。 有时用户真正想要的是能够以增量方式解析 XML 而无需阻塞操作,同时享受完整的已构造 Element 对象。

针对此需求的最强大工具是 XMLPullParser。 它不要求通过阻塞式读取来获得 XML 数据,而是通过执行 XMLPullParser.feed() 调用来增量式地添加数据。 要获得已解析的 XML 元素,应调用 XMLPullParser.read_events()

1
2
3
4
5
6
7
8
parser = ET.XMLPullParser(['start', 'end'])
parser.feed('<mytag>sometext')
list(parser.read_events())

parser.feed(' more text</mytag>')
for event, elem in parser.read_events():
print(event)
print(elem.tag, 'text=', elem.text)

应用:针对以非阻塞方式进行的应用程序,其中 XML 是从套接字接收或从某些存储设备增量式读取的。 在这些用例中,阻塞式读取是不可接受的。

缺点:因为其非常灵活,XMLPullParser 在更简单的用例中使用起来可能并不方便。

其他方法:

  • iterparse():不介意你的应用程序在读取 XML 数据时造成阻塞但仍希望具有增量解析能力。 它在你读取大型 XML 文档并且不希望将它完全放去内存时会很适用。
  • XMLPullParser.flush() :有助于减少延迟,适用于需要通过事件获得即时反馈的场合

查找元素

  • Element.iter():帮助递归遍历其下的所有子树(包括子级,子级的子级,等等)

    1
    2
    3
    4
    5
    6
    7
    8
    for neighbor in root.iter('neighbor'):
    print(neighbor.attrib)

    {'name': 'Austria', 'direction': 'E'}
    {'name': 'Switzerland', 'direction': 'W'}
    {'name': 'Malaysia', 'direction': 'N'}
    {'name': 'Costa Rica', 'direction': 'W'}
    {'name': 'Colombia', 'direction': 'E'}
  • Element.findall() :仅查找当前元素的直接子元素中带有指定标签的元素

  • Element.find() :找带有特定标签的 第一个 子级

然后可以用 Element.text 访问元素的文本内容。 Element.get 访问元素的属性:

1
2
3
4
5
6
7
8
for country in root.findall('country'):
rank = country.find('rank').text
name = country.get('name')
print(name, rank)

Liechtenstein 1
Singapore 4
Panama 68

ps:通过使用 XPath ,可以更精确地指定要查找的元素

修改XML文件

ElementTree 提供了一种构建XML文档并将其写入文件的简单方法。调用 ElementTree.write() 方法就可以实现。

创建后可以直接操作 Element 对象。例如:

假设我们要为每个国家/地区的中添加一个排名,并在排名元素中添加一个 updated 属性:

1
2
3
4
5
6
for rank in root.iter('rank'):
new_rank = int(rank.text) + 1
rank.text = str(new_rank)
rank.set('updated', 'yes')

tree.write('output.xml')
  • Element.remove() 删除元素

  • 假设我们要删除排名高于50的所有国家/地区:

    1
    2
    3
    4
    5
    6
    7
    for country in root.findall('country'):
    # using root.findall() to avoid removal during traversal
    rank = int(country.find('rank').text)
    if rank > 50:
    root.remove(country)

    tree.write('output.xml')

请注意在迭代时进行并发修改可能会导致问题,就像在迭代并修改 Python 列表或字典时那样。 因此,可以先通过 root.findall() 收集所有匹配的元素,在此之后再对匹配项列表进行迭代。

构建XML文档

SubElement() 函数还提供了一种便捷方法来为给定元素创建新的子元素

1
2
3
4
5
6
>>> a = ET.Element('a')
>>> b = ET.SubElement(a, 'b')
>>> c = ET.SubElement(a, 'c')
>>> d = ET.SubElement(c, 'd')
>>> ET.dump(a)
<a><b /><c><d /></c></a>

使用xml.dom解析xml

  • 文件对象模型(Document Object Model,简称DOM)
  • 一个 DOM 的解析器在解析一个 XML 文档时,一次性读取整个文档,把文档中所有元素保存在内存中的一个树结构里,之后你可以利用DOM 提供的不同的函数来读取或修改文档的内容和结构,也可以把修改过的内容写入xml文件。
  • python中用xml.dom.minidom来解析xml文件
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
#!/usr/bin/python
# -*- coding: UTF-8 -*-

from xml.dom.minidom import parse
import xml.dom.minidom

# 使用minidom解析器打开 XML 文档
DOMTree = xml.dom.minidom.parse("movies.xml")
collection = DOMTree.documentElement
if collection.hasAttribute("shelf"):
print "Root element : %s" % collection.getAttribute("shelf")

# 在集合中获取所有电影
movies = collection.getElementsByTagName("movie")

# 打印每部电影的详细信息
for movie in movies:
print "*****Movie*****"
if movie.hasAttribute("title"):
print "Title: %s" % movie.getAttribute("title")

type = movie.getElementsByTagName('type')[0]
print "Type: %s" % type.childNodes[0].data
format = movie.getElementsByTagName('format')[0]
print "Format: %s" % format.childNodes[0].data
rating = movie.getElementsByTagName('rating')[0]
print "Rating: %s" % rating.childNodes[0].data
description = movie.getElementsByTagName('description')[0]
print "Description: %s" % description.childNodes[0].data

XML

xml:可扩展标记语言

——>用来传输和存储数据

——没有预定义的标签

——对html的补充

描述:独立于软件和硬件的信息传输工具

python对xml的解析:

  1. SAX:事件驱动模型,通过在解析XML的过程中触发一个个的事件并调用用户定义的回调函数来处理XML文件
  2. DOM:将 XML 数据在内存中解析成一个树,通过对树的操作来操作XML
  3. ElementTree:轻量级的DOM

对比:DOM需要将XML数据映射到内存中的树,一是比较慢,二是比较耗内存,而SAX流式读取XML文件,比较快,占用内存少,但需要用户实现回调函数(handler)

python使用SAX解析xml

SAX是一种基于事件驱动的 API,牵涉到两个部分: 解析器事件处理器

  1. 解析器:读取XML文档,并向事件处理器发送事件,如元素开始跟元素结束事件。
  2. 事件处理器:负责对事件作出响应,对传递的XML数据进行处理。
  • 引入:import xml.sax

  • 继承基类,自定义相关的类

    • init方法
    • ContebtHandler类方法
      • characters(content):内容事件处理
      • startDocument() :文档启动的时候调用
      • endDocument() :解析器到达文档结尾时调用
      • startElement(name, attrs):遇到XML开始标签时调用,name是标签的名字,attrs是标签的属性值字典
      • endElement(name) :遇到XML结束标签时调用
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
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import xml.sax

class MovieHandler( xml.sax.ContentHandler ):
def __init__(self):
self.CurrentData = ""
self.type = ""
self.format = ""
self.year = ""
self.rating = ""
self.stars = ""
self.description = ""

# 元素开始事件处理
def startElement(self, tag, attributes):
self.CurrentData = tag
if tag == "movie":
print "*****Movie*****"
title = attributes["title"]
print "Title:", title

# 元素结束事件处理
def endElement(self, tag):
if self.CurrentData == "type":
print "Type:", self.type
elif self.CurrentData == "format":
print "Format:", self.format
elif self.CurrentData == "year":
print "Year:", self.year
elif self.CurrentData == "rating":
print "Rating:", self.rating
elif self.CurrentData == "stars":
print "Stars:", self.stars
elif self.CurrentData == "description":
print "Description:", self.description
self.CurrentData = ""

# 内容事件处理
def characters(self, content):
if self.CurrentData == "type":
self.type = content
elif self.CurrentData == "format":
self.format = content
elif self.CurrentData == "year":
self.year = content
elif self.CurrentData == "rating":
self.rating = content
elif self.CurrentData == "stars":
self.stars = content
elif self.CurrentData == "description":
self.description = content

if ( __name__ == "__main__"):

# 创建一个 XMLReader
parser = xml.sax.make_parser()
# turn off namepsaces
parser.setFeature(xml.sax.handler.feature_namespaces, 0)

# 重写 ContextHandler
Handler = MovieHandler()
parser.setContentHandler( Handler )

parser.parse("movies.xml")

2.1.1进程的概念、组成、特征

进程vs程序

  • 程序:静态的 可执行文件
  • 进程:动态的 程序的一次执行过程

进程的组成

  1. PCB/进程控制块:操作系统个管理进程所需要的信息,都记录在这,组成
    1. 进程描述信息
      • PID:进程唯一的身份标识
      • UID:进程所属用户ID
    2. 进程控制和管理信息
      • CPU、磁盘、网络流量使用情况统计
      • 进程当前状态
    3. 资源分配清单
      • 正在使用哪些文件、正在使用哪些内存区域、正在使用哪些I/O设备
    4. 处理机相关信息
      • 如PSW、PC等等寄存器的值——>用来实现进程切换
  2. 程序段:程序的代码
  3. 数据段:运行过程当中产生的各种数据

PCB是给操作系统用的——方便操作系统管理

程序段、数据段是给进程自己用的

程序的运行过程

image-20240629204733795

  1. 代码经过编译链接形成可执行文件==一系列指令
  2. 运行时将指令读入内存,创建对应的进程(创建对应的PCB)
  3. cpu从内存的程序段中读取指令、执行
  4. 运行过程中产生的数据保存在数据段

进程是系统进行资源分配和调度的一个独立单位

进程的特征:

  1. 动态性
  2. 并发性
  3. 独立性:进程是能独立运行、独立获得资源、独立接受调度的基本单位
  4. 异步性:各进程按照各自独立的、不可预知的速度向前推进,操作系统要提供“进程同步机制”来解决异步问题
  5. 结构性:进程——>PCB+程序段+数据段

2.1.2进程的状态和转换

进程的状态转换

image-20240630011111138

进程的组织

链接方式:

执行指针—>PCB1(指向当前处于运行态的进程,多少个cpu=最多有多少个进程处于运行态)

就绪队列指针—>PCB2—>PCB3—>PCB4(指向当前处于就绪态的进程,通常会把优先级高的进程放在队头)

阻塞队列指针—>PCB5—>PCB6

操作系统还会根据阻塞原因不同再分为多个阻塞队列,比如说:等待打印机的阻塞队列,等待磁盘的阻塞队列

索引方式(较少用)

image-20240630004846720

KMP算法

KMP算法:查找连续子串,返回值:str1中str2开始的位置/-1

例:str1:ABCD1234de

​ str2:1234 返回值:4

​ str3:1234e 返回值:-1

暴力解法:遍历str1,看每个开头能否配出str2

时间复杂度:O(mn)

KMP算法基础:next数组

——str2中每个字符对应一个信息:最长公共前后缀(该字符前面的字符串相等前缀和后缀的最大长度,并且不能取到整体)

例:abbabb k k==>3

长度 1 2 3 4 5 6
前缀 a ab abb abba abbab 不讨论
后缀 b bb abb babb bbabb
!= != == != !=

所以str2对应一个next arr==》用来加速匹配过程

例:str2={a,a,b,a,a,b,s}

next={-1,0,1,0,1,2,3} ps:next[0]=-1(人为规定),next[1]=0

KMP算法实现原理

——目的:让i跳的尽可能快(经典:i=i+1)

image-20240624223723044

(2)的证明通过反证法:设k在i~j之间,k开始能配出str2……推出跟最长公共前后缀矛盾

next数组的求法

求next[i]

找next[i-1]==》前缀的下一位?=next[i-1]

相等:next[i]=next[i-1]+1

不相等:cur再往前跳,来到cur对应前缀的下一位(next[cur]),判断跟str[i-1]是否相等

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
//O(M)
vector<int> getNextArray(string str) {
int size = str.size();
if (size == 1) {
return { -1 };
}
vector<int> next(size);
next[0] = -1;
next[1] = 0;
int i = 2;//当前要求next数组位置
int cur = 0;//跟i位置比较的位置,0:next[1]=0(cur=next[i-1])
while (i < size) {
if (str[i - 1] == str[cur]) {
//next[i] = cur + 1;//next[i-1]+1
//i++;
//cur = cur + 1;
next[i++] = ++cur;
}
else if (cur > 0) {
cur = next[cur];
}
else {
next[i++] = 0;
}
}
return next;
}
//str1长N,str2长M,N>=M
//时间复杂度:O(N)
int KMP(string str1, string str2) {
if (str1.empty() || str2.empty() || str1.size() < str2.size()) {
return -1;
}
vector<int> next = getNextArray(str2);//O(M)
int ptr1 = 0, ptr2 = 0;
//O(N)
while (ptr1 < str1.size() && ptr2 < str2.size()) {
if (str1[ptr1] == str2[ptr2]) {
ptr1++;
ptr2++;
}
else if (ptr2 == 0) {//相当于next[ptr2]=-1
//str2[ptr2]!=str1[ptr1],str1第一个都不匹配
ptr1++;
}
else {
ptr2 = next[ptr2];
}
}
//ptr1越界—-1,ptr2越界—匹配完成
return ptr2 == str2.size() ? ptr1 - ptr2 : -1;
}
int main() {
string str1 = "abcd1234";
string str2 = "1234";
string str3 = "1234e";
cout << KMP(str1, str2) << endl;
cout << KMP(str1, str3);
}

哈希函数和哈希表

哈希函数的特点

  1. 一般情况下,输入域无穷,输出域有限

  2. 相同的输入参数,一定会返回相同的值(内部不随机)

  3. 因为输出域可能小于输入域,所以不同输入可能有相同输出(def:哈希碰撞)

  4. 离散性:即便输入参数有一点点不一样,输出的值也有可能不一样

    均匀性:假设输出域为S,很多个输入,映射到输出域,在输出域内任意选择一块区域,选中的输出点个数几乎一样

    假设输入:in1,in2,in3……

    输出为:out1,out2,ou3……

    如果输出为均匀的,那么将输出值%m之后,结果在0~m-1上也是均匀的

例1:小内存返回大文件中出现次数最多的

一个文件存放无符号整数,总共有40亿个,只有1G内存,返回出现次数最大的数

Q:使用简单的哈希,有可能出现内存不足

​ 因为一条记录<int,int>至少占用8字节,则40亿数的哈希表至少占32G

解法:

40亿数—>哈希函数—>%100—>0~99 (哈希函数的作用:使数据均匀分布)

相当于把一个40亿的大文件划分为100个小文件,由于哈希函数的均匀性,所以哈希值再取模以后一定是均匀分布在0~99

再依次读取小文件,建立每个小文件的哈希表,因为是均匀分布的,所以一个小文件的哈希表大小=32G/100

哈希碰撞的解决方案:

  1. 链表式解决

  2. 开放寻址法

    1. 线性探测法:碰撞发生时,元素存储位置+1直到找到未占用位置

      ——>问题:导致“二次聚集”:不同基地址的元素争夺同一个位置

    2. 平方探测法:为了避免上述问题,重新寻址时,位置+1,+4……+(冲突次数)^2

  3. 再哈希法

    遇到位置被占用,对该位置进行再次哈希,循环直到找到未占用的位置

    注意:控制再哈希的次数阈值,不然可能出现无限循环的情况,导致查找元素时无法确定边界,即不知道进行几次哈希才算找不到元素

哈希表的实现

先进行哈希,再模一个数确定放在哪个桶里

当单向链表过于长时,影响查找效率,对哈希表进行扩容——>哈希表大小变为原来两倍,则单向链表长度变为原来一半(哈希函数的均匀性)

布隆过滤器

问题:黑名单问题

要求一个集合:增加和查询,不需要删除操作,且允许一定失误率(这种失误指的是把白误报成黑,不会出现把黑误报成白)——宁可错杀,不可放过

布隆过滤器:减少内存空间,但带来了一定的失误率

位图

——bit类型的数组

实现方式:拿基础类型拼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int *arr = new int[10];//4*8*10=320bits
//arr[0]——int[]0~31
//arr[1]——int[]32~63

int i = 178;//取得178bit的信息:0/1
//定位
int numIdx = i / 32;
int bitIdx = i % 32;

//取得i位置的信息
//为什么是32,因为1个int是32bit
int status = ((arr[numIdx] >> bitIdx) & 1);
int bit = (arr[i / 32] >> (i % 32)) & 1;

//将状态改为1
arr[numIdx] = arr[numIdx] | (1 << bitIdx);

//将状态改为0
arr[numIdx] = arr[numIdx] & (~(1 << bitIdx));

布隆过滤器的实现

(1)黑名单的建立

准备一个大的位图长为m,k个哈希函数

url1—f1—>m1 m1位置涂黑

​ —f2—>m2 …… —fk—>mk ===>m1,m2,……mk位置涂黑

…… …… ……

urln===>k个位置涂黑

ps:白的描黑,黑的别管

黑名单建立完毕

(2)黑名单的查找

比如说要查找urlx ===》 经过k个哈希函数再%m得到k个位置

如果这k个位置都为黑,则输出urlx属于黑名单

为什么黑不会报为白?只要urlx是黑的,则k个位置一定是黑的,报为黑名单

有可能白报为黑?例如m值很小,有可能位图全黑,误报率增加

(3)失误率的决定因素
  1. 主要因素:m值

    m太小,导致黑名单建立过程中都被涂黑了,失误率提高

  2. 第二个因素:k值

    相当于一个样本采k个特征点,所以一定程度上,k值越大,误报率越低

    但如果k值太大,同样会导致位图上涂黑的地方过多,提高误报率

    所以,先选取合适的m值,再根据m值选取合适的k值来降低误报率

(4)布隆过滤器参数选择
  1. 确定模型:是不是类似于黑名单问题,只需要添加和查询,不需要删除操作

  2. 确定是否允许失误率

  3. 布隆过滤器的设计只跟两个因素有关:n=样本量,p=失误率

    注意:跟单样本的大小没关系,因为放到布隆过滤器的值是哈希之后再模的,所以只需要保证单样本的大小属于哈希函数的输入范围

    结果都向上取整
    $$
    m=-\frac {n\ln p} {(\ln 2)^2}\
    k=\ln 2
    \frac {m}{n}\approx0.7*\frac {m}{n}
    $$
    上述取到的是理论值。

    由实际的m,k值可得到实际的失误率p
    $$
    p=(1-e^{-\frac {(n*k)}{m}})^k
    $$

一致性哈希

分布式服务器

假设有三台数据库服务器m1 m2 m3

data1——哈希 %3——m1 数据1放在m1里

…… …… ……

负载问题:如果有的数据高频,有的数据低频,导致服务器负载不均衡

哈希key的选择

===》题外话:哈希key的选择

​ 可以:身份证、人名

​ 不可以:国家名、性别

——》高频、中频、低频都有数量——》三台服务器负载均衡

例:以性别为哈希key会导致两台服务器在工作,另一台服务器负载为0

一致性哈希

下一个问题:

这种服务器选择方式——data==》哈希==》%服务器数量==》数据存放位置

带来问题:当增加服务器或者减少服务器,数据迁移是全量的,也就是说所有数据都要重新计算哈希值再模运算

解决====》一致性哈希

例:某种哈希算法得到的哈希值取值范围形成一个环0~x,数据得到的哈希值打在环上

计算机器的哈希值:m1 m2 m3 m4

image-20240621170814015

数据存储:数据==哈希==》data ——》插在环上,顺时针最近的就是数据存储的数据库,例如:data1放在m2上

所以在逻辑服务器上:m1 [c , 0] m2 [0 , a] m3 [a , b] m4 [b , c]

所以在逻辑服务器上存储:0 a b c,插入数据data=》计算哈希值datam=》通过二分查找找到>datam最左边的数==》找到存储位置

  • 数据库增加,例如:增加m4,原来[b , 0]归m1管,现在分一部分[b , c]给m4管,所以只需要重新计算m1上的数据的哈希值
  • 数据库减少,例如:减少m4,只需要把m4上的数据放到m1上就行

===》问题:当机器数量较少时,服务器分布是不均匀的也会导致负载不均衡的情况

虚拟结点

解决办法:虚拟结点

m1:a1,a2……a1000

m2:b1,b2……b1000

m3:c1,c2……c1000

实际上去抢环的是虚拟结点,数量多==》环上有3000个点==》数据分布均衡

数据选择存放在哪个点——》存放在哪台服务器上

并且,这种方式还可以管理负载:比如,实际服务器a性能号,b性能差===>给a分配2000个虚拟结点,b分配500个虚拟结点

[TOC]

1. C++11 Thead线程库的基本使用

进程与线程

  • 进程:运行中的程序
  • 线程:进程中的进程

本文详细介绍C++11 Thead线程库的基本使用,包括如何创建线程、启动线程、等待线程完成以及如何分离线程等。

1. 创建线程

要创建线程,我们需要一个可调用的函数或函数对象,作为线程的入口点。在C++11中,我们可以使用函数指针、函数对象或lambda表达式来实现。创建线程的基本语法如下:

1
2
#include <thread>
thread t(function_name, args...);

function_name是线程入口点的函数或可调用对象

args...是传递给函数的参数

测试代码:

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <thread>
using namespace std;
void printHello() {
cout << "hello" << endl;
}
int main() {
//创建线程
thread thread1(printHello);
return 0;
}

报错:

image-20240605121651420

原因:还没等线程执行完就return了


2. 主程序等待线程执行完毕

创建线程后,我们可以使用t.join()等待线程完成,或者使用t.detach()分离线程,让它在后台运行。

1
thread1.join();

加上这一句,程序会检查线程是否执行结束,就不会报错了


3.传递参数

我们可以使用多种方式向线程传递参数,例如使用函数参数、全局变量、引用等。如:

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>
using namespace std;

void printHello(string msg) {
cout << msg << endl;
}

void increment(int& x){
++x;
}
int main() {
//值传递
thread thread1(printHello,"hello");
thread1.join();
int x = 0;
//引用传递
thread t2(increment, ref(x));
t2.join();
cout << x << endl;
return 0;
}

在第一个例子中,我们使用了一个字符串作为函数参数,传递给线程。在第二个例子中,我们使用了一个引用来传递一个整数变量。需要注意的是,当我们使用引用传递参数时,我们需要使用std::ref来包装引用,否则编译器会报错。


4.分离线程

detach():用的不多,用这个即使线程没有执行完,主程序结束也不会报错

有时候我们可能不需要等待线程完成,而是希望它在后台运行。这时候我们可以使用t.detach()方法来分离线程。

需要注意的是,一旦线程被分离,就不能再使用t.join()方法等待它完成。而且,我们需要确保线程不会在主线程结束前退出,否则可能会导致未定义行为。


5. joinable()

joinable()方法返回一个布尔值,如果线程可以被join()或detach(),则返回true,否则返回false。如果我们试图对一个不可加入的线程调用join()detach(),则会抛出一个std::system_error异常。

所以严谨的做法,在使用join前面要使用joinable()进行判断

下面是一个使用joinable()方法的例子:

1
2
3
if (t.joinable()) {
t.join();
}

2. 线程函数中的数据未定义错误

1. 传递引用变量

1
2
3
4
5
6
7
8
void increment(int& x){ 
++x;
}
int main() {
thread thread1(increment,1);
thread1.join();
return 0;
}

报错:image-20240605123357864

因为函数参数是引用类型,所以使用ref来传递引用变量

1
2
int a=1;
thread t1(increment,ref(a));

2. 传递指针或引用指向局部变量的问题

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <thread>
using namespace std;
thread thread1;
void increment(int& x){
++x;
}
void test() {
int a = 1;
//a是局部变量
thread1 = thread(increment, ref(a));
}
int main() {
test();
thread1.join();
return 0;
}

a是局部变量,这样会导致在线程函数执行时,指向局部变量a的指针已经被销毁,从而导致未定义行为。


3. 传递指针或引用指向已释放的内存的问题

1
2
3
4
5
6
7
8
9
10
void print(int *x){ 
cout << *x << endl;
}
int main() {
int* ptr = new int(1);
thread thread1 = thread(print, ptr);
delete ptr;
thread1.join();
return 0;
}

线程还没有执行完,就把ptr释放了,会报错

将类对象传入函数,线程还没执行完就释放对象也会有同样的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <thread>
using namespace std;
class A {
public:
void f() {
cout << "hello" << endl;
}
};
int main() {
A a;
thread t(&A::f, &a);//注意这个的写法
t.join();
return 0;
}

解决:通过智能指针

1
2
shared_ptr<A> a = make_shared<A>();
thread t(&A::f, a);

4. 入口函数为类的私有成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
class A {
private:
void f() {
cout << "hello" << endl;
}
};
int main() {
//指向类A的一个指针
shared_ptr<A> a = make_shared<A>();
thread t(&A::f, a);
t.join();
return 0;
}

f()是类A的私有函数,不可访问

解决方法:使用友元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class A {
private:
friend void thread_f();
void f() {
cout << "hello" << endl;
}
};
//要使用类A的私有函数,需要在类A里生命声明它是友元
void thread_f() {
shared_ptr<A> a = make_shared<A>();
thread t(&A::f, a);
t.join();
}
int main() {
thread_f();
return 0;
}

3. 互斥量解决多数据共享的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a = 0;
void func() {
for (int i = 0; i < 10000; i++) {
a++;
}
}
int main() {
thread thread1(func);
thread thread2(func);
thread1.join();
thread2.join();
cout << a << endl;
return 0;
}

两个线程同时对a进行操作,最后结果可能不等于20000,而是任何小于等于20000的可能值

解决方法:上锁

1
2
3
4
5
6
7
8
9
#include <mutex>
mutex mtx;
void func() {
for (int i = 0; i < 10000; i++) {
mtx.lock();//当访问a的时候对a进行加锁,其他线程无法访问a
a++;
mtx.unlock();//访问结束进行解锁,其他线程又可以访问a
}
}

线程安全:如果多线程程序每一次运行的结果和单线程程序的结果始终是一样的,那么这个线程就是安全的

4. 互斥量死锁

假设有两个线程 T1 和 T2,它们需要对两个互斥量 mtx1 和 mtx2 进行访问,而且需要按照以下顺序获取互斥量的所有权:

  • T1 先获取 mtx1 的所有权,再获取 mtx2 的所有权。

  • T2 先获取 mtx2 的所有权,再获取 mtx1 的所有权。

如果两个线程同时执行,就会出现死锁问题。因为 T1 获取了 mtx1 的所有权,但是无法获取 mtx2 的所有权,而 T2 获取了 mtx2 的所有权,但是无法获取 mtx1 的所有权,两个线程互相等待对方释放互斥量,导致死锁。

测试代码:

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
#include <iostream>
#include <thread>
#include <mutex>
using namespace std;
mutex mtx1;
mutex mtx2;
void func1() {
for (int i = 0; i < 10000; i++) {
mtx1.lock();
mtx2.lock();
mtx1.unlock();
mtx2.unlock();
}
}

void func2() {
for (int i = 0; i < 10000; i++) {
mtx2.lock();
mtx1.lock();
mtx2.unlock();
mtx1.unlock();
}
}
int main() {
thread thread1(func1);
thread thread2(func2);
thread1.join();
thread2.join();
return 0;
}

结果:程序卡死了

解决方法:改变死锁顺序,保证获取死锁的顺序是一样的,比如说都先获取mtx1,再获取mtx2,就不会卡住了

5. lock_guard 与 unique_lock


lock_guard

lock_guard 是 C++ 标准库中的一种互斥量封装类,用于保护共享数据,防止多个线程同时访问同一资源而导致的数据竞争问题。

lock_guard 的特点如下:

  • 当构造函数被调用时,该互斥量会被自动锁定。
  • 当析构函数被调用时,该互斥量会被自动解锁。
  • lock_guard 对象不能复制或移动,因此它只能在局部作用域中使用。
1
2
3
4
5
6
7
mutex mtx;
void func() {
for (int i = 0; i < 10000; i++) {
lock_guard<mutex> lg(mtx);//离开作用域的时候析构,自动解锁
a++;
}
}

lock_guard 的实现

  1. 构造函数内进行加锁,析构函数内进行解锁

  2. 禁用了拷贝构造和赋值构造,所以不能复制和移动

    image-20240605131332588


unique_lock

unique_lock 是 C++ 标准库中提供的一个互斥量封装类,用于在多线程程序中对互斥量进行加锁和解锁操作。它的主要特点是可以对互斥量进行更加灵活的管理,包括延迟加锁、条件变量、超时等。

unique_lock 提供了以下几个成员函数:

  • lock():尝试对互斥量进行加锁操作,如果当前互斥量已经被其他线程持有,则当前线程会被阻塞,直到互斥量被成功加锁。
  • try_lock():尝试对互斥量进行加锁操作,如果当前互斥量已经被其他线程持有,则函数立即返回 false,否则返回 true
  • try_lock_for(const std::chrono::duration<Rep, Period>& rel_time):尝试对互斥量进行加锁操作,如果当前互斥量已经被其他线程持有,则当前线程会被阻塞,直到互斥量被成功加锁,或者超过了指定的时间。
  • try_lock_until(const std::chrono::time_point<Clock, Duration>& abs_time):尝试对互斥量进行加锁操作,如果当前互斥量已经被其他线程持有,则当前线程会被阻塞,直到互斥量被成功加锁,或者超过了指定的时间点。
  • unlock():对互斥量进行解锁操作。
1
2
3
4
5
unique_lock<mutex> lg(mtx);//自动完成加锁
============================================================
//延迟加锁,传入一个参数,此时解锁还是自动完成
unique_lock<mutex> lg(mtx,defer_lock);//defer_lock
lg.lock();//后面自己手动加速

不自动加锁的原因:自己加锁可以有更多的加锁方案

比如:try_lock_for(const std::chrono::duration<Rep, Period>& rel_time)。其他互斥锁获取不到锁就阻塞在这里,而try_lock_for是只会等待一段时间,还没有获取锁就跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <thread>
#include <mutex>
using namespace std;
int a = 0;
timed_mutex mtx;//mutex不支持对时间的操作,所以这里使用时间锁
void func() {
for (int i = 0; i < 2; i++) {
unique_lock<timed_mutex> lg(mtx,defer_lock);
if (lg.try_lock_for(chrono::seconds(2))) {
this_thread::sleep_for(chrono::seconds(1));
a++;
}
}
}
int main() {
thread thread1(func);
thread thread2(func);
thread1.join();
thread2.join();
cout << a << endl;
return 0;
}

运行结果:3

原因解释(一种可能情况):

thread1先拿到锁(a++),thread2等待1s;thread1释放锁,下一个又是thread1拿到锁(a++),则thread2等待2s就不等了,进入下一次循环拿到锁了,执行a++。所以结果:a=3

6. call_once及其使用场景

单例设计模式是一种常见的设计模式,用于确保某个类只能创建一个实例。由于单例实例是全局唯一的,因此在多线程环境中使用单例模式时,需要考虑线程安全的问题。

下面是一个简单的单例模式日志类的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <thread>
#include <mutex>
using namespace std;
class Log {
private:
Log(){}
public:
Log(const Log& log) = delete;
Log& operator=(const Log& log) = delete;
static Log& GetInstance() {
static Log* log = NULL;
if (!log) log = new Log();
return *log;
}
void print(string msg) {
cout << msg << endl;
}
};
int main() {
Log::GetInstance().print("hello");
return 0;
}

在这个单例类中,我们使用了一个静态成员函数 getInstance() 来获取单例实例,该函数使用了一个静态局部变量 log 来存储单例实例。由于静态局部变量只会被初始化一次,因此该实现可以确保单例实例只会被创建一次。

但是,该实现并不是线程安全的。如果多个线程同时调用 getInstance() 函数,可能会导致多个对象被创建,从而违反了单例模式的要求。

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
class Log {
private:
Log(){
cout<<"I am here"<<endl;
}
public:
Log(const Log& log) = delete;
Log& operator=(const Log& log) = delete;
static Log& GetInstance() {
static Log* log = NULL;
//例如t1先进来log为空,创建完log之后,还没来得及把值赋给log
//导致log已创建,但是log仍等于null
//此时t2进来了,发现log为空又创建一次log
//不符合单例模式的要求
if (!log) log = new Log();
return *log;
}
void print(string msg) {
cout << msg << endl;
}
};
void printError() {
Log::GetInstance().print("error");
}
int main() {
thread t1(printError);
thread t2(printError);
t1.join();
t2.join();
return 0;
}

运行结果:image-20240605135337140

显然是有错误的

为了解决这些问题,我们可以使用 std::call_once 来实现一次性初始化,从而确保单例实例只会被创建一次。下面是一个使用 std::call_once 的单例实现:

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>
using namespace std;
static once_flag once;
class Log {
private:
Log(){
cout << "I am here" << endl;
}
static Log* log;
public:
Log(const Log& log) = delete;
Log& operator=(const Log& log) = delete;

static void init() {
if (!log) log = new Log();
}

static Log& GetInstance() {
call_once(once, init);
return *log;
}

void print(string msg) {
cout << msg << endl;
}
};
Log *Log::log = NULL;

void printError() {
Log::GetInstance().print("error");
}
int main() {
thread t1(printError);
thread t2(printError);
t1.join();
t2.join();
return 0;
}

运行结果:image-20240605135435435

使用 call_once 可以确保单例实例只会被创建一次,从而避免了多个对象被创建的问题。

call_once 是 C++11 标准库中的一个函数,用于确保某个函数只会被调用一次。其函数原型如下:

使用 call_once 可以在多线程环境中实现一次性初始化,避免了多个线程同时初始化的问题。例如,在单例模式中,可以使用 call_once 来保证单例实例只会被创建一次。

7. condition_variable 与其使用场景

std::condition_variable 的使用:

  1. 创建一个 condition_variable 对象。

  2. 创建一个互斥锁 mutex 对象,用来保护共享资源的访问。

  3. 在需要等待条件变量的地方

    使用 unique_lock<mutex> 对象锁定互斥锁

    并调用 condition_variable::wait()condition_variable::wait_for()condition_variable::wait_until() 函数等待条件变量。

  4. 在其他线程中需要通知等待的线程时,调用 condition_variable::notify_one()condition_variable::notify_all() 函数通知等待的线程。

生产者消费者模型

  • 任务队列
  • 生产者:负责往任务队列加任务
  • 消费者:负责往任务队列取任务
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
using namespace std;
queue<int> que;
condition_variable cv;
//负责往队列加任务
void Producer() {
for (int i = 0; i < 10; i++) {
que.push(i);
}
}
//负责从队列里取任务
void Consumer() {
while (1) {
int value = que.front();
que.pop();
}
}

问题:consumer取任务的同时,producer有可能正在放任务,所以要加速

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
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
using namespace std;
queue<int> que;
condition_variable cv;//条件变量
mutex mtx;
//负责往队列加任务
void Producer() {
for (int i = 0; i < 10; i++) {
{
unique_lock<mutex> lock(mtx);
que.push(i);
//通知消费者来取任务
cv.notify_one();//通知一个线程来取任务
cout << "Producer : " << i << endl;
}
this_thread::sleep_for(chrono::microseconds(100));
}
}
//负责从队列里取任务
void Consumer() {
while (1) {
unique_lock<mutex> lock(mtx);
//如果队列为空,就要等待
cv.wait(lock, []() {
return !que.empty();
});//如果第二个参数为false,阻塞在这里
int value = que.front();
que.pop();
cout << "Consumer : " << value << endl;
}
}
int main() {
thread t1(Producer);
thread t2(Consumer);
t1.join();
t2.join();
return 0;
}

分成两个项目:服务端和客户端,完整源码在最后

服务端

  1. 包含相关的库文件

    1
    2
    3
    #include <stdio.h>
    #include <WinSock2.h>//windows网络通讯头文件
    #pragma comment(lib,"ws2_32.lib")//一个库文件(windows不开源) ws2_32,提供接口
  2. 开启网络权限

    1
    2
    WSADATA wsaData;
    WSAStartup(MAKEWORD(2, 2), &wsaData);
  3. 创建socket套接字

    先看一下socket的数据结构

    1
    2
    3
    4
    5
    socket(
    _In_ int af, //协议地址族 AF_INET/AF_INET6 ipv4/ipv6
    _In_ int type, //协议类型 TCP/UDP SOCK_STREAM/SOCK_DGRAM
    _In_ int protocol //保护方式
    );

    创建socket,如果创建失败,socket值为-1

    1
    2
    3
    4
    5
    6
    7
    //创建socket
    SOCKET server_socket = socket(AF_INET, SOCK_STREAM, 0);//如果创建失败为-1
    //进行检查
    if (server_socket == -1) {
    printf("server socket create failed!Error Code:%d\n", GetLastError());
    exit(-1);
    }
  4. 指定ip和端口号

    先来看一下struct sockaddr_in的数据结构

    1
    2
    3
    4
    5
    6
    7
    typedef struct sockaddr_in {
    short sin_family;//协议地址族
    USHORT sin_port;//端口号 5000+
    IN_ADDR sin_addr;//服务端,所有网卡都要监测,所以一般为0.0.0.0
    //inet_addr()——将点分十进制的IP地址转换为整数
    CHAR sin_zero[8];//保留位置 可能将来升级协议可能会用
    } SOCKADDR_IN, * PSOCKADDR_IN;

    这里涉及到大端序和小端序的内容

    • 大端序:数字大的在前面 比如:百 十 个

    • 小端序:数字小的在前面 比如:个 十 百

    例:本地为90 1f 00 00为小端序,网络上为大端序00 00 1f 90(实际值)——8080

    htons():小端序转换为大端序 eg:htons(8080);

    1
    2
    3
    4
    struct sockaddr_in local;
    local.sin_family = AF_INET;
    local.sin_port = htons(8080);//将8080转换为大端序
    local.sin_addr.S_un.S_addr = inet_addr("0.0.0.0");
  5. 绑定socket和端口

    bind()

    1
    2
    3
    4
    5
    6
    // 绑定socket和端口
    if (bind(server_socket, (struct sockaddr*)&local, sizeof(struct sockaddr_in))
    == -1) {
    printf("bind server socket failed!Error Code:%ld\n", GetLastError());
    exit(-1);
    }
  6. 监听端口

    listen()

    1
    2
    3
    4
    5
    if (listen(server_socket, 10) == -1) {
    printf("listen server socket failed!Error Code:%ld\n", GetLastError());
    exit(-1);
    }
    printf("bind and listen success. wait client connect ...\n");
  7. 等待客户端连接

    accept():函数进行过程就是三次握手

    accept函数是阻塞函数,没有客户端连接就停在这里

    server_socket:负责传话

    返回值:一个新的socket负责通信

    1
    SOCKET client_socket = accept(server_socket, NULL, NULL);
  8. 循环处理

    可以接收消息或者发送消息,在循环内部自行定义

    recv():从通信socket上接收数据

    • 返回值为-1,表示出错
    • 返回值为0,表示正常断开
    • 返回值为正数,表示接收到了多少数据
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    while (1) {
    char buff[BUFSIZ * 4] = { 0 };//接收数据

    int ret = recv(client_socket, buff, BUFSIZ * 4, 0);
    if (ret <= 0) break;

    printf("ret:%d buff:%s\n", ret, buff);

    if (memcmp(buff, "music", strlen("music")) == 0) {
    //表示当你接收到"music",进行这部分处理
    printf("playing music\r\n");
    }
    }

客户端

  1. 包含相关的库文件

    1
    2
    3
    #include <stdio.h>
    #include <WinSock2.h>//windows网络通讯头文件
    #pragma comment(lib,"ws2_32.lib")//一个库文件(windows不开源) ws2_32,提供接口
  2. 开启网络权限

    1
    2
    WSADATA wsaData;
    WSAStartup(MAKEWORD(2, 2), &wsaData);
  3. 创建socket套接字

    跟服务端代码一样

    1
    2
    3
    4
    5
    6
    //创建socket
    SOCKET client_socket = socket(AF_INET, SOCK_STREAM, 0);
    if (client_socket == -1) {
    printf("client socket create failed!Error Code:%d\n", GetLastError());
    exit(-1);
    }
  4. 指定目标ip和端口号

    跟服务端不同的是,不是监听所有,只是针对目标ip

    1
    2
    3
    4
    5
    6
    struct sockaddr_in target;
    target.sin_family = AF_INET;
    target.sin_port = htons(8080);
    //127.0.0.1本地环回
    //或者填本机ip
    target.sin_addr.S_un.S_addr = inet_addr("127.0.0.1");
  5. 直接连接就行

    connect()

    1
    2
    3
    4
    //直接连接就行
    if (connect(client_socket, (struct sockaddr*)&target, sizeof(struct sockaddr)) == -1) {
    printf("connect server failed!Error Code:%ld\n",GetLastError());
    }
  6. 进行通信

    1
    2
    3
    4
    5
    6
    7
    8
    while (1) {
    char buff[BUFSIZ * 4] = { 0 };
    printf("please input send content:");
    scanf("%s",buff);
    int ret = send(client_socket, buff, strlen(buff), 0);
    if (ret <= 0)
    break;
    }

最后同时运行两个项目就可以了!

完整源码

服务端

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
#include <stdio.h>
#include <WinSock2.h>
#pragma comment(lib,"ws2_32.lib")

int main() {
WSADATA wsaData;
WSAStartup(MAKEWORD(2, 2), &wsaData);
//创建socket
SOCKET server_socket = socket(AF_INET, SOCK_STREAM, 0);//如果创建失败为-1
if (server_socket == -1) {
printf("server socket create failed!Error Code:%d\n", GetLastError());
exit(-1);
}

//ip地址 + 端口号
struct sockaddr_in local;
local.sin_family = AF_INET;
local.sin_port = htons(8080);//将8080转换为大端序
local.sin_addr.S_un.S_addr = inet_addr("0.0.0.0");

// 绑定socket和端口
if (bind(server_socket, (struct sockaddr*)&local, sizeof(struct sockaddr_in))
== -1) {
printf("bind server socket failed!Error Code:%ld\n", GetLastError());
exit(-1);
}

//监听这个端口
if (listen(server_socket, 10) == -1) {
printf("listen server socket failed!Error Code:%ld\n", GetLastError());
exit(-1);
}
printf("bind and listen success. wait client connect ...\n");

//等待客户端连接 accept函数在进行的过程中就是三次握手
SOCKET client_socket = accept(server_socket, NULL, NULL);

while (1) {
char buff[BUFSIZ * 4] = { 0 };
int ret = recv(client_socket, buff, BUFSIZ * 4, 0);
if (ret <= 0) break;
printf("ret:%d buff:%s\n", ret, buff);

if (memcmp(buff, "music", strlen("music")) == 0) {
printf("playing music\r\n");
}
}
return 0;
}

客户端

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
#include <stdio.h>
#include <WinSock2.h>
#pragma comment(lib,"ws2_32.lib")

int main() {
//开启网络权限
WSADATA wsaData;
WSAStartup(MAKEWORD(2, 2), &wsaData);

//创建socket
SOCKET client_socket = socket(AF_INET, SOCK_STREAM, 0);
if (client_socket == -1) {
printf("client socket create failed!Error Code:%d\n", GetLastError());
exit(-1);
}

//创建目标IP和端口
struct sockaddr_in target;
target.sin_family = AF_INET;
target.sin_port = htons(8080);
//127.0.0.1本地环回
//或者填本机ip
target.sin_addr.S_un.S_addr = inet_addr("127.0.0.1");

//直接连接就行
if (connect(client_socket, (struct sockaddr*)&target, sizeof(struct sockaddr)) == -1) {
printf("connect server failed!Error Code:%ld\n",GetLastError());
}

//发消息
while (1) {
char buff[BUFSIZ * 4] = { 0 };
printf("please input send content:");
scanf("%s",buff);
int ret = send(client_socket, buff, strlen(buff), 0);
if (ret <= 0)
break;
}

return 0;
}

单继承

1.继承的写法和权限问题

class 子类:继承方法 父类

  1. 继承方法:父类中的属性在子类中的最低权限

    权限由低到高:public protected private

    eg:class boy:public woman——woman类的属性在boy类的最低权限为public

  2. 父类的私有属性对于子类来说是不可访问的

类的访问权限有三种:

  1. public 公共权限: 可以被该类中的函数、子类的函数、其友元函数访问,也可以由该类的对象访问
  2. protected 保护权限: 可以被该类中的函数、子类的函数、以及其友元函数访问,但不能被该类的对象访问
  3. private 私有权限:只能由该类中的函数、其友元函数访问,不能被任何其他访问,该类的对象也不能访问。

三种权限的区别:

public:可以被任意实体访问
protected:只允许本类及子类的成员函数访问
private:只允许本类的成员函数访问

2.继承中构造函数的写法

子类的构造函数必须调用父类的构造函数

不想写的时候,习惯在父类中增加一个无参构造函数

如:直接Boy boy;——报错,显示是已删除的构造函数

​ 解决方法:在woman类中新增无参构造函数Woman(){}

测试代码:

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
#include <iostream>
using namespace std;
class Woman
{
public:
Woman(string name,int age):name(name),age(age){
cout<<"调用基类带参构造函数"<<endl;
}//初始化参数列表
Woman(){
cout<<"调用基类无参构造函数"<<endl;
};
void print(){
cout<<"Woman "<<name<<" "<<age<<endl;
}
protected:
string name;
int age;
};
class Boy:protected Woman//Woman类的属性在boy类的最低权限是protected
{
public:
Boy(){
cout<<"调用子类无参构造函数"<<endl;
}
//采用初始化列表的方式调用父类的构造函数
Boy(string name,int age):Woman(name,age){
cout<<"调用子类带参构造函数"<<endl;
}
void print(){
cout<<"Boy "<<name<<" "<<age<<endl;
}
protected:
//子类隐含有以下属性
//void print();
//string name;
//int age;
};
int main(){
Woman woman1;
cout<<"============================"<<endl;
Woman woman2("Amy",40);
cout<<"============================"<<endl;
Boy boy1;
cout<<"============================"<<endl;
Boy boy2("Jack",10);
cout<<"============================"<<endl;
woman2.print();
boy2.print();
};

结果:

image-20240510131814280

总结:子类构造函数一定会调用对应的父类构造函数

构造顺序和析构顺序

正常情况下,构造函数和析构函数顺序相反

测试代码:

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>
using namespace std;
class A{
public:
A(){
cout<<"A";
}
~A(){
cout<<"~A";
}
};
class B:public A{
public:
B(){
cout<<"B";
}
~B(){
cout<<"~B";
}
};
int main(){
A a;//A
B b;//AB
//~B~A~A
};

结果:

1
AAB~B~A~A

注意:有delete的时候

1
2
3
B *p=new B;
B b;
delete p;

结果:

1
2
3
ABAB~B~A~B~A
//第一个~B~A是对象p的,什么delete就结束对象的生命周期
//b的析构是因为程序结束,生命周期结束自动调用析构函数

类的继承的遗传性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class A{
public:
int a;
A(int a):a(a){}
};
class B{
public:
//int a;
int b;
B(int a,int b):A(a),b(b){}
};
class C{
public:
//int a;
//int b;
int c;
C(int a,int b,int c):B(a,b),c(c){}
};
  1. B继承A,C继承B——则C不仅包含B的属性,也包含A的属性
  2. 构造函数的写法:初始化参数列表—调用直接父类的构造函数+初始化其他属性

继承中的同名问题

父类和子类同名问题:

  1. 数据成员同名
  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
#include <iostream>
using namespace std;
class Woman
{
public:
Woman(string name,int age):name(name),age(age){}
void print(){
cout<<"Woman "<<name<<" "<<age<<endl;
}
protected:
string name;
int age;
};
class Boy:public Woman
{
public:
Boy(string name,int age,string mmName,int mmAge):name(name),age(age),Woman(mmName,mmAge){}
void print(){
//1.通常都是就近原则,调用本类的
cout<<"Boy "<<name<<" "<<age<<endl;
//2.用类名限定,调用对应类的属性
cout<<"类名限定 "<<Woman::name<<" "<< Woman::age<<endl;
}
protected:
string name;
int age;
};
int main(){
Boy coolboy("boy",18,"woman",40);
coolboy.print();//Boy boy 18 类名限定 woman 40
coolboy.Woman.print();//Woman woman 40
Woman *p=new Boy("Woman_Boy",19,"Woman",41);
p->print();//Woman WomanPtr 41
};

结果:

1
2
3
4
Boy boy 18
类名限定 woman 40
Woman woman 40
Woman WomanPtr 41

总结:

  1. 通常情况下,都是就近原则,优先调用本类的数据和方法

  2. 如果加上类名限定,则调用对应类的数据和方法

  3. 如果是指针,没有virtual的情况下,也是就近原则

  4. 特殊情况:父类指针被子类对象初始化,没有virtual的情况看类型,有virtual的情况看对象

    Woman *p=new Boy("Woman_Boy",19,"Woman",41);p->print();

    所以调用的p对应的类型Woman的函数

    注意:不允许子类指针被父类对象初始化//除非进行指针类型转换

多继承

  1. 多继承——存在两个及以上的父类
  2. 权限问题:跟单继承情况一样
  3. 构造函数写法:跟单继承也是一样的
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
#include <iostream>
using namespace std;
class Woman
{
public:
Woman(string WomanFName,string WomanSName):WomanFName(WomanFName),WomanSName(WomanSName){}
protected:
string WomanFName;//姓
string WomanSName;//名
};
class Man
{
public:
Man(string ManFName,string ManSName):ManFName(ManFName),ManSName(ManSName){}
protected:
string ManFName;
string ManSName;
};
//多继承
class Son:public Woman,public Man
{
public:
//多继承要调用多个父类的构造函数
Son(string ManFName,string ManSName,string WomanFName,string WomanSName,string SonSName)
:Man(ManFName,ManSName),Woman(WomanFName,WomanSName),SonFName(ManFName+WomanFName),SonSName(SonSName){}
void print(){
cout<<"mother:"<<WomanFName+WomanSName<<endl;
cout<<"father:"<<ManFName+ManSName<<endl;
cout<<"Son:"<<SonFName+SonSName<<endl;
}
protected:
string SonFName;
string SonSName;
};
int main(){
Son son("欧","明明","阳","丽丽","修");
son.print();
};
1
2
3
mother:阳丽丽
father:欧明明
Son:欧阳修

虚继承

菱形继承:B、C继承A,D继承B、C

存在二义性:例如A-int a;B-//int a;C-//int a;D-//int a;二义性:D的a来自谁

image-20240510145208543

解决方法一:加上类型限定

屏幕截图 2024-05-10 145254

解决方法二:使用虚继承

1
2
3
4
5
6
7
8
9
10
11
12
13
class A {
public:
int a;
A(int a) : a(a) {}
};
class B : virtual public A {
public:
B(int a) : A(a) {}
};
class C : virtual public A {
public:
C(int a) : A(a) {}
};

image-20240510150049091

image-20240510150104291

PS:几个类共享一份数据

image-20240517090644926

  • 类B和类C都虚继承自类A。虚继承意味着它们不会直接包含类A的实例,而是会包含一个指向类A的共享基类的指针(这通常被称为虚基类指针)。所以sizeof(B)=8,sizeof(C)=8
  • 类D继承了类B和类C,D需要包含B和C的所有成员,所以sizeof(D)=16

虚函数

虚函数——用virtual修饰的函数

注意:构造函数不能为虚函数

1.虚函数对类的内存的影响

image-20240510150956262

2.纯虚函数

抽象类:具有纯虚函数的类

特性:不能创建对象,但可以创建对象类型指针

image-20240510151251920

子类继承抽象类,必须实现所有的纯虚函数才能实例化。

3.虚析构函数

image-20240510151908866

结果:

1
2
3
4
父类构造函数
子类构造函数
父类析构函数
//发现没有调用子类的析构函数

解决方法:使用虚析构函数

——注意:虚函数一旦被继承,不管被继承多少次,永远为虚函数

image-20240510152117958

结果:

1
2
3
4
父类构造函数
子类构造函数
子类析构函数
父类析构函数