array

数组数据结构概述

基本概念

• 连续内存存储： 数组在内存中占用一块连续区域，每个元素的存储位置可以通过起始地址加上偏移量计算得到

  • 所以我们不能单独删除数组中的某个元素，只能覆盖，也就是移动其他元素的地址

• 下标：数组的下标是从0开始的

• 固定大小： 在大多数静态数组实现中（如 C 语言的数组、C++ 中的传统数组、Go 的数组），数组的大小在创建时就被确定，并且在运行时不能自动扩展

• 随机访问时间复杂度为 O(1)： 由于内存是连续分布的，访问任意下标的元素的时间基本相同，非常高效

• 在不同编程语言中，对于二维数组的内存管理是不一样的，C++ 中是连续的，但 Java 中则是不连续的

• 缺点：

  • 固定大小导致灵活性不足，一旦数组大小确定，无法自动增大或缩小

  • 插入和删除操作在中间位置时需要移动大量元素，效率较低

应用场景

数组常用于需要高效随机读写的场景，如算法中的静态数据存储，适用于数据量已知且变化不大的情况

在很多编程语言中，数组也常作为更复杂数据结构（例如链表、哈希表、堆）的底层存储结构之一

C++ 中数组的应用

在 C++ 中，可以使用多种方式来实现数组，这些方式大致可以分为“传统 C 风格数组”和 STL 中的容器（如 std::array 和 std::vector）

C 风格数组

声明与初始化：C 风格数组直接在栈上分配内存，语法简单但缺少边界检查

虽然效率高，直接操作内存，但大小固定且容易出现越界错误，调试时较难发现错误

例如：

# include <iostream>
using namespace std;

int main()
{
    int arr[5] = {1, 2, 3, 4, 5};  // 定义一个包含 5 个整数的数组

    for (int i = 0; i < 5; ++i)
    {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

std::array

自 C++11 引入以来，std::array 是一种封装了固定大小数组的容器，提供了更丰富的接口（如 size(), begin(), end()），并支持 STL 算法

它封装了原始数组且依然是固定大小，在编译时大小已知，更安全，接口友好

使用示例：

# include <iostream>
# include <array>

int main()
{
    std::array<int, 5> arr = {1, 2, 3, 4, 5};  // 声明并初始化数组

    for (auto elem : arr)
    {
        std::cout << elem << " ";
    }

    std::cout << std::endl;

    return 0;
}

std::vector

std::vector 是动态数组而非静态数组，它在需要动态改变数组大小的场景中非常重要，并且在底层依然采用连续内存存储

它提供了丰富的成员函数方便元素的插入、删除和其他操作，尽管底层实现与数组相似，但在扩容时需要重新分配内存和复制数据，扩容时可能影响性能

使用示例：

# include <iostream>
# include <vector>

int main()
{
    std::vector<int> vec = {1, 2, 3, 4, 5};  // 初始化 vector
    vec.push_back(6); // 动态增加元素

    for (size_t i = 0; i < vec.size(); ++i)
    {
        std::cout << vec[i] << " ";
    }

    std::cout << std::endl;

    return 0;
}

Go 语言中的数组及其衍生数据结构

Go 语言在语法上与 C 家族相似，但在数组和切片的设计上有其独到之处

固定大小的数组

在 Go 中，数组的大小是其类型的一部分，其大小固定，类型严格，例如 [5]int 和 [10]int 就是不同的类型

类似地，在 Go 中当数组被赋值或作为参数传递时，整个数组会被复制，这在某些情况下需要注意内存和性能问题

声明时指定固定大小：

package main
import "fmt"

func main() {
    var arr [5]int = [5]int{1, 2, 3, 4, 5}

    for i, v := range arr {
        fmt.Printf("arr[%d] = %d\n", i, v)
    }
}

切片（Slice）

切片是在 Go 中使用更为频繁的一个数据结构，它基于数组，但提供了动态长度的特性

切片包含三个信息：指向底层数组的指针、长度和容量

切片更灵活，能够自动扩展，但底层依然是数组，通过 append 操作，当容量不足时 Go 会自动分配更大的底层数组，并复制原有元素

切片是引用类型，多个切片可以共享同一个底层数组，因此修改其中一个切片可能会影响到其他共享相同底层数组的切片

声明与使用：

package main
import "fmt"

func main() {
    // 声明一个数组
    arr := [5]int{1, 2, 3, 4, 5}

    // 创建切片，从数组中截取部分元素
    slice := arr[1:4]  // 包含索引1到索引3的元素
    fmt.Println("slice:", slice)  // 输出: [2 3 4]

    // 使用 make 创建动态切片
    s := make([]int, 0, 10)  // 长度为0，容量为10
    s = append(s, 100)
    s = append(s, 200)
    fmt.Println("s:", s)
}

C++ 与 Go 数组的对比

内存管理与类型安全

• C++：

  • 传统 C 风格数组没有内置越界检查，容易出现错误

  • std::array 提供了类型安全和固定大小的数组，而 std::vector 则支持动态扩展

• Go：

  • 固定数组的长度是类型的一部分，易于编译器检查，但因值传递会导致数据复制

  • 切片作为动态数组，大大提高了操作便利性，同时也要注意共享底层数组带来的影响

使用场景

C++：当内存效率和操作速度为关键时，传统数组或 std::array 是不错的选择；而当需要动态改变数据量时，std::vector 是更合适的容器

Go： 虽然 Go 支持固定数组，但在实际开发中更常使用切片，因为切片的灵活性更适合大多数场景

边界检查

C++ 的传统数组和 std::vector 在访问时没有自动的边界检查（虽然可以通过 at() 方法获得检查功能）

而 Go 在切片操作时会进行边界检查，如果越界会自动抛出异常（运行时 panic）。

总结

数组作为一种基本且高效的数据结构，其主要优势在于能够以常数时间复杂度访问元素

在 C++ 中，你可以选择使用传统的 C 风格数组、std::array（适用于固定大小数据且更安全）以及 std::vector（适用于需要动态扩展的场景），每种方式都在不同场景下发挥其优势

在 Go 中，虽然支持固定大小数组，但由于数组作为值类型的特性和复制开销，切片成为了更为常用和灵活的选择，切片不仅继承了数组的高效存取特性，而且通过动态扩展机制提高了开发效率