数组
2026-07-14 21:14:50
发布于：浙江
一、数组是什么
你写一行代码：
int arr[10];
编译器就给你干了件事：去内存里找了连续的一块地方，够放10个int，然后把这块地方的起始地址记下来，跟arr这个名字绑在一起。
arr就是这块内存的名字。
以后你写arr[3]，编译器就拿着arr的地址，加上3乘以int的大小，算出第4个格子的地址，去那里读或者写。
就这么简单。
连续、定长、同类型——这三个词概括了数组的全部。
二、连续性的意义
连续不只是个概念，它直接影响性能。
CPU读内存不是读一个字节，是读一条缓存行，通常64字节。你遍历一个数组，CPU一次性把相邻的几个元素都读进缓存了，下次访问直接用缓存里的，快。
链表不是连续的，每个节点可能在内存的任意位置。你遍历链表，CPU每读一个节点都可能要重新去内存里取，缓存不命中，慢。
数组的连续性能让编译器做优化。循环展开、向量化指令，都依赖数据是连续的。编译器看到你遍历数组，能自动生成SIMD指令，一次处理多个数据。链表不行，地址是散的，编译器没法搞。
差距有多大？顺序遍历一个数组比遍历一个链表快一个数量级。不是常数倍，是量级上的差别。这就是连续性的威力。
三、索引为什么从0开始
因为索引是偏移量。
arr[0]是首地址加0，arr[1]是首地址加一个元素大小，arr[i]是首地址加i个元素大小。
如果从1开始，arr[1]是首地址加0，arr[i]是首地址加(i-1)个元素大小。每次访问多一次减法。
早期的C语言设计者很在乎这点性能。那时候机器慢，指令少，多一条减法可能就是几个百分点的差距。
这个习惯延续下来了，后面的语言都跟着C从0开始。除非是专门面向非程序员的语言，比如Lua和MATLAB，它们从1开始，因为数学家习惯从1开始数。
四、数组名到底是什么
数组名是一个表达式，它的值是数组首元素的地址。
但它不是指针变量，它是个地址常量。
int arr[10];
int* p = arr; // arr的值给了p，没问题
arr = p; // 编译错误，arr不是可修改的左值
arr在编译器眼里是一个符号，标记着一块内存的起始位置。这块内存有多大、里面装的是什么类型，编译器都知道。但arr本身不是变量，没有自己的存储空间。
所以sizeof(arr)能算出整个数组的大小，因为编译器知道arr代表的那块内存有多大。
但如果把arr传给函数，情况就变了。
五、数组退化为指针
这是初学者最容易困惑的地方。
void foo(int arr[]) {
// arr到底是什么？
}
你写int arr[]，编译器看到函数参数，直接给你改成int* arr。你写的数组语法只是个幌子，底层就是个指针。
所以函数里拿不到数组的大小。
void foo(int arr[]) {
sizeof(arr); // 指针的大小，不是数组的大小
}
为什么这么设计？因为C语言函数调用时，参数是值传递。如果要传整个数组，得把整个数组的数据全部拷贝一份压到栈上，数组大了根本扛不住。所以传的是地址，8个字节，搞定。
这个设计合理，但带来麻烦：长度丢了。
解决方式有三种。
第一种：多传一个长度参数。
void foo(int arr[], size_t len);
第二种：用模板推导引用。
template<size_t N>
void foo(int (&arr)[N]) {
// N就是数组长度
}
这种写法不传值，传引用，数组不退化为指针，类型信息保留。
第三种：用std::array或者std ::span。
void foo(std::span<int> arr);
span是C++20的东西，它拿着地址和长度，既不拥有数据也不拷贝数据，就是一个"视图"。
六、栈数组和堆数组
数组放在哪里，决定了它的生命周期、大小限制、释放方式。
栈数组
void func() {
int arr[100]; // 栈上
}
栈是每个线程一块固定大小的内存，几MB到几十MB不等。函数调用的时候，往里压一个栈帧，局部变量都在这个帧里。函数返回，栈帧弹出，局部变量随帧一起销毁。
栈数组的好处是快。分配只需要移动栈顶指针，没有任何额外开销。销毁也不需要你做任何事。
缺点是大小受限制。你写int arr[1000000]，4MB，栈可能装不下，程序直接崩溃。
还有就是生命周期固定。你没法把一个栈数组返回给调用者，函数返回它就不存在了。
堆数组
int* arr = new int[100]; // 堆上
delete[] arr;
堆是程序启动时从操作系统申请的一大块内存，由内存分配器管理。你调用new，分配器从堆里找一块空出来的地方给你，记上账，把地址返回给你。
堆数组的好处是大小灵活，只要内存够，多大都行。生命周期由你控制，你可以把它返回给调用者，可以在多个函数间传递。
坏处是慢。分配要经过分配器，可能有锁、有查找、有合并碎片。释放要你自己记得写delete，忘写了内存泄漏。
现代C++用智能指针管理堆数组：
std::unique_ptr<int[]> arr = std::make_unique<int[]>(100);
不用手动delete，arr离开作用域自动释放。
或者直接用vector，连new都不用写。
七、数组的大小和容量
对原生数组来说，大小就是容量，固定不变。
int arr[10];
// 大小是10，容量也是10，永远没法变成11
对vector来说，大小和容量是两码事。
大小是里面实际有几个元素。容量是分配了多少内存，够放几个元素。
std::vector<int> v;
v.reserve(100); // 容量100，大小0
v.push_back(1); // 容量100，大小1
v.push_back(2); // 容量100，大小2
容量大于等于大小。大小可以增加，直到追上容量。追上之后再加，就要扩容。
扩容的过程：
- 分配一块更大的内存，通常是原来的1.5倍或2倍
- 把旧内存里的元素拷贝或移动到新内存
- 释放旧内存
这个过程消耗性能。如果你提前知道大概要存多少，先reserve一下，省得扩容。
但reserve别滥用。你reserve了10000个int，只用10个，那9990个int的空间就浪费了。内存不要钱？服务器上要。
八、数组的边界
原生数组不检查边界。
int arr[5];
arr[5] = 100; // 越界，但是编译通过
arr[-1] = 200; // 负索引，编译也通过
下标只要是个整数，编译器就照算不误。arr[5]的地址是首地址加5乘以元素大小，arr[-1]是首地址减一个元素大小。往那个地址写，不管那片内存是谁的。
后果可能是：
- 覆盖了别的变量，导致逻辑错误
- 覆盖了栈上的返回地址，函数返回时崩溃
- 写到了不属于你的内存，操作系统直接杀掉进程
C为什么不检查？性能。每次访问都检查，乘以循环次数，开销可观。C的哲学是不为你不用的事情付费，你要安全自己去检查。
stdarray和stdvector的at方法检查边界，越界抛异常。operator[]不检查，跟原生数组一样快。
std::vector<int> v(5);
v[5] = 100; // 不检查，危险
v.at(5) = 100; // 检查，越界抛std::out_of_range
用哪个看场景。性能关键的地方用operator[]，安全优先的地方用at。
九、二维数组的真相
二维数组是数组的数组。
int matrix[3][4];
这句话的意思是：matrix是一个长度为3的数组，每个元素是一个长度为4的int数组。
内存布局就是12个int连续排列，先放第一个长度为4的数组，再放第二个，再放第三个。
访问matrix[i][j]，编译器算地址：
地址 = matrix起始地址 + i * 4 * sizeof(int) + j * sizeof(int)
所以二维数组本质上还是一维的，只是编译器帮你做了两层下标到偏移量的转换。
行主序是什么意思？就是上面说的，先排满一行再排下一行。C语言是行主序，Fortran是列主序。
为什么行主序影响了性能？因为CPU访问连续地址快。
// 行遍历，地址连续，快
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
sum += matrix[i][j];
}
}
// 列遍历，地址跳跃，慢
for (int j = 0; j < 4; j++) {
for (int i = 0; i < 3; i++) {
sum += matrix[i][j];
}
}
第一个循环访问顺序是[0][0]、[0][1]、[0][2]、[0][3]、[1][0]……地址连续，缓存命中率高。
第二个循环访问顺序是[0][0]、[1][0]、[2][0]、[0][1]、[1][1]……每次跳一行，缓存命中率低。
在数据量大时，两种写法的性能差距可能是几倍。
十、多维数组的vector版本
多维的vector写作：
std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));
注意：这个不是一块连续的内存。外层vector存3个内层vector，每个内层vector各自在堆上分配自己的内存。这3块内存不一定挨着。
所以matrix[1][2]的访问比原生二维数组慢一层，因为要先找到第二个内层vector，再在里面找第三个元素。
好处是每行可以有不同的长度，也就是锯齿数组。
std::vector<std::vector<int>> jagged;
jagged.push_back({1, 2});
jagged.push_back({3, 4, 5});
jagged.push_back({6});
每行长度不一样，这在原生二维数组里做不到。
如果你不需要锯齿，而且希望内存连续，用一维vector模拟二维：
std::vector<int> matrix(rows * cols);
matrix[i * cols + j] = value;
访问的时候算一下偏移。这样内存连续，访问快，而且vector管理内存，安全。
十一、数组和字符串的关系
C语言没有字符串类型，字符串就是字符数组，末尾有个'\0'。
char str[] = "hello";
这个数组长度是6，不是5。5个字符加一个'\0'。
strlen函数算的是'\0'之前的字符数，不包括'\0'。
strlen(str); // 5
sizeof(str); // 6
字符数组的坑：
char str[5] = "hello"; // 错误，没地方放'\0'
char str[5] = "hell"; // 正确，剩下一个位置放'\0'
如果没放'\0'，strlen会一直往后找，直到在内存里碰到一个0，结果不可预测。
C++有std::string，用这个，别用char数组。除非你在写底层或者跟C库交互。
十二、数组在函数间的传递
前面说了数组传参退化为指针，丢长度。这是C语言的历史包袱，C++继承下来了。
但C++提供了几种更好的方式。
方式一：std::array
void foo(std::array<int, 5> arr);
arr是值传递，拷贝了5个int。小数组没问题，大数组用引用。
void foo(const std::array<int, 5>& arr);
类型信息完整保留。
方式二：std::vector
void foo(const std::vector<int>& v);
vector自带长度，传引用不拷贝。
方式三：std::span
void foo(std::span<int> s);
span不拥有数据，只存一个指针和一个长度。vector、array、原生数组都可以转成span传进去。
std::vector<int> v = {1, 2, 3, 4};
std::array<int, 5> a = {1, 2, 3, 4, 5};
int arr[] = {1, 2, 3};
foo(v);
foo(a);
foo(arr);
同一个函数处理三种数组，而且不拷贝数据。
十三、数组与迭代器
C++的迭代器概念源自指针。
指针能做的操作：解引用、自增、自减、加减整数、比大小。迭代器就是对这些操作的抽象。
数组的指针天然满足迭代器的要求：
int arr[5] = {1, 2, 3, 4, 5};
int* begin = arr;
int* end = arr + 5;
for (int* it = begin; it != end; ++it) {
cout << *it;
}
这个循环跟vector的迭代器循环长得一模一样。因为vector的迭代器就是封装的指针。
STL里的算法都工作在迭代器上，所以算法既能用在vector上，也能用在数组上。
std::sort(arr, arr + 5);
std::sort(v.begin(), v.end());
完全一样的调用方式。这就是迭代器设计的妙处：不同的容器提供同样的接口，算法不需要知道底层是什么。
十四、数组在内存中的对齐
数组的对齐要求跟元素类型一样。
如果int是4字节对齐，那int数组首地址也4字节对齐。每个元素都4字节对齐，因为每个元素间隔正好4字节。
如果元素类型是8字节对齐的，数组首地址也8字节对齐。
所以数组里不会有内存空隙，所有元素紧挨着。
这个特性在序列化和网络传输里很有用。把整个数组当一块二进制数据直接发出去，到了对端直接解读，不用额外处理。
但要注意，如果数组里是复杂对象，指针成员指向的数据不会被序列化，只拷指针本身没用。这种时候需要深拷贝或者专门的序列化库。
十五、数组与const
int arr[5]; // 普通数组
const int arr[5]; // 元素不可修改
int* const p = arr; // 指针不可改，指向的内容可改
const int* p = arr; // 指针可改，指向的内容不可改
const int* const p = arr;// 都不可改
函数传参的时候：
void foo(const int arr[]) {
// arr指向的内容不可修改
}
void foo(int* const arr) {
// arr地址不可修改，相当于上面的写法
}
但是：
void foo(const int arr[5]) {
// 这个5编译器忽略，还是当int* const
}
写着像数组带了长度，实际上长度信息被丢弃，写成5只是给读代码的人看的。
十六、指针数组和数组指针
这两个名字容易混。
指针数组：数组里放的是指针。
int* arr[10]; // 10个int*组成的数组
每个元素是一个指向int的指针。可以用来存多个字符串：
const char* strs[] = {"hello", "world", "!"};
数组指针：指向数组的指针。
int (*p)[10]; // p指向一个长度为10的int数组
int arr[10];
p = &arr; // p指向arr
这种写法不多见，一般出现在多维数组的场合：
int matrix[3][10];
int (*p)[10] = matrix; // matrix退化为指向第一行的指针
p的类型是"指向长度为10的int数组的指针"，++p就跳到下一行。
十七、数组和指针的等价与不等价
很多人说数组和指针是等价的，这话说对了一半。
在表达式中，数组名可以当作指针用，这是等价的部分。
arr[i] == *(arr + i)
但数组和指针不是一回事。
- 数组有大小，指针没有
- 数组名是常量，指针是变量
- sizeof对数组算总大小，对指针算指针大小
- 数组不能赋值，指针可以
两者的区别在声明和定义时最明显：
// 在文件a.cpp里
int arr[10];
// 在文件b.cpp里
extern int* arr; // 错误！arr不是指针
extern int arr[]; // 正确
如果在一个文件里定义的是数组，在另一个文件里声明成指针，编译器会按指针去解释数组的内存，结果完全乱掉。
十八、从数组到容器的演变
为什么C++有了数组还要搞vector和array？
因为数组太原始了。
数组不知道自己的长度，传给函数就丢了。数组不能拷贝赋值。数组没有迭代器。数组不提供任何算法接口。
人们在使用中不断往数组上包东西，C++标准库就提供了两种封装。
std::array：固定大小，容器接口，零开销。编译之后跟原生数组一样，但用起来安全方便。
std::vector：动态大小，自动扩容，管理内存。用起来最省心，绝大多数场景用它就对了。
两个都是容器，都提供begin、end、size、at、operator[]，都支持迭代器，都能跟算法配合。
区别只在于大小是固定的还是动态的。
现代C++的建议：用std::array替代原生固定数组，用std: :vector替代原生动态数组。
原生数组什么时候还用？写嵌入式系统，没有标准库；写C接口的桥接代码；写极其讲究性能的热路径，连std::array的轻微抽象开销都不想付。
但绝大多数应用层代码，这三个场景都不沾边，就用容器。
十九、数组相关的常用算法
C++标准库提供了大量操作数组的算法，都在<algorithm>里。
排序
std::sort(v.begin(), v.end()); // 升序
std::sort(v.begin(), v.end(), std::greater<int>()); // 降序
std::stable_sort(v.begin(), v.end()); // 稳定排序
二分查找（要求数组有序）
bool found = std::binary_search(v.begin(), v.end(), 5);
auto it = std::lower_bound(v.begin(), v.end(), 5); // 第一个>=5的位置
auto it2 = std::upper_bound(v.begin(), v.end(), 5); // 第一个>5的位置
合并
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
反转
std::reverse(v.begin(), v.end());
旋转
std::rotate(v.begin(), v.begin() + 2, v.end()); // 把前两个移到末尾
去重（要求有序）
auto it = std::unique(v.begin(), v.end());
v.erase(it, v.end());
查找
auto it = std::find(v.begin(), v.end(), 42);
auto it2 = std::find_if(v.begin(), v.end(), [](int x){ return x > 10; });
计数
int count = std::count(v.begin(), v.end(), 5);
int count2 = std::count_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
最大最小
auto it = std::max_element(v.begin(), v.end());
auto it2 = std::min_element(v.begin(), v.end());
auto [min, max] = std::minmax_element(v.begin(), v.end());
这些算法不仅用于vector，也用于array和原生数组，只要提供begin和end迭代器就行。
二十、数组的底层实现
如果你写一个vector，核心就是三根指针。
template<typename T>
class MyVector {
T* begin_; // 起始位置
T* end_; // 当前最后一个元素的下一个位置
T* cap_; // 容量末尾
};
size = end_ - begin_
capacity = cap_ - begin_
push_back的时候：
if (end_ == cap_) {
// 扩容
size_t new_cap = 2 * (cap_ - begin_);
T* new_begin = new T[new_cap];
std::copy(begin_, end_, new_begin);
delete[] begin_;
begin_ = new_begin;
end_ = begin_ + old_size;
cap_ = begin_ + new_cap;
}
*end_ = value;
++end_;
这就是vector的底层。三根指针管理一块连续内存，扩容时搬移。
array更简单，连这三根指针都没有：
template<typename T, size_t N>
class MyArray {
T data_[N];
};
直接嵌入N个元素，没有额外开销。
这就是为什么array性能跟原生数组一样，因为编译出来就是原生数组。
二十一、数组与C接口
C++经常要跟C代码交互，C代码用的都是原生数组。
vector和array都提供了data方法，返回指向底层数组的指针。
std::vector<int> v = {1, 2, 3, 4, 5};
some_c_function(v.data(), v.size());
std::array<int, 5> a = {1, 2, 3, 4, 5};
some_c_function(a.data(), a.size());
原生数组直接传名字：
int arr[5] = {1, 2, 3, 4, 5};
some_c_function(arr, 5);
反过来，C函数返回的数组指针可以用vector包装：
size_t len;
int* data = some_c_function(&len);
std::vector<int> v(data, data + len);
// 如果data是malloc的，记得free
二十二、数组的现代替代
C++20引入了std::span，前面提过。它是视图，不拥有数据，替代了指针加长度的传参方式。
C++17有std::string_view，是span的字符版本，替代const char*。
C++20的std::mdspan是多维数组视图，用来替代多维指针。
这些视图类都遵循一个设计原则：只给看，不管。它们指向别人的数据，不管理生命周期，所以轻量，拷贝开销极小。
使用的时候要保证被指向的数据在视图使用期间存活，否则悬空引用。
二十三、常见错误总结
越界访问：下标超过了size-1，或者负下标。编译器不查，自己小心。
返回栈数组地址：函数返回后栈帧销毁，返回的指针指向已释放的内存。
delete和delete[]混用：new[]配delete[]，new配delete。混用未定义行为。
传参丢长度：数组传给函数退化为指针，长度丢了。用template保留长度或传size参数。
迭代器失效：vector插入或删除后，之前的迭代器可能失效。重新获取或使用索引。
浅拷贝数组：数组不能直接拷贝，用std::copy或循环手动拷。
vector扩容时的引用失效：对vector元素的引用在扩容后会失效，因为内存重新分配了。
数组指针类型错误：在不同编译单元里声明不一致，一个说数组一个说指针。
二十四、一句话总结
数组是内存里连续的一块，用索引算地址，快但原始。
原生数组留给底层，std::array留给固定大小，std: :vector留给动态大小。
能选容器的别选原生数组，除非不得已。
这里空空如也
有帮助，赞一个