C语言变长数组讲解
 
参考资料：
 1、https://www.cnblogs.com/Anker/p/3744127.html
 2、https://www.cnblogs.com/veis/p/7073076.html
 3、https://blog.csdn.net/dalerkd/article/details/69666716
 
看如下代码：
 
#include<stdio.h>
typedef struct {
    int len;
    int array[];
}SoftArray;

int main() {
    int len = 10;
    printf("The struct's size is %d\n",sizeof(SoftArray));
    return 0;
}
 
运行结果：
 
[root@VM-0-7-centos mydoc]# ./a.out 
The struct's size is 4
 
我们可以看出，_SoftArray结构体的大小是4，显然，在32位操作系统下一个int型变量大小刚好为4，也就说结构体中的数组没有占用内存。为什么会没有占用内
 
存，我们平时用数组时不时都要明确指明数组大小的吗？但这里却可以编译通过呢？这就是我们常说的动态数组，也就是变长数组。
 
先不要乱，让我们再看一段代码
 
#include<stdio.h>
#include<malloc.h>

typedef struct {
    int len;
    int array[];
}SoftArray;

int main() {
    int len = 10;
    SoftArray *p=(SoftArray*)malloc(sizeof(SoftArray) + sizeof(int)*len);
    printf("SoftArray size is %d\n", sizeof(SoftArray));
    free(p);

    return 0;
}

 
运行结果：
 
[root@VM-0-7-centos mydoc]# ./a.out 
SoftArray size is 4
 
是不是有点奇怪，为什么申请了内存后结构体大小还是4呢？原因是动态申请的内存只是申请给数组拓展所用，从上个程序我们可以看出结构体的大小在创建时已经
 
确定了，array明确来说不算是结构体成员，只是挂羊头卖狗肉而已。
 
下面我们来看看关于变长数组的资料：
 
1、什么是变长数组？
 
变长数组既数组大小待定的数组， C语言中结构体的最后一个元素可以是大小未知的数组，也就是所谓的0长度，所以我们可以用结构体来创建变长数组。
 
2、变长数组有什么用途 ？
 
它的主要用途是为了满足需要变长度的结构体，为了解决使用数组时内存的冗余和数组的越界问题。
 
3、用法 ：在一个结构体的最后 ，申明一个长度为空的数组，就可以使得这个结构体是可变长的。对于编译器来说，此时长度为0的数组并不占用空间，因为数组名
 
本身不占空间，它只是一个偏移量， 数组名这个符号本身代 表了一个不可修改的地址常量 （注意：数组名永远都不会是指针！ ），但对于这个数组的大小，我们
 
可以进行动态分配,对于编译器而言，数组名仅仅是一个符号，它不会占用任何空间，它在结构体中，只是代表了一个偏移量，代表一个不可修改的地址常量！
 
对于变长数组的这个特点，很容易构造出变成结构体，如缓冲区，数据包等等
 
typedef struct {
    int len;
    int array[];
}SoftArray;
 
这样的变长数组常用于网络通信中构造不定长数据包，不会浪费空间浪费网络流量，比如我要发送1024字节的数据，如果用定长包，假设定长包的长度为2048，就
 
会浪费1024个字节的空间，也会造成不必要的流量浪费。
 
举个简单例子。
 
#include<stdio.h>
#include<malloc.h>

typedef struct {
    int len;
    int array[];
}SoftArray;

int main() {
    int len=10, i=0;
    SoftArray *p=(SoftArray*)malloc(sizeof(SoftArray)+sizeof(int)*len);
    p->len=len;
    for(i = 0;i < p->len;i++) {
        p->array[i] = i+1;
    }
    for(i = 0;i < p->len;i++) {
        printf("%d\n", p->array[i]);
    }
    free(p);

    return 0;
}
 
运行结果：
 
[root@VM-0-7-centos mydoc]# ./a.out 
1
2
3
4
5
6
7
8
9
10
 
注意，内存对齐字节偏移
 解决：资料【3】
 
#pragma pack(1)
struct node {
    int  xxx;//4字节
    char yyy;//1字节
    char data[0];//零字节数组
}
#pragma pack()

     1.什么是变长数组
 

struct MyData 
{
    int nLen;
    char data[0];
};   
	sizeof(MyData)=4;
 
可能有的编译器不支持char data[0];需要用char data[1]；代替，这样上面结构体大小是sizeof(MyData)=8(字节对齐）；
 
在上结构中，data是一个数组名；但该数组没有元素；该数组的真实地址紧随结构体MyData之后，而这个地址就是结构体后面数据的地址（如果给这个结构体分配的内容大于这个结构体实际大小，后面多余的部分就是这个data的内容），这种声明方法可以巧妙的实现C语言里的数组扩展。
 
如下下所示：
 

#include <iostream>
using namespace std;
struct MyData 
{
    int nLen;
    char data[0];			//如果这里用char* data;代替呢？是一个指针占用空间，而采用变长数组不占内存，数组名只是一个符号
							//代表一个不可修改的地址常量
};

int main()
{
    int nLen = 10;
    char str[10] = "123456789";

    cout << "Size of MyData: " << sizeof(MyData) << endl;

    MyData *myData = (MyData*)malloc(sizeof(MyData) + 10);
    memcpy(myData->data,  str, 10);

    cout << "myData's Data is: " << myData->data << endl;

    free(myData);

    return 0;
}


//输出：
Size of MyData: 4
myData's Data is: 123456789   
//由于数组没有元素，该数组在该结构体中不分配占用空间，所以sizeof(struct Mydata) = 4。 

 实际用时采取这样：

          struct MyData *p = (struct MyData *)malloc(sizeof(struct MyData )+strlen(str))
 
这样就可以通过p->data 来操作这个str。
 
 

 
 
struct MyData1 
 {
     int nLen;
     char data[0]; //char data[1];有的编译要求这样写
 
 };
 
 struct MyData2 
 {
     int nLen;
     char*data; 
 
 };
 
 对于上面两个结构体有下面几点说明：
 1. MyData1  (char data[0])结构体占用内存最小，Mydata2有个指针占用4B
 2.MyData1与前面结构体数据是连续的内存存储空间，而MyData2下，新增加数据data是单独开辟的空间；
 3.释放内存时，MyData1可以直接释放，而MyData2需要先释放指针指向内存，然后再释放结构体数据部分否则会内存泄漏
 
 

 
 

 

 
 
转载请注明原创出处，谢谢！
 
 
HappyFeet的博客
 
 
varchar 类型用于存储可变长字符串，是最常见的字符串数据类型。它比定长类型更节省空间，因为它仅使用必要的空间（例如：越短的字符串使用越少的空间）。
 
 
 
本文基于 MySQL 数据库进行探讨。
 
 
MySQL 版本为：Server version: 5.7.16 MySQL Community Server (GPL)。
 
 
 
1、varchar 的长度分配问题
 
一直对数据库的可变长字符串的长度分配问题存在疑问：不知道应该分配多长。
 
今天我们就来看看 varchar 的长度是依据什么来判断的？
 
 
有的人说：“属性有多长，就分配多长”。 ---- 即只分配真正需要的空间；
 
 
也有人说：“属性的长度应为 4 的倍数，因为这样可以做到内存对齐”。 ---- 即分配为 4 的倍数的长度，可以内存对齐；
 
 
另一些极端的人觉得：“既然对于 varchar 来说，越短的字符串使用越少的空间，那么这个长度定大一些也不会有什么问题，都分配 4000 的长度，这样可以避免出现超过长度的数据存不进去的问题”，即不管属性长度如何，都分配一个很大的长度，例如：4000.
 
 
那到底哪一种说法是对的呢？
 
我们来看个例子，假设我们要建一张表来存 CSDN 个人资料中的三条属性：昵称、地区和简介。下面有三个版本的建表语句，分别针对不同的说法所创建的。
 
-- 版本 1：只分配真正需要的空间
create table user_info (
	user_id 		long primary key,
	nickname 		varchar(20),
	region   		varchar(100),
	introduction 	varchar(500)
);
 
-- 版本 2：在版本 1 的基础上调整为 4 的倍数
create table user_info (
	user_id 		long primary key,
	nickname 		varchar(32),
	region   		varchar(128),
	introduction 	varchar(512)
);
 
-- 版本 3：长度都取 4000
create table user_info (
	user_id 		long primary key,
	nickname 		varchar(4000),
	region   		varchar(4000),
	introduction 	varchar(4000)
);
 
经过查阅众多资料之后，得出结论：版本 1 是最好的，即只分配真正需要的空间。
 
2、结论分析
 
下面就来说一下为什么：
 
（1）varchar 需要 1 或 2 个额外字节记录字符串的长度
 
如果列的最大长度小于或等于 255 字节，则只使用 1 个字节表示，否则使用 2 个字节。假设采用 latin1 字符集，一个 varchar(10) 的列需要 11 个字节的存储空间。varchar(1000) 的列则需要 1002 个字节，因为需要 2 个字节存储长度信息。
 
（2）内存对齐 确实有一定的性能提升，但是通过将字段长度定义为 4 的倍数做不到内存对齐
 
对于 varchar 类型来说，字符串是变长的，它的实际存储长度为：1 或 2 个额外字节 + 字符串实际长度。举几个例子：
 
a、往 varchar(8) 中存入 "abcdefgh"，实际存储长度应该为 1 + 8 = 9 个字节，第一个字节记录这个字符串的长度；
 
b、往 varchar(8) 中存入 "abc"，实际存储长度为 1 + 3 = 4 个字节。
 
c、往 varchar(1000) 中存入 "abc"，实际存储长度为 2 + 3 = 5 个字节。
 
说到内存对齐就简单提一下 MySQL 存储引擎 InnoDB 的数据页结构：page 是 MySQL 管理存储空间的基本单位，它由一条或多条 row 组成，row 就对应于 table 的一条记录，数据读取也是基于 page 来的，而不是一行一行的读。更多详情见：InnoDB数据页结构 。
 
（3）MySQL 在解决某些类型的查询时需要创建隐式临时表（又分为内存临时表和磁盘临时表）
 
对于临时表中的字段，MySQL 都会分配一个足够长的定长空间来存放。这个定长空间必须足够长以容纳其中最长的字符串，例如，如果是 varchar 列则需要分配其完整长度，如果使用 UTF-8 字符集，那么 MySQL 将会为每个字符预留三个字节。
 
假设我们在查询 user_info 的时候触发了隐式临时表的创建，对于 nickname 这一列，如果我们使用版本 1的建表语句，MySQL 按照完整长度，每条记录仅需要分配 20 的内存，而如果是版本 3的话，每条记录却需要分配 4000 的长度！！！很明显，这是一个非常糟糕的设计。
 
MySQL 在以下几种情况会创建临时表（不过这不是本文的重点！）
 
 
UNION 查询；
 
 
用到 TEMPTABLE 算法或者是 UNION 查询中的视图；
 
 
ORDER BY 和 GROUP BY 的子句不一样时；
 
 
表连接中，ORDER BY 的列不是驱动表中的；
 
 
DISTINCT 查询并且加上 ORDER BY 时；
 
 
SQL 中用到 SQL_SMALL_RESULT 选项时；
 
 
FROM 中的子查询；
 
 
子查询或者 semi-join 时创建的表；
 
 
（4）预分配内存空间的问题
 
 
 
注意，这一点存疑！这个说法我目前还没有找到具体的源码或文档说明，不过如果有预分配内存的话，那应该是说得通的，待找到依据再对这一点进行更新
 
 
这个和第三点有点类似，只是第三点讲的是在数据库内部引擎中，而这里讲的是客户端从数据库引擎获取数据。简单来说就是，对于一个 varchar(1000)，客户端的 executor 在没拿到存储引擎存储的数据之前，并不会知道我这一行拿出来的数据到底有多长，可能长度只有 1，可能长度是 800，那怎么办呢，那就只能先把最大空间分配好了，避免放不下的问题发生，这样实际上对于真实数据较短的 varchar 确实会造成空间的浪费。举例：如果我有 1000 个 varchar(1000)，但是每个只存一个字符，那么真实数据量其实只有 1K，但是我却需要 1M 的内存去适应它。
 
（5）字段长度能够起到一定的约束作用
 
比如一个字段长度最大不超过 10 个字节，那我们就可以将其设置为 varchar(10)，如果超过了 10 个字节，就说明这是个脏数据，这对实际数据能起到一定的约束。
 
（6）数据库对于索引的字段长度有限制，在长的数据列上建索引可能会报错，例如
 
mysql> create table long_length_table(
    -> long_column1 varchar(2000),
    -> long_column2 varchar(2000),
    -> long_column3 varchar(2000),
    -> long_column4 varchar(2000),
    -> long_column5 varchar(2000)
    -> );
Query OK, 0 rows affected (0.02 sec)

mysql> create table short_length_table(
    -> short_column1 varchar(10),
    -> short_column2 varchar(10),
    -> short_column3 varchar(10),
    -> short_column4 varchar(10),
    -> short_column5 varchar(10)
    -> );
Query OK, 0 rows affected (0.03 sec)

mysql> create index short_length_table_idx on short_length_table(short_column1, short_column2, short_column3, short_column4);
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> create index long_length_table_idx on long_length_table(long_column1, long_column2, long_column3, long_column4);
ERROR 1071 (42000): Specified key was too long; max key length is 3072 bytes
 
3、总结
 
在 varchar(30) 和 varchar(1000) 存入 “ab”，使用的存储空间区别不大，无非就是一个使用 1 个字节记录字符串的长度，另一个使用 2 个字节记录。但是对于在某些 case 下，varchar(1000) 的性能会比 varchar(30) 差很多，内存消耗也会成倍增加。
 
另外，将长度调整为 4 的倍数（内存对齐）会提高性能这种说法也是不对的。
 
所以得出的结论是： 只分配真正需要的空间
 
PS：以后终于可以理直气壮的跟别人讲：varchar 的长度不宜过长，满足长度要求即可；也不必强行将长度设置成 4 的倍数，这对性能提升是没有效果的。_
 
参考资料：
 
（1）《高性能 MySQL》第三版.
 
（2）MySQL - varchar length and performance
 
（3）What are the current best practices concerning varchar sizing in SQL Server?
 
（4）Best practices for SQL varchar column length
 
（5）Would using varchar(5000) be bad compared to varchar(255)?
 
（6）What are the optimum varchar sizes for MySQL?
 
（7）MySQL: Disk Space Exhaustion for Implicit Temporary Tables
 
（8）File Space Management
 
（9）InnoDB数据页结构

传统的数组创建
 
在java中我们都知道创建简单数组较为简单，和C很相似。如下是创建1、2、3维数组的代码。
 
int []  array = new int[5];
int [][] array = new int[5][5];
int [][][] array = new int[5][5][5];
 
但是作为传统数组都拥有一个共同的缺陷，那就是申请出来的数组长度都是固定的，不能改变。这就导致我们在不知道需要的空间大小的时往往很为难。
 传统的解决办法是：设置一个数组长度不可能突破的上界（通常声明为常数），将该常数作为要申请的数组大小，勉强可以满足使用。
 但是这种办法却有局限性，就是当你不能确定上界的时候，你的数组有很大可能越界，另外多余的空间也是一种内存的浪费。
 所以我们需要一种更加有效的解决方案，那就是——变长数组。
 
变长数组
 
变长数组，顾名思义，就是长度可变的数组。首先需要注意一点，这里说的变长数组不是指用变量来指定数组长度（如下所示）。这种方法只能本质上并不能算变长。因为当执行这句代码的时候，该数组被申请出来，数组长度为n当时的值。一旦被申请数组空间便不能再改变，也就是说此后n再改变，数组长度也不会再改变。所以本质来说它的数组长度并不可变。
 
int []  array = new int[n];
 
那么究竟如何创建变长数组呢？其实，java早就为我们准备了一系列专门用来存储数据的数据结构，即java.util库中的容器类，包括List、Set、Map及它们的子类。这些ADT几乎可以满足我们所有的存储需要，其中，**变长数组就可以由List类进行实现。**具体声明如下：
 
List<Integer> array = new ArrayList<Integer>();
 
那么可能有些同学又会问了，这个可以实现二维以上的边长数组吗？当然可以！之所以说java系统库提供的那几个ADT就可以满足我们的所有需要，一方面是因为它们基础，另一方面就是它们之间可以进行组合嵌套，组合嵌套之后它们就可以进一步表示更多更复杂的数据结构了！所以我们通过对List进行嵌套就能得到变长的多维数组了，下面就是变长的二维数组和三维数组申请实例：
 
List<List<Integer>> array = new ArrayList<List<Integer>>();
List<List<List<Integer>>> array = new ArrayList<List<List<Integer>>>();