← 返回题目列表

AtCoder · APG4b_aj

AJ. 4.05.指针

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_ad 任务ID:3776

前一页

键指针

  • 程序中的变量保存在内存中
  • 内存就像一个巨大的数组
  • 内存中的位置通过称为地址的数字来识别
    • 与地址数组的下标对应
  • 指针是处理地址的整数类型
  • 指针的使用方法
操作 記法
指针的声明 型 *ポインタ;
获取变量的地址 &変数
访问指针指向的目标(读写) *ポインタ
对指针本身的访问 ポインタ
通过指针访问成员 ポインタ->メンバ
  • 堆内存的分配
型 *ポインタ1 = new 型;        // 1つ分の領域を確保
型 *ポインタ2 = new 型[n];     // 連続したn個分の領域を確保
  • 堆内存的释放
delete ポインタ1;   //「new 型」で確保したときに返ってきたポインタ
delete[] ポインタ2; //「new 型[n]」で確保したときに返ってきたポインタ

指针

指针用于直接操作内存。使用指针可以执行复杂的操作。完全不使用指针也可以编写程序,但在一些情况下使用指针可以更简单地编写程序,或者编写高效运行的程序。

本页说明基于3.01.整数型的内容。忘记或理解不清的人请重新阅读。

梅莫里

到目前为止,我们只是粗略说明了使用变量会消耗相应的内存,但这里将进行更详细的说明。

内存是安装在计算机上的存储装置。请在这里把它想象成一个巨大的数组。计算机按照程序的指令,在这个巨大的序列中写入或读取数值来运行。

内存以1字节(8位)为单位进行处理。这个1字节的单位是adoresu(番地)标识。 如果将地址视为与数组下标相对应,可能会更容易理解。 如果你用C++写的话 它看起来像vector<uint8_t>。

当保存8位或更多大小的数据时,将其分为8位并保存。 详细内容将详细介绍。

内存和 C++ 正如

3.01.整数型中所解释的, 根据可以处理的数字范围,有多种可用的 C++ 数字类型。 每种类型在内存中都有固定的大小。

例如,int32_t是一个 32 位整数类型,因此它将在内存中使用 32 位(4 字节)。 uint8_t类型是8位整数类型,因此它在内存中使用8位(1字节)。

sizeof 运算符

当你想知道“某种类型在内存中有多少字节”时 您可以使用sizeof(型)。

cout << sizeof(int32_t) << endl; // 4
cout << sizeof(int8_t) << endl;  // 1

指针

内存地址可以用整数值表示。 处理该整数值的类型是指针类型和指针类型变量 它被称为指针。

指针图像

下图显示了内存中地址 101 处的数字 12 以及指向它的指针。
ポインタのイメージ

指针有两个基本功能:

  • 将值写入指针指向的地址
  • 从指针指向的地址读取值

让我们看一个具体的例子。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int x = 1;
  int *p;    // int8_t型に対するポインタを定義
  p = &x;    // xのアドレスで初期化
  *p = 2;    // ポインタが指すメモリへの書き込み
  cout << x << endl;  // 2

  int y;
  y = *p;  // ポインタ経由でxの値を読み取る
  cout << y << endl;  // 2
}
実行結果
2
2

以下幻灯片逐行解释了操作。


使用指针有三种基本方法,如本例所示: 您可以使用

  • &変数获取变量的地址 使用
  • 型 *ポインタ名定义指针 使用
  • *ポインタ访问(写/读)指针指向的内存区域

相同 值得注意的是,符号*具有不同的含义。

其他功能包括地址值的加法和减法。

指针的使用方法

指针的声明

型 *ポインタ名;  // ポインタ変数の宣言

同时声明多个指针:

型 *ポインタ名1, *ポインタ名2;

更改指针的目的地

ポインタ = &変数; // 変数のアドレスでポインタを初期化
ポインタ = 別のポインタ; // 別のポインタと同じアドレスを指す

访问指针指向的目的地 通过添加

*ポインタ

*,可以对指针指向的目的地进行写入和读取。 将出现表格

型 *ポインタ和*ポインタ, 注意,前者是指针声明,后者是指针访问。

与指针相关的运算符比较复杂,所以如果你不熟悉它们,请在编写它们时一一检查它们在做什么。

访问指针指向的成员

如果指针指向一个对象, 您可以使用->运算符访问成员。 它与写 (*ポインタ).メンバ的含义相同,但可以写得更简单。

オブジェクトを指すポインタ->メンバ
具体例
#include <bits/stdc++.h>
using namespace std;

struct A {
  int data;
  void print() {
    cout << data << endl;
  }
};

int main() {
  A a = A { 1 };

  // オブジェクトaを指すポインタ
  A *p = &a;
  p->print();  // a.print()の呼び出し
  p->data = 2; // a.dataの書き換え
  p->print();
}
実行結果
1
2

指针值

我们解释了指针本身在内存中保存了一个地址(整数值)。 地址是将内存视为一个大数组时对应下标的值。

下面的程序是直接输出“指针值本身”的示例,即指针指向的地址。 请注意,如果您只写指针名称而不写

#include <bits/stdc++.h>
using namespace std;

int main() {
  uint8_t x = 1;

  uint8_t *p;
  p = &x;  // ポインタの内容をxのアドレスで初期化
  cout << p << endl;  // ポインタの内容を出力
}
実行結果(例)
0x7ffcf0483a6c

*,您将访问指针本身的值。

在上面的执行结果中,0x7ffcf0483a6c。 这是以十六进制表示的地址。如果你写成十进制140724339751532。 不需要考虑这个值本身的含义,但是在这个例子中变量x已在内存中 可以看到它被分配到地址0x7ffcf0483a6c。

关于十六进制 十进制系统使用 0 到 9 的 10 个字符来表示数字,而十六进制系统使用 16 个字符,即 0 到 9 的 10 个字符和 A 到 F 的字母表。

10進法 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
16進法 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17 18 19 1A

另外,为了清楚地表明它是一个十六进制数, 添加0x它通常表示为0x1A。 您还可以在 C++ 中使用此表示法编写整数值。

写入地址时经常使用十六进制表示法。 和cout还输出十六进制的指针地址。

比较地址值 您可以将指针与

ポインタ1 == ポインタ2
ポインタ1 != ポインタ2

==呀 请注意,类似!=进行比较,这些是比较地址值的结果。

具体例
#include <bits/stdc++.h>
using namespace std;

int main() {
  int x = 123;

  int *p = &x;  // xを指すポインタ
  int *q = &x;  // yを指すポインタ

  // アドレスの比較
  if (p == q) {
    cout << "p == q" << endl;
  } else {
    cout << "p != q" << endl;
  }
}
実行結果
p == q

栈区和堆区

我解释过,当你在C++中使用变量时,会分配相应的内存区域。

要使用变量,您需要相应地分配内存。 由于内存是有限的,因此您需要根据需要分配尽可能多的内存,并在不再需要时释放它。

这种内存管理很麻烦,但是编译器可以在某种程度上自动完成。

以下是如何分配内存的快速说明。

内存区域分类

程序使用的内存是静的領域、堆栈区域、堆区域大致可以分为三类区域。

静的領域

全局变量是从程序开始到结束都保持有效的变量,因此 它必须始终分配在内存中。

只需要在程序开始时分配,在程序结束时释放,所以 全局变量的内存分配和释放由编译器自动完成。

此时,指定放置全局变量的内存区域。静的領域。

堆栈区域

局部变量在作用域内有效,所以 在作用域开始时分配内存并在作用域结束时释放内存就足够了。

编译器还会自动分配和释放局部变量。 此时分配的内存区域为 它被称为堆栈区域它被称为

堆区域

在设计程序时,您可能想要处理一些“超出范围”的信息。 在这种情况下,使用堆区域。

虽然堆区域可以灵活使用,但程序员必须负责分配和释放它。

此外,堆区域必须通过指针读写。

堆区域适用于您想要有效使用内存的情况。 如果不需要有效使用内存,通常提前分配所需的内存作为全局变量就足够了。

堆内存的分配

您可以按如下方式为堆区域分配内存。

型 *ポインタ1 = new 型;        // 1つ分の領域を確保
型 *ポインタ2 = new 型(引数);   // 1つ分の領域を確保(コンストラクタに引数を渡す)
型 *ポインタ3 = new 型[n];     // 連続したn個分の領域を確保

你可以通过“保留n个连续区域”将其视为数组。

从堆区域分配的内存将保留到程序终止,除非显式释放它。

释放内存: 使用

delete ポインタ1;   //「new 型」や「new 型()」で確保したときに返ってきたポインタ
delete[] ポインタ3; //「new 型[n]」で確保したときに返ってきたポインタ

new 型[n]分配的内存delete ポインタ或 对于指向显式分配区域以外的区域的指针delete不要这样做。

下面的示例是不需要使用堆区域的情况,但请参阅它作为如何使用它的示例。

确保一个区域的示例
#include <bits/stdc++.h>
using namespace std;

int main() {
  uint32_t *p;

  // uint32_t型の変数の分だけヒープ領域からメモリを確保する
  p = new uint32_t;

  // ポインタを介して使う
  *p = 123;
  cout << *p << endl;

  // メモリを解放する
  delete p;
}
実行結果
123
确保连续区域的示例
#include <bits/stdc++.h>
using namespace std;

int main() {
  uint32_t *p;

  // uint32_t型の変数10個分だけ(つまり4*10=40バイト分)ヒープ領域からメモリを確保する
  p = new uint32_t[10];

  // ポインタを介して使う
  uint32_t *tmp = p;  // アドレス値のコピー
  for (int i = 0; i < 10; i++) {
    *tmp = i; // i番目にiを書き込む
    tmp++; // 次の要素を指すように変更
  }

  tmp = p;  // pの位置に戻す
  for (int i = 0; i < 10; i++) {
    cout << *tmp << endl;
    tmp++;
  }

  // メモリを解放する(10個分連続で確保したのでdelete[]を使う)
  delete[] p;
}
実行結果
0
1
2
3
4
5
6
7
8
9

注意点

内存访问限制

是否可以通过指针向任何位置写入或读取值?那不是真的。 基本上,您应该只访问“为变量分配的内存区域”或“显式分配的内存区域”。 尝试强行写入或读取混乱的地址将导致意外行为。

在编写处理指针的程序时,必须始终小心,不要访问未经授权的内存区域。 从这个意义上来说,处理指针的程序可以说是困难的。


详情

在指针的声明中*位置

在指针的声明中*的位置可以是以下任意位置。

型 *ポインタ名
型* ポインタ名
型 * ポインタ名

您可以使用其中任何一个,但它们应该在整个程序中保持一致。

声明多个指针时,每个指针 为了更容易理解*是必需的,APG4b 使用第一种表示法。

空指针

指示指针尚未初始化或未指向有效地址。 作为特殊值 可以使用nullptr。nullptr通常表示 0。

指针是 要检查它是否不是nullptr,您可以编写:

if (ポインタ) {
  (nullptrでないとき)
} else {
  (nullptrのとき)
}
例
#include <bits/stdc++.h>
using namespace std;

int main() {
  uint8_t x = 1;
  uint8_t *p = nullptr;  // 初期値として nullptr を使う
  p = &x;
  *p = 2;
  p = nullptr;  // 使い終わったポインタには nullptr を入れておく
  cout << (int)x << endl;  // 2

  if (p) {
    cout << "not nullptr" << endl;
  } else {
    cout << "nullptr" << endl;
  }
}
実行結果
2
nullptr

多字节变量

大于1字节的数据被分成多个字节并保存。

例如,考虑存储数字 12345。 这个数字是不适合1字节(0~255)范围内的数据,所以 我们把它分成数字“57”和“48”,并保存在2个字节中。 那么你可以恢复原来的值57 + 48 * 256 = 12345。

当像这样跨多个字节保存值时, 如何划分是由计算机、编译器等环境决定的。 对于那些想了解更多的人字节序 请使用关键字搜索。

地址值的加法和减法

通过对指针(其自身值)进行加法和减法,可以获得“指向移动了该量的位置的指针”。 当连续分配内存并像数组一样使用它时,指针的加法和减法非常有用。

下面的程序是为10个int类型的元素分配内存并按顺序访问它们的示例。

#include <bits/stdc++.h>
using namespace std;

int main() {
  // int型10要素分をヒープ領域から確保(先頭のアドレスがpに入っている)
  int *p = new int[10];
  int *q = nullptr;

  for (int i = 0; i < 10; i++) {
    q = p + i;  // i番目の要素のポインタを取得
    *q = i;  // q の指す位置に i を書き込む
  }

  q = p;
  for (int i = 0; i < 10; i++) {
    cout << *q << endl;
    q++; // q = q + 1と同じ意味(次の要素を指すポインタに変更)
  }

  delete[] p;  // メモリ解放
}
実行結果
0
1
2
3
4
5
6
7
8
9

更准确地说,T类型的指针 对于p如果你写p + d, p的地址d地址前进一个元素(即sizeof(T)字节目标地址)。

与引用和迭代器的关系

C++ 中的引用和迭代器是旨在使指针更易于处理的功能。

下面是使用指针作为引用或迭代器的示例。 不需要实际使用指针来执行这种处理。

用作参考的示例

#include <bits/stdc++.h>
using namespace std;

void f(int &ref) {
  ref = 2;
}

// ポインタを用いた参照渡し
void g(int *ptr) {
  *ptr = 2;
}

int main() {
  int x = 1;
  f(x);  // 参照渡し
  cout << x << endl;

  int y = 1;
  g(&y);  // yのアドレスを渡す
  cout << y << endl;
}
実行結果
2
2

用作迭代器的示例

#include <bits/stdc++.h>
using namespace std;

int main() {
  // イテレータを用いて順番にアクセス
  vector<int> a = { 1, 2, 3 };
  for (auto it = a.begin(); it != a.end(); it++) {
    cout << *it << endl;
  }

  // ポインタを用いて順番にアクセス
  vector<int> b = { 1, 2, 3 };
  // b.data() ... bのデータの先頭アドレスを返す(&b[0] と同じ)
  int *begin_addr = b.data();
  for (int *ptr = begin_addr; ptr < begin_addr + 3; ptr = ptr + 1) {
    cout << *ptr << endl;
  }
}
実行結果
1
2
3
1
2
3

空指针 有一种特殊的指针类型称为

void *。 指向 void 的指针可以处理任何指针值。

指向 void 的指针无法访问它所指向的点。 您必须将其转换为原始指针类型才能访问它。

编译器不会检查原始指针类型是什么,所以 在处理 void 指针时,程序员必须负责管理原始类型。

下面是将指向各种对象的指针放入 void 指针数组的示例。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int x = 123;
  string y = "hello";
  double z = 4.5;

  // voidポインタの配列 順番に int*, string*, double* 型のポインタ
  vector<void *> ptrs = { &x, &y, &z };

  int *xp = (int *)ptrs[0];
  string *yp = (string *)ptrs[1];
  double *zp = (double *)ptrs[2];
  cout << *xp << endl;
  cout << *yp << endl;
  cout << *zp << endl;
}
実行結果
123
hello
4.5

STL容器实现

我到现在为止一直在使用它vector在内部使用指针实现。 基本上,在构造函数中分配堆内存,在那里存储元素, 执行诸如使用析构函数释放内存等操作。

如果你结合我们到目前为止所讨论的内容,事情就会很简单。 您可以实现vector,所以请尝试一下。

何时使用指针

由于指针具有引用和迭代器,因此您可能无法想到它们在 C++ 中的良好用途。

可以说,当涉及到分配堆空间时,指针才体现出其真正的价值。 因此,如果想要高效地使用内存,指针是必要的。

另外,在竞争性编程中,当表达树结构和图等数据结构时, 有时使用指针很有用。 当你第一次开始竞争性编程时,你很少需要指导。 如果您将来需要使用它,请记住这一点。

智能指针

C++ 提供了一个名为智能指针的库来安全、轻松地分配内存。

从广义上讲,智能指针有两种类型:

  • std::unique_ptr
  • std::shared_ptr

我会在这里保持简单,但如果你有兴趣,请检查一下。

std::unique_ptr交换内存的“所有权”, 当不再需要内存时,内存会自动释放。 永远是一个 归std::unique_ptr所有 没有所有权的指针无法访问目标内存区域。

例
#include <bits/stdc++.h>
using namespace std;

int main() {
  // int型1つ分の領域を確保(123で初期化)
  unique_ptr<int> p1 = make_unique<int>(123);
  *p1 += 1;
  cout << *p1 << endl;

  unique_ptr<int> p2;
  p2 = move(p1); // メモリの所有権をp2に移動
  //*p1 += 10;  // p1は所有権を失ったのでエラー
  *p2 += 1;
  cout << *p2 << endl;
}  // ここでp2の持っていた所有権が無効になり自動的にメモリが回収される
実行結果
124
125

std::shared_ptr用于多个std::shared_ptr对象共享内存所有权的模型。 这个也分享了std::shared_ptr当对象数量变为0时,目标内存将被释放。

例
#include <bits/stdc++.h>
using namespace std;

int main() {
  shared_ptr<int> p3;
  {
    shared_ptr<int> p1 = make_shared<int>(123);
    {
      shared_ptr<int> p2 = p1;  // p2も所有権を共有
      *p2 += 1;
      p3 = p2;  // p3も所有権を共有
    } // p2が所有権を手放す(p1, p3が共有している状態)
    *p1 += 1;
  } // p1が所有権を手放す(p3が持っている状態)
  *p3 += 1;
  cout << *p3 << endl;
} // 所有者がいなくなり、メモリが解放される
実行結果
126

std::shared_ptr存在一个问题,即发生循环引用时无法回收内存。 在这种情况下 使用std::weak_ptr可以避免循环引用。

您还可以使用 `const` 定义只读指针,如下所示。 wzxhzdk:39 请注意,您可以更改指针变量的值,从而更改指针。 wzxhzdk:40 #####执行结果 wzxhzdk:41 上面的程序创建了一个链表,如下图所示。 ![非连续单向列表图](https://img.atcoder.jp/APG4b-hidden/3.05.linked_list_2.png) “ListNode”结构是一种表示一个节点的结构。它保存数据和链接作为成员变量。 整个列表表示为“ListNode”数组。 print_list 函数从 head_index 指定的数据位置处的节点开始输出 data 的值,并跟踪节点,直到没有后续节点为止。 ## 使用指针实现 以下程序是使用名为“shared_ptr”的指针的示例。 `shared_ptr` 将在下一节中详细解释。 wzxhzdk:42 #####执行结果 wzxhzdk:43 在不使用指针的示例中,链接被保存为“int”类型值。 在此示例中,“shared_ptr<ListNode> next_ptr;”对应于链接。 “shared_ptr<ListNode>”是指针类型,“next_ptr”是指向下一个节点的指针。 此外,此示例实现了一个列表,但没有将节点放入数组中。 `print_list` 函数还可以通过仅使用 `shared_ptr<ListNode>` 类型的变量作为参数来遍历整个列表。 --- # 共享指针 ## 简单的例子 wzxhzdk:44 #####执行结果 wzxhzdk:45 ## 指针概念 指针可以像引用一样使用来更改引用的数据。 指针和引用在以下方面有所不同: - 您可以更改参考目的地(可能没有参考目的地) - 可以返回指向函数内创建的对象的指针 对于第一个,引用必须始终指定引用目的地,并且一旦设置了引用目的地,就无法更改。 关于第二个,我无法返回对我在函数内声明的变量的引用。 (详情请参阅[参考文献2.04](https://atcoder.jp/contests/apg4b/tasks/APG4b_u)。) 您可能会将其视为“更灵活的参考”。 虽然自由度很高,但也有一些点需要小心处理。 ##shared_ptr的声明和初始化 声明指针变量: wzxhzdk:46 要创建新对象并引用该对象,请执行以下操作: wzxhzdk:47 要从现有指针变量创建具有相同引用目标的指针变量,请执行以下操作: wzxhzdk:48 ## 空指针 没有引用的指针称为**空指针**。 如果你还没有初始化`shared_ptr`变量,它将是一个空指针。 在 C++ 中,您可以使用关键字“nullptr”来表示空指针。 wzxhzdk:49 wzxhzdk:50 ## 访问指针指向的对象 |符号|含义| |----|----| |`*指针`|访问引用的对象| |`指针->成员变量`|访问被引用对象的成员变量(与`(*pointer).成员变量`相同)| |`Pointer->Member function()`|调用被引用对象的成员函数(与`(*pointer).member function()`相同)| ## 注意事项 不要访问空指针。 导致未定义的行为。 --- # 树结构 ## 树结构概念 ## 没有指针的实现 wzxhzdk:51 ## 使用指针实现 矢量版本单向列表 共享指针 好像是一个参考 - 从功能方面进行变更的示例 - 共享指针 - make_shared shared_ptr版本单向列表 木结构 概念 实施 使用shared_ptr实现 --- # 注意事项 --- #详情 - 记忆故事(简要) - 分配内存 - 堆 - 堆栈 - 双向列表 - 唯一的_ptr - 循环引用 - 弱指针 -C指针 - 算术运算 - 内存泄漏 --- ## 练习 请在链接目的地解决问题。 提出问题:列表上的操作(大约有3个涉及指针操作的操作) ## [EX24.问题名称](https://atcoder.jp/contests/apg4b/tasks/APG4b_bw)

前一页