C中的智能/动态数组

Question

我试图在C中创建一个智能/动态数组实现，它应该是C++向量/堆栈/队列之间的混合。

这就是我想出来的：

标头(smart_array.h)：

#pragma once

#include <stddef.h>

typedef struct smart_array smart_array_t;

void smart_array_alloc(smart_array_t** array, size_t capacity);
void smart_array_free(smart_array_t** array);
int  smart_array_resize(smart_array_t* array, size_t capacity);

void smart_array_capacity(smart_array_t* array, size_t* capacity);
void smart_array_total(smart_array_t* array, size_t* total);
void smart_array_empty(smart_array_t* array, int* empty);

int  smart_array_set(smart_array_t* array, size_t index, void* item);
int  smart_array_set_back(smart_array_t* array, void* item);
int  smart_array_set_top(smart_array_t* array, void* item);

void smart_array_get(smart_array_t* array, size_t index, void** item);
void smart_array_get_back(smart_array_t* array, void** item);
void smart_array_get_top(smart_array_t* array, void** item);

int  smart_array_push_back(smart_array_t* array, void* item);
int  smart_array_push_top(smart_array_t* array, void* item);

int  smart_array_pop(smart_array_t* array, size_t index);
int  smart_array_pop_back(smart_array_t* array);
int  smart_array_pop_top(smart_array_t* array);
int  smart_array_clear(smart_array_t* array);

源文件：(smart_array.c)：

#include "smart_array.h"
#include <stdlib.h>

struct smart_array {
    void** items;
    size_t total;
    size_t capacity;
};

void smart_array_alloc(smart_array_t** array, size_t capacity) {
    if(!(*array = malloc(sizeof(struct smart_array))))
        return;
    if(!((*array)->items = malloc(sizeof(void*) * capacity))) {
        free(*array);
        *array = 0;
        return;
    }
    (*array)->capacity = capacity;
    (*array)->total = 0;
}

void smart_array_free(smart_array_t** array) {
    if(array && *array) {
        free((*array)->items);
        free(*array);
        *array = 0;
    }
}

int smart_array_resize(smart_array_t* array, size_t capacity) {
    if(array) {
        void **items = realloc(array->items, sizeof(void*) * capacity);
        if(items) {
            array->items = items;
            array->capacity = capacity;
            return 0;
        }
    }
    return 1;
}

void smart_array_capacity(smart_array_t* array, size_t* capacity) {
    *capacity = !array ? 0 : array->capacity;
}

void smart_array_total(smart_array_t* array, size_t* total) {
    *total = !array ? 0 : array->total;
}

void smart_array_empty(smart_array_t* array, int* empty) {
    *empty = array->total == 0;
}

int smart_array_set(smart_array_t* array, size_t index, void* item) {
    if(array) {
        if (index >= 0 && index < array->total) {
            array->items[index] = item;
            return 0;
        }
    }
    return 1;
}

int smart_array_set_back(smart_array_t* array, void* item) {
    size_t total;
    smart_array_total(array, &total);
    return smart_array_set(array, total - 1, item);
}

int smart_array_set_top(smart_array_t* array, void* item) {
    return smart_array_set(array, 0, item);
}

void smart_array_get(smart_array_t* array, size_t index, void** item) {
    if(array && item) {
        if (index >= 0 && index < array->total)
            *item = array->items[index];
        else 
            *item = 0;
    }
}

void smart_array_get_back(smart_array_t* array, void** item) {
    size_t total;
    smart_array_total(array, &total);
    smart_array_get(array, total - 1, item);
}

void smart_array_get_top(smart_array_t* array, void** item) {
    smart_array_get(array, 0, item);
}

int smart_array_push_back(smart_array_t* array, void* item) {
    if(array) {
        if(array->capacity == array->total) {
            if(smart_array_resize(array, array->capacity * 2))
                return 1;
        }
        array->items[array->total++] = item;
        return 0;
    }
    return 1;
}

int smart_array_push_top(smart_array_t* array, void* item) {
    if(array) {
        if(array->capacity == array->total) {
            if(smart_array_resize(array, array->capacity * 2))
                return 1;
        }
        array->total++;
        for(size_t s = array->total; s > 0; --s) 
            array->items[s] = array->items[s - 1];
        array->items[0] = item;
        return 0;
    }
    return 1;
}

int smart_array_pop(smart_array_t* array, size_t index) {
    if(array && (index >= 0) && (index < array->total)) {
        array->items[index] = 0;
        for (int i = index; i < array->total - 1; ++i) {
            array->items[i] = array->items[i + 1];
            array->items[i + 1] = NULL;
        }
        array->total--;
        if ((array->total > 0) && ((array->total) == (array->capacity / 4))) {
            if(smart_array_resize(array, array->capacity / 2))
                return 0;
        }
    }
    return 1;
}

int smart_array_pop_back(smart_array_t* array) {
    size_t total;
    smart_array_total(array, &total);
    return smart_array_pop(array, total - 1);
}

int smart_array_pop_top(smart_array_t* array) {
    return smart_array_pop(array, 0);
}

int smart_array_clear(smart_array_t* array) {
    int empty;
    smart_array_empty(array, &empty);
    while(!empty) {
        smart_array_pop_top(array);
        smart_array_empty(array, &empty);
    }
    return 0;
}

测试(main.c)：

#include "smart_array.h"
#include <stdlib.h>
#include <stdio.h>

void print_smart_array(smart_array_t* array) {
    size_t total, capacity;
    
    smart_array_total(array, &total);
    smart_array_capacity(array, &capacity);
    
    printf("Array total: %i\n", total);
    printf("Array capacity: %i\n", capacity);
    
    printf("Array items:\n");
    for(size_t i = 0; i < total; ++i) {
        int* val;
        smart_array_get(array, i, (void**)&val);
        printf("\t%i\n", *val);
    }
}

int main(void) {
    smart_array_t* a;
    smart_array_alloc(&a, 4);
    
    int* x = malloc(sizeof(int));
    int* y = malloc(sizeof(int));
    int* z = malloc(sizeof(int));
    int* w = malloc(sizeof(int));
    
    *x = 3;
    *y = 56;
    *z = 100;
    *w = 87;
    
    smart_array_push_back(a, x);
    smart_array_push_back(a, x);
    smart_array_push_top(a, w);
    smart_array_push_back(a, w);
    smart_array_push_top(a, y);
    
    print_smart_array(a);
    
    smart_array_clear(a);
    
    print_smart_array(a);
    
    free(x);
    free(y);
    free(z);
    free(w);
    smart_array_free(&a);
}
```#qcStackCode# 

Answer 1

文件结构

代码被很好地组织成测试、实现和头文件。在头中包含stddef.h是合适的，因为您使用了size_t。

一致性

在编写指针之前，请考虑确保这些指针是有效的，例如，使用assert，或者至少在文档中。这段代码的用户可能不理解，对他们来说，通过筛选您的代码来发现问题是不理想的。至少，它必须是一致的；在smart_array_set中，它检查null，而其他的则不检查。

typedef struct smart_array smart_array_t可能存在问题。请参见讨论类型后接_T代表和Linux内核样式指南。我认为用户应该可以自由地将其表示为typedef，所以我只需要使用struct smart_array；C和C++是不同的语言。

返回值

从void返回smart_array_alloc是有问题的，因为它可以采用两种不同的路径；一种是查询指针，看看它是否成功。它应该很容易正确地使用，而且就目前的情况而言，在不检查的情况下使用它是一个(无记录的)错误。

我希望smart_array_get(_*)会返回该项目。就其本身而言，有一个指针指向传入的项，并返回void。当需要功能组合时，这可能会很烦人。大多数人的其他功能也是一样的。至少在很短的时间内，他们就会从C++中解释这一变化。

我希望在访问越界时会出现某种错误或反馈，但这没有任何作用。可以说，这不是最好的选择。

构造器简化

我希望大多数时候都会用默认的构造函数调用smart_array_alloc，所以我会考虑做一个不包括调用这个构造函数的capacity。

这两个分配由smart_array_alloc正确处理，但是可以通过调用smart_array_free来简化它们。一个不需要两个分配，因为它已经对齐了，将它作为一个分配会更简单。

if(!(*array = malloc(sizeof struct smart_array + sizeof(void*) * capacity)
    return (fail);
(*array)->items = (void *)(*array + 1);

实际上，有多个内存分配可以全部调用smart_array_resize。

如果ptr是空指针，对于指定的大小，realloc()应该等同于malloc()。

我会考虑在头中公开struct smart_pointer，以便在堆栈上进行分配，并进一步简化它，但这是一个不总是合适的设计决策。

零值

当空或容量为零时，smart_array_set_back和smart_array_set_top将有未定义的行为。

私人成员的

使用

我认为在这个私有代码中使用total作为数据成员是可以的，而不是让它通过面向外部的公共smart_array_total。访问私有成员的smart_array_clear应该非常简单。