还施水阁
0%

ANSI-Bit Fields

发表于 更新于 分类于

我们在前面提到了用空间换时间的字节对齐规则,会发现结构体其实会浪费很多的空间以用来提高程序运行速度.在这一部分,我们将讨论结构体中的节省空间的技巧,也就是所谓的位域和柔性数组.

位域

我们先考虑如下的实际例子,我们需要判断一个变量是否为extern,static以及关键字.如果我们用最为直接的方式,我们只需要设置多个char变量作为flag,分别设置0或1,来表示是否的二元状态.但是这样的话,我们需要开辟多个字节的空间,这样会浪费很多的空间.

我们先利用屏蔽码集合来解决这个问题,如

1
2
3
#define KEYWORD 01
#define EXTERNAL 02
#define STATIC 04

值得注意的是,这些数字必须是2的幂次;这样我们就可以通过位运算来进行判断.例如:

1
2
flag|=EXTERNAL|STATIC;//将flag的external和static位置为1
flah&=~(EXTERNAL|STATIC);//将flag的external和static位置为0

位域指信息在存储时,并不需要占用一整个字节，而只需要占用一个或几个二进制位即可.例如,如果我们设置多个flag,分别用于判断变量是否为extern,static或const;常见的做法是用三个char变量来存储这三个flag,但这样的话,我们需要开辟三个字节的空间,然而实际上flag的取值只有0和1两个状态,因此我们完全可以只使用一个二进制位来存储每个flag.这样的话,我们只需要开辟一个字节的空间即可.这样的技巧就是位域.

1
2
3
4
5
6
struct
{
  unsigned int is_keyword:1;
  unsigned int is_external:1;
  unsigned int is_static:1;
} flags;

这样他只开辟了一个unsigned int的空间.其调用和正常的结构体成员一样,通过StructName.BitName来调用.位域的使用方法大体需要遵循如下几点:

  1. 定义位域时,可以指定成员的位域宽度,即成员所占的位数

  2. 位域的宽度不能超过其类型的位数,因为位域必须适用于所用的整数类型(如int,unsigned int等)

  3. 位域可以单独使用,也可以和其他成员一起使用,如

    1
    2
    3
    4
    5
    6
    struct
    {
      int a:1;
      int b;
      int c:2;
     };

我们进一步讨论位域的几个空间占用的问题:

  1. 不可以跨字节存储,如

    1
    2
    3
    4
    5
    6
    struct
    {
      char a:3;
      char b:4;
      char c:5;
    };

这里我们需要开辟9个二进制位,但是char只有8个二进制位,因此我们需要开辟两个字节.但实际上我们会发现,a和b已经占用了7个二进制位,因此一个字节只剩下了1个空闲的二进制位,但是c需要5个二进制位,因此我们会选择空闲掉这个空间,开辟一个新的字节空间来存储c.

  1. 不可以跨类型存储,如

    1
    2
    3
    4
    5
    struct
    {
      char a:1;
      int b:1;
    };

虽然这个例子里面,我们只需要两个二进制位,但我们发现这两个变量的类型不同,因此我们不能仅开辟一个字节的空间,而应该按照对应类型大小开辟.char开辟1个字节,但其需要与int对齐,所以需要额外开辟3个空闲字节;int则需要开辟4个字节,这样一共开辟8个字节.实际上在GCC下,只需要开辟4个字节,这是一种极度节省空间的方法,先开辟类型最大的空间,然后再根据实际情况来存储.
在位域中,还有一些特殊的用法,如:

  1. 无名位域:位域成员可以没有名字,只给出数据类型和位宽,

    1
    2
    3
    4
    5
    6
    struct
    {
       int m: 12;
       int  : 20;  //该位域成员不能使用
       int n: 4;
    };

    这里的无名位域的作用一般用于填充或调整成员位置.并且因为其没有名字,所以无名位域是不可以被使用的.

  2. 位域的大小为0:这表示该位域为空域,其只能在无名位域中使用,下一个域则以下一个类型单元开始存放,如

    1
    2
    3
    4
    5
    6
    7
    struct
    {
       char m: 1;
       short l:2;
       int  : 20;  //该位域成员不能使用
       int n: 4;
    };

    这里的n会在第四个字节开始存放.

柔性数组

柔性数组的产生其实是与coding中对动态结构体的需求有关.在日常的编程中,我们可能希望在结构体里存放一个长度是动态的数组,一般的做法是在结构体中定义一个指针成员,用这个指针指向一个动态开辟的数组空间.然而这一操作会对内存管理带来极大的困扰,因为我们需要在使用完这个结构体后,手动释放这个指针指向的空间.而柔性数组其实就是在结构体中存放一个长度动态的数组.

柔性数组的使用

1
2
3
4
5
6
struct Test
{
  char a;
  double b;
  int c[0];
}

柔性数组成员的两个特征:

  1. 柔性数组成员只能是结构体的最后一个成员
  2. 柔性数组成员的数组长度为0,因此柔性数组成员不占用结构体的空间.故上面的struct空间为16个字节.

因此,对于柔性数组,我们可以按照如下角度来理解:

  1. 柔性方面:柔性数组成员的长度是动态的,所管理的空间可大可小,因此我们可以根据实际情况来动态调整空间大小.
  2. 数组成员方面:形式为数组形式,但大小为0,其次,被定义在结构体内部.

传统结构体指针成员使用

如果我们仅考虑静态的结构体,可能并不是很容易体现柔性数组的优势,但如果我们考虑结构体的动态生成,就会十分明显的体现出柔性数组的优势.例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<malloc.h>
typedef struct Test
{
    int size;
    int* ptr;
}Test;
int main()
{
    int sz = 10;
    Test* pt = (Test*)malloc(sizeof(Test));
    pt->ptr = (int*)malloc(sizeof(int) * sz);
    pt->size = sz;
    for (int i = 0; i < pt->size; i++)
        pt->ptr[i] = i + 1;
    for (int i = 0; i < pt->size; i++)
        printf("%d ", pt->ptr[i]);
    printf("\n");
    free(pt->ptr);
    free(pt);
}

这里我们可以发现,传统方式下有两个缺点:

  1. 结构体成员ptr是一个指针,因此我们需要为之开辟空间.
  2. 对于申请的结构体空间和指针空间,我们需要分开申请和释放;因此这并不利于内存管理,及其容易出现内存泄漏的问题,从而导致程序运行效率低下.

柔性数组成员的使用

柔性数组成员的使用可以很好的解决上面的问题,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
#include<malloc.h>
typedef struct Test
{
    int size;
    int ptr[0];
}Test;
int main()
{
    int sz = 10;
    Test* pt = (Test*)malloc(sizeof(Test)+sizeof(int)*sz);
    pt->size = sz;
    for (int i = 0; i < pt->size; i++)
        pt->ptr[i] = i + 1;
    for (int i = 0; i < pt->size; i++)
        printf("%d ", pt->ptr[i]);
    printf("\n");
    free(pt);
}

这里其实主要的区别在于,我们在malloc的时候不仅为结构体开辟了空间,还为柔性数组开辟了空间.我们可以这么理解柔性数组成员,柔性数组成员其实就是一个指针,这个指针指向紧贴着结构体空间后的空间,当我们同时开辟结构体和柔性数组空间时,柔性数组成员其实就是指向柔性数组空间的首元素.因此,我们不需要将开辟空间的操作分开,而是一次性完成,这样就很好的解决了内存管理的问题.