C mảng phát triển động

Question

Tôi có một chương trình đọc danh sách "nguyên" của thực thể trong trò chơi và tôi dự định tạo một số chỉ mục (int) của số thực thể không xác định, để xử lý nhiều thứ. Tôi muốn tránh sử dụng quá nhiều bộ nhớ hoặc CPU để giữ các chỉ mục như vậy ...

Một giải pháp nhanh chóng và bẩn mà tôi sử dụng cho đến nay là khai báo, trong chức năng xử lý chính (tập trung cục bộ) mảng có kích thước các thực thể trò chơi tối đa và một số nguyên khác để theo dõi số lượng đã được thêm vào danh sách. Điều này là không thỏa đáng, vì mọi danh sách đều chứa 3000 mảng, không phải là nhiều, nhưng cảm thấy như một sự lãng phí, vì tôi có thể sử dụng giải pháp cho 6-7 danh sách cho các chức năng khác nhau.

Tôi chưa tìm thấy bất kỳ giải pháp cụ thể nào về C (không phải C++ hoặc C#) để đạt được điều này. Tôi có thể sử dụng con trỏ, nhưng tôi hơi sợ sử dụng chúng (trừ khi đó là cách duy nhất có thể).

Các mảng không rời khỏi phạm vi chức năng cục bộ (chúng sẽ được chuyển đến một hàm, sau đó bị loại bỏ), trong trường hợp thay đổi mọi thứ.

Nếu con trỏ là giải pháp duy nhất, làm thế nào tôi có thể theo dõi chúng để tránh rò rỉ?

Answer 1

tôi có thể sử dụng con trỏ, nhưng tôi một chút sợ sử dụng chúng.

Nếu bạn cần mảng động, bạn không thể thoát khỏi con trỏ. Tại sao bạn sợ? Họ sẽ không cắn (miễn là bạn cẩn thận, đó là). Không có mảng động tích hợp trong C, bạn sẽ chỉ phải tự viết một bản. Trong C++, bạn có thể sử dụng lớp được xây dựng trong std::vector. C# và chỉ là về mọi ngôn ngữ cấp cao khác cũng có một số lớp tương tự quản lý mảng động cho bạn.

Nếu bạn có kế hoạch để viết của riêng bạn, đây là một cái gì đó để bạn bắt đầu: triển khai mảng năng động nhất hoạt động bằng cách bắt đầu với một số kích thước mặc định (nhỏ), sau đó bất cứ khi nào bạn hết dung lượng khi thêm mới phần tử, tăng gấp đôi kích thước của mảng. Như bạn có thể thấy trong ví dụ dưới đây, nó không phải là rất khó khăn ở tất cả: (Tôi đã bỏ qua kiểm tra an toàn cho ngắn gọn)

typedef struct { 
    int *array; 
    size_t used; 
    size_t size; 
} Array; 

void initArray(Array *a, size_t initialSize) { 
    a->array = (int *)malloc(initialSize * sizeof(int)); 
    a->used = 0; 
    a->size = initialSize; 
} 

void insertArray(Array *a, int element) { 
    // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed. 
    // Therefore a->used can go up to a->size 
    if (a->used == a->size) { 
    a->size *= 2; 
    a->array = (int *)realloc(a->array, a->size * sizeof(int)); 
    } 
    a->array[a->used++] = element; 
} 

void freeArray(Array *a) { 
    free(a->array); 
    a->array = NULL; 
    a->used = a->size = 0; 
} 

Sử dụng nó chỉ là đơn giản:

Array a; 
int i; 

initArray(&a, 5); // initially 5 elements 
for (i = 0; i < 100; i++) 
    insertArray(&a, i); // automatically resizes as necessary 
printf("%d\n", a.array[9]); // print 10th element 
printf("%d\n", a.used); // print number of elements 
freeArray(&a); 

Answer 2

Có một vài tùy chọn mà tôi có thể nghĩ đến.

1. Danh sách liên kết. Bạn có thể sử dụng một danh sách liên kết để tạo ra một mảng phát triển động như điều. Nhưng bạn sẽ không thể thực hiện array[100] mà không cần phải đi qua 1-99 trước tiên. Và nó có thể không có ích cho bạn để sử dụng một trong hai.
2. Mảng lớn. Chỉ cần tạo một mảng có đủ không gian cho mọi thứ
3. Thay đổi kích thước mảng. Tạo lại mảng khi bạn biết kích thước và/hoặc tạo một mảng mới mỗi khi bạn hết dung lượng với một số lề và sao chép tất cả dữ liệu vào mảng mới.
4. Kết hợp mảng danh sách được liên kết. Đơn giản chỉ cần sử dụng một mảng với một kích thước cố định và một khi bạn chạy ra khỏi không gian, tạo ra một mảng mới và liên kết đến đó (nó sẽ là khôn ngoan để theo dõi mảng và liên kết đến mảng tiếp theo trong một cấu trúc).

Thật khó để nói lựa chọn nào là tốt nhất trong trường hợp của bạn. Đơn giản chỉ cần tạo ra một mảng lớn là một trong những giải pháp dễ nhất và không nên cung cấp cho bạn nhiều vấn đề trừ khi nó thực sự lớn.

Answer 3

Khi bạn đang nói

làm cho một mảng tổ chức một số chỉ số (int) của một số không xác định của các tổ chức

bạn về cơ bản nói rằng bạn đang sử dụng "con trỏ", nhưng một trong đó là một con trỏ địa phương toàn bộ mảng thay vì con trỏ trên toàn bộ bộ nhớ. Vì bạn đang sử dụng khái niệm "con trỏ" (tức là số id đề cập đến phần tử trong mảng), tại sao bạn không chỉ sử dụng con trỏ thông thường (tức là số id đề cập đến phần tử trong mảng lớn nhất: toàn bộ bộ nhớ).

Thay vì các đối tượng của bạn lưu trữ một số id tài nguyên, bạn có thể làm cho chúng lưu trữ một con trỏ thay thế. Về cơ bản giống nhau, nhưng hiệu quả hơn nhiều vì chúng ta tránh biến "mảng + chỉ mục" thành "con trỏ".

Pointers không đáng sợ nếu bạn nghĩ về họ như chỉ số mảng cho toàn bộ bộ nhớ (đó là những gì họ thực sự là)

Answer 4

Như với tất cả mọi thứ điều đó có vẻ đáng sợ hơn lúc đầu, đó là cách tốt nhất để vượt qua nỗi sợ ban đầu là đắm mình vào sự khó chịu của số chưa biết! Đó là vào những thời điểm mà chúng ta học được nhiều nhất.

Thật không may, có những hạn chế. Trong khi bạn vẫn đang học cách sử dụng một hàm, bạn không nên giả định vai trò của một giáo viên, ví dụ. Tôi thường đọc câu trả lời từ những người dường như không biết cách sử dụng realloc (tức là câu trả lời hiện được chấp nhận!) nói cho người khác biết cách sử dụng không chính xác, đôi khi dưới vỏ bọc rằng họ đã xử lý lỗi bị bỏ qua, mặc dù đây là một cạm bẫy phổ biến mà cần phải đề cập đến. Here's an answer explaining how to use realloc correctly. Lưu ý rằng câu trả lời đang lưu trữ giá trị trả lại vào một biến số khác nhau để thực hiện kiểm tra lỗi.

Mỗi khi bạn gọi một hàm và mỗi khi bạn sử dụng một mảng, bạn đang sử dụng một con trỏ. Các chuyển đổi đang diễn ra hoàn toàn, mà nếu bất cứ điều gì thậm chí còn đáng sợ hơn, vì đó là những thứ chúng ta không thấy thường gây ra nhiều vấn đề nhất. Ví dụ, rò rỉ bộ nhớ ...

Các toán tử mảng là toán tử con trỏ. array[x] thực sự là phím tắt cho *(array + x), có thể được chia nhỏ thành: * và (array + x). Rất có thể là * là điều khiến bạn bối rối. Chúng tôi cũng có thể loại bỏ việc bổ sung từ các vấn đề bằng cách giả sử x là 0, do đó, trở thành array[0]*array vì thêm 0 sẽ không thay đổi giá trị ...

... và do đó chúng ta có thể thấy rằng *array tương đương với array[0]. Bạn có thể sử dụng nơi bạn muốn sử dụng và ngược lại. Các toán tử mảng là toán tử con trỏ.

malloc, realloc và bạn bè không khái niệm về con trỏ bạn đã sử dụng tất cả cùng; họ chỉ đơn thuần là sử dụng điều này để triển khai một số tính năng khác, đây là một dạng thời lượng lưu trữ khác, phù hợp nhất khi bạn muốn thay đổi mạnh mẽ, năng động trong kích thước.

Đó là một sự xấu hổ rằng hiện chấp nhận câu trả lời cũng đi ngược lại các hạt some other very well-founded advice on StackOverflow, và cùng một lúc, bỏ lỡ một cơ hội để giới thiệu một tính năng ít được biết đến mà tỏa sáng cho chính xác usecase này: Các thành viên mảng linh hoạt! Đó thực sự là một khá chia câu trả lời ... :(

Khi bạn xác định struct của bạn, khai báo mảng của bạn vào cuối của cấu trúc, mà không cần bất kỳ giới hạn trên Ví dụ:.

struct int_list { 
    size_t count; 
    int value[]; 
}; 

Điều này sẽ cho phép bạn kết hợp mảng lại int vào việc phân bổ giống như count của bạn, và sau khi họ bị ràng buộc như thế này có thể rất tiện dụng!

sizeof (struct int_list) sẽ hoạt động như thể value có kích thước bằng 0, vì vậy nó sẽ cho bạn biết kích thước của cấu trúc với danh sách trống. Bạn vẫn cần phải thêm kích thước được chuyển đến realloc để chỉ định kích thước danh sách của bạn.

Một mẹo hữu ích khác là hãy nhớ rằng realloc(NULL, x) tương đương với malloc(x) và chúng tôi có thể sử dụng điều này để đơn giản hóa mã của chúng tôi. Ví dụ:

int push_back(struct int_list **fubar, int value) { 
    size_t x = *fubar ? fubar[0]->size : 0 
     , y = x + 1; 

    if ((x & y) == 0) { 
     void *temp = realloc(*fubar, sizeof **fubar 
            + (x + y) * sizeof fubar[0]->value[0]); 
     if (!temp) { return 1; } 
     *fubar = temp; // or, if you like, `fubar[0] = temp;` 
    } 

    fubar[0]->value[x] = value; 
    fubar[0]->count = y; 
    return 0; 
} 

struct int_list *array = NULL; 

Lý do tôi đã chọn để sử dụng struct int_list ** như là đối số đầu tiên có thể không có vẻ ngay lập tức rõ ràng, nhưng nếu bạn suy nghĩ về đối số thứ hai, bất kỳ thay đổi nào value từ bên trong push_back sẽ không được hiển thị cho chức năng mà chúng tôi đang gọi từ, phải không? Cũng vậy với đối số đầu tiên, và chúng ta cần để có thể sửa đổi array của chúng tôi, không chỉ đây nhưng có thể là ở khắp mọi chức năng khác/s chúng tôi vượt qua nó để ...

array bắt đầu giảm giá chỉ không có gì; nó là một danh sách trống. Khởi tạo cũng giống như thêm vào nó. Ví dụ:

struct int_list *array = NULL; 
if (!push_back(&array, 42)) { 
    // success! 
}