flexible array柔性数组、不定长的数据结构Struct详解

简介: 柔性数组,这个名词对我来说算是比较新颖的,在学习跳跃表的实现时看到的。这么好听的名字,的背后到底是如何的优雅。 柔性数组,其名称的独特和迷惑之处在于“柔性”这个词。在C/C++中定义数组,是一个定长的数据结构,最常用的定义如下 int arr[100]; 上述代码的中arr数组的长度已知,我们把上面的语句称之为声明语句,因为在编译期数组的长度已经确定了,我暂且发明了一个词来称呼这类数组——“刚性”数组(声明,这个词是我臆想的,是不存在这种说法的)。

 

柔性数组,这个名词对我来说算是比较新颖的,在学习跳跃表的实现时看到的。这么好听的名字,的背后到底是如何的优雅。


柔性数组,其名称的独特和迷惑之处在于“柔性”这个词。
在C/C++中定义数组,是一个定长的数据结构,最常用的定义如下

int arr[100];

上述代码的中arr数组的长度已知,我们把上面的语句称之为声明语句,因为在编译期数组的长度已经确定了,我暂且发明了一个词来称呼这类数组——“刚性”数组(声明,这个词是我臆想的,是不存在这种说法的)。

你可能会说:等等,C/C++不是有可以在运行期通过malloc调用来创建动态数组的做法吗?
没错,柔性数组正是需要malloc来实现的,其柔性也是在这个地方体现的。

套路先行

我们先来看一看柔性数组到底是用来干什么的吧?

柔性数组(flexible array member)也叫伸缩性数组成员,这种结构产生与对动态结构体的去求。在日常编程中,有时需要在结构体中存放一个长度是动态的字符串(也可能是其他数据类型),一般的做法,实在结构体中定义一个指针成员,这个指针成员指向该字符串所在的动态内存空间。

在通常情况下,如果想要高效的利用内存,那么在结构体内部定义静态的数组是非常浪费的行为。其实柔性数组的想法和动态数组的想法是一样的。

先修知识

  • 不完整类型

    在C/C++中对于不完整类型的定义是这样的:
    不完整类型是一种缺乏足够的信息去描述一个完整对象的类型
    还是以数组的定义/声明为例子。
// 一个为知长度的数组属于不完整类型
// 这个语句属于声明语句,不是定义语句
extern int a[]; // 这样的语句是错误的, extern关键字不能去掉 // int a[] // 不完整类型的数组需要补充完整才能使用 // 下面的语句是声明语句(定义+初始化) int a[] = {10, 20};
  • 结构体

    看到这个标题的你可能会说,什么?结构体还用得着你来补充?
    如果各位看官对结构体和内存对其比较熟悉的话,可以跳过这部分,看总结本段的总结,对后面柔性数组的说明有点帮助。

对于内存对齐的部分已经超出了文章所要讨论的内容了。那我想讲的是什么东西,且看下面的代码

#include<stdio.h>

struct test{ int i; char *p; }; int main(void){ struct test t; printf("t:\t%p\n", &t); printf("t.i:\t%p\n", &(t.i)); printf("t.p:\t%p\n", &(t.p)); }

内存对齐

我们看到t.i的地址和t的地址是一样的。t.p的地址就是(&t + 0x8),0×8这个偏移地址就是成员p在编译时就被编译器给hard code了的地址。

总结:不管结构体的实例是什么,访问其成员就是实例的地址加上成员偏移量。这个偏移量是编译器hard code的,跟内存对齐等因素有关。

千呼万唤始出来

我们来回顾一下,柔性数组用来在结构体中存放一个长度动态的字符串。
其实不用柔性数组我们一样可以做到:在结构体中定义一个方法,在方法中动态地将指针指向动态数组

#include<cstring>
#include<cstdlib> #include<cstdio> struct Test{ int a; char *p; void set_str(const char *str){ int len = std::strlen(str); if(len <=0) return; p = (char*)std::malloc((len+1)*sizeof(char)); std::strcpy(p, str); p[len] = '\0'; } }; int main(){ const char copy_str[] = "Hello World"; Test t; t.set_str(copy_str); printf("Content:\n"); printf("t.p:\t%s\n", t.p); printf("Address:\n"); printf("t.p\t %p\n", t.p); printf("&t.p\t %p\n", &(t.p)); }

指针方式
我们看到,上面的代码的确是可以完成我们想要的结果。我们看了一下指针p和数组的起始地址。我们可以看到动态数组的内存块和字符串的内存是两块不一样的内存。
折磨程序员的来了,我们在析构对象时,需要显式地在析构函数里面对指针p引用的内存进行释放,不然会出现内存泄露的情况。

那么柔性数组是怎么做到的呢?
还是回到上述的结构体

struct Test{
    int a;
    char *p; };

我们想把字符串和结构体连在一起的话,释放的内存时候就能够顺便把字符串的内存给释放掉了,看一看下面的代码

// 使用上面的结构体Test
const str copy_str[] = "Hello World"; int len = std::strlen(copy_str); // 申请连续的空间 Test *p_test = (Test*)std::malloc(sizeof(Test)+(len+1)*sizeof(char)); // 复制数组 std::strcpy(p_test+1, copy_str); ((char*)(p_test+1))[len] = '\0';

起始这么依赖,会发现char *p就成了多余的东西了,我们完全可以使用语句(char*)(p_test+1)来获取字符串的地址了。

聪明的程序员不想被这么丑陋的代码给糊弄,他们想如果能够找到一种方法既能直接引用字符串,又不占用结构体的空间就很棒了。符合这个条件的应该是一个非对象的符号地址
回忆一下上文所说的不完整类型,起始就是一个符号地址。在结构体的尾部放一个长度为0的方案似乎不错,但是C/C++标准规定是不能定义长度为0的数组。标准不允许?编译器厂商就自行开发呗,有些编译器把0长度的数组作为自己的非标准扩展。

struct flexible_t{
    int a; double b; char c[0]; }; 

c就叫柔性数组成员(flexible array member).我觉得翻译成灵活数组成语也是可以的。此时p_test->c就是数组的首地址,不再需要原来那么丑陋的代码了。

这种代码结构这么常用,标准马上就支持了。在C99标准中便包含了柔性成员数组。
记得上文所说的不完整类型吗,C99便是使用不完整类型实现柔性数组成员的。为什么使用不完整类型呢,说说我的理解。

int a[] = {10, 20}; 

看到这个声明语句,我们发现a[]其实就是个数组记号,不完整类型,由于赋值语句,所以在编译时便确定了数组的大小,是一个完整的数组类型。
在结构体中便利用不完整类型在运行对动态的数组进行指明。

C99标准的定义如下

struct flexible_t{
    int a; double b; char c[]; // 不只是char类型,其他类型同样也是可以 }

由于声明内存连续性的关系,柔性数组成员必须定义在结构体的最后一个,并且不能是唯一的成员。
我们再来看一看整个结构体(包含数组内存的分布情况)

#include<cstring>
#include<cstdlib> #include<cstdio> # define new_instance(n) (Felexible*) std::malloc(sizeof(Flexible) + (n+1)*sizeof(char)) struct Flexible{ int a; char p[0]; }; int main(){ const char copy_str[] = "Hello World"; // 我们使用宏来把创建对象的代码简化 Flexible *flexible_p = new_instance(std::strlen(copy_str)); std::strcpy(flexible_p->p, copy_str); printf("Content:\n"); printf("%s\n", flexible_p->p); printf("Address:\n"); printf("t.p:\t %p\n", flexible_p->p); printf("&t.p:\t %p\n", &(flexible_p->p)); free(flexible_p); }

柔性数组成员方式

由运行结果就可以看出,整个结构体是连续的,并且释放结构体的方式也非常简单直接对结构体指针进行释放。

warning C4200: 使用了非标准扩展: 结构/联合中的零大小数组

由于这个是C99的标准,在ISO C和C++的规格说明书中是不允许的。在vs下使用0长度的数组可能会得到一个警告。
然而gcc, clang++预先支持了C99的玩法,所以在Linux下编译无警告

总结

我们学习了柔性数组成员的来源及一些用法,
其实柔性数组成员在实现跳跃表时有它特别的用法,在Redis的SDS数据结构中和跳跃表的实现上,也使用柔性数组成员。

 

 
 
谋胆并重
目录
相关文章
|
2月前
|
存储 应用服务中间件 nginx
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
82 0
|
4月前
|
应用服务中间件 nginx C语言
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
这两种数据结构是Nginx自定义数据类型的例子,它们证明了Nginx设计者在构建一个为高并发和高性能优化的web服务器时的精确和高效。理解这些数据结构是深入学习Nginx内部机制的基础,同时也是扩展和开发Nginx模块不可或缺的一部分知识。
46 1
|
7月前
|
SQL 存储 Java
Hive 特殊的数据类型 Array、Map、Struct
在Hive中,`Array`、`Map`和`Struct`是三种特殊的数据类型。`Array`用于存储相同类型的列表,如`select array(1, &quot;1&quot;, 2, 3, 4, 5)`会产生一个整数数组。`Map`是键值对集合,键值类型需一致,如`select map(1, 2, 3, &quot;4&quot;)`会产生一个整数到整数的映射。`Struct`表示结构体,有固定数量和类型的字段,如`select struct(1, 2, 3, 4)`创建一个无名结构体。这些类型支持嵌套使用,允许更复杂的结构数据存储。例如,可以创建一个包含用户结构体的数组来存储多用户信息
665 0
|
存储 数据处理 C语言
Python二进制通信:struct、array、ctypes模块比较
Python是一种广泛应用于数据处理和网络编程的语言。在与C语言或其他设备进行二进制通信时,Python需要使用一些专门的模块来转换数据格式。本文将介绍三个常用的模块:struct、array、ctypes,并从结构说明和性能分析两方面进行比较。
264 0
Python二进制通信:struct、array、ctypes模块比较
|
存储 算法 Python
Python数据结构与算法(7)---数组array
Python数据结构与算法(7)---数组array
126 0
Python数据结构与算法(7)---数组array
|
存储 Go 索引
Go数据结构系列之 Array and Alice
Go数据结构系列之 Array and Alice
146 0
Go数据结构系列之 Array and Alice
|
存储 JavaScript 前端开发
JavaScript数据结构之 Array
几乎所有的编程语言都原生支持数组类型,因为其是最简单的内存数据结构。数组也是 JavaScript 中最常见的数据结构之一,它提供了很多处理存储数据的方法。JavaScript 中,数组是经过改进的对象,和其他语言不同的是,数组中每个槽位可以存储任意类型的数据,这意味着可以创建一个数组,它的第一个元素是字符串、第二个元素是数字、第三个是对象。在 JavaScript 中拥有许多很实用的方法,本文就来总结一下数组中常用的操作方法。
92 0
|
索引 Ruby
【Ruby on Rails全栈课程】2.6 ruby的数据结构--数组(Array)
数组是一个集合,但是不仅仅是数字的集合,可以是任何对象(String、 Integer、 Fixnum、 Hash、 Symbol 等对象)的集合。数组的索引是从0开始的有序整数,可以通过正数索引或者负数索引来寻找数组中的值,数组中的值是有顺序的。
97 0