重新分配...何时和最好的方式。 [英] Reallocating... When and the best way.

问题描述

我正在创建一个小矢量绘画应用程序。 （使用纯Win32 API和C）



到目前为止它只能在窗口上绘制框。一个框采用 typedef struct 来存储其数据（X和Y pos，width和height ..）。存储这些数据的数组（ typedef struct ）是动态分配的。



我使用 malloc（）在第一次为该数组分配内存。

每当创建一个新框时，使用 realloc（）扩展该数组。并且新框的数据被指定为数据[last_box] = new_box 。



通过后到 WM_PAINT 开始喘气。



这个设计工作正常！但问题是，

1.这是一个很好的做法，每次创建新盒子时都要重新分配。

2.有没有其他选择，如果有的话哪个是最好的。

解决方案

回答1.不，这不是一个好主意。一旦你在绘图中达到几千个元素，这将变得非常缓慢。不断的重新分配也可能会破坏内存，导致你的有效内存使用量比必要的高很多倍。



回答2.是的，有很多选择。所有这些都基于链接数据结构的想法。您的案例中的每个元素，向量或矩形都有与之关联的附加数据，这些数据会指向指向下一个元素的指针。

有许多变体，单链表，双链表，树，地图，哈希和各种专业定制和混合结构。如果你真的坚持C而不是C ++，那么遗憾的是你没有得到C ++标准库的好处，它以可重用和模板的形式为你实现了很多这些。然而，关于这些数据结构的文章和书籍无穷无尽，如果你想实现自己的话，你可以搜索一下。

所有这些的基本原则是你可以分配新元素而不必总是重新分配所有现有元素，然后简单地将新元素链接到结构中。

结构在元素上形成一个或多个排序（在数学意义上），以便代码可以以通用方式迭代它们（访问结构的每个元素），无论有多少或添加或删除特定元素。

每个结构在存储方面都有成本和收益链接数据的开销，搜索速度，插入速度，删除速度以及可能需要的任何类型重新索引或重新分配的频率。

选择正确的数据结构绝对是成功的关键。你写的那种应用程序，所以很多研究都会得到回报。

I am creating a small vector paint application. (using pure Win32 API and C)

Up to now it can just draw boxes on the window. A box takes a typedef struct to store its data (X and Y pos, width and height..). An array to store these data (typedef struct) is dynamically allocated.

I used malloc() to allocate memory for that array at the first time.
Whenever a new box is created that array is expanded using realloc(). And the data for the new box is assigned as data[last_box] = new_box.

After they are passed to WM_PAINT to begin panting.

This design works fine ! But the questions are,
1. Is this a good practice, reallocating every time a new box is created.
2. Are there any alternatives, if so which is the best.

解决方案

In answer to 1. No this is not a very good idea. Once you get up to a few thousand elements in your drawing this will become very slow. Constant reallocation may also fragment memory causing your effective memory usage to be many times higher than necessary.

In answer to 2. Yes there are many alternatives. All of these are based on the idea of linked data structures. Each element, vector or rectangle in your case has additional data associated with it which ammounts to a pointer to the next element.
There are many variations, singly linked lists, doubly linked lists, trees, maps, hashes and all kinds of specialized custom and hybrid structures. If you really are sticking to C rather than C++ then sadly you don''t get the benefit of the C++ standard library which implements a lot of these for you in reusable and template form. However there are endless articles and books on these data structures that you can search up if you want to implement your own.
The fundamental principles of all of them are that you can allocate new elements without always having to reallocate all the existing ones and then simply link the new one into the structure.
The structure forms one or more orderings (in the mathematical sense) over the elements so that the code can iterate over them (visit each element of the structure) in a generic way regardless of how many there are or the addition or removal of specific elements.
Each structure has costs and benefits in terms of storage overhead for the linkage data, search speed, insertion speed, deletion speed and the frequency of any kind of reindexing or reallocation that may be needed.
Choosing the right data structures is absolutely key to the success of the kind of application you''re writing so lots of research will pay off.

这篇关于重新分配...何时和最好的方式。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！