分享/交流: 数据结构实现

[Eplankton]

https://github.com/Eplankton/nut-struct

[Sunrisepeak]

https://github.com/Eplankton/nut-struct

今天太晚了，明天我看看代码

[Sunrisepeak]

https://github.com/Eplankton/nut-struct

以std基本的数据结构ADT来实现的mini-std, 感觉一个实验作业完成这么多内容还挺不容易的

[Eplankton]

还行吧，不写到这个程度这门课根本过不了

[Sunrisepeak]

目前DStruct 的目标是:

• 无依赖, 库 及 操作系统 环境, 只使用语言特性去支撑 裸机/嵌入式RT-Kernel/正常操作系统 等不同环境
• 易用, 简化数据结构接口 - 做一个较好&统一的接口规范, 具体数据结构的实现面向用户的通用接口准从统一接口规范 或其 子集
• 丰富的数据结构, 会去实现 有具体场景但又不那么通用的数据结构(例如: 带滑动窗口的循环队列, 步长是5, 数据宽度是10)
• 数据结构 属性定制化, 尝试把一些固有操作给抽象"ADT", 开放"固有属性"接口(例如: Vector的 分配规则, 分配器, 或则像上面说的 窗口大小(5bytes), 数据宽度(10bytes)....), 还有一点DStruct基本不会有private属性和方法, 封装性用protected来做。提供, 固有属性, 组合方式, 继承方式, 适配器方式 等 方向上 定义的可能性

只不过目前DStruct 还在初级阶段, 在搭建基层框架, 规范。

[Eplankton]

去看看ETL，一个专门为嵌入式定制的STL，和你这个很像，而且兼容STL的接口

[Sunrisepeak]

看了下 这个库 挺不错的(已star), 使用编译期来确定容器内存, 不依靠动态内存分配。

仅从无环境依赖的角度看(目标之一): DStruct 和 ETL 要解决的问题是差不多的
但解决的方式略不同

• ETL: 编译期确定最大SIZE的静态容器
• DStruct: 通过分配器规范(AllocSpec), 解耦数据结构 和 内存分配 的细节, 这代表内存的来源是操作系统或还是全局静态数据区域还是函数的调用栈上 或裸机物理内存 都是可以的, 或者说不关心内存来源 的方式来处理的

从编译期确定内存的方式

目前提供了一个 简单的静态内存分配器(SMA)作为分配器实现的例子
https://github.com/Sunrisepeak/DStruct/blob/main/memory/StaticMemAllocator.hpp

SMA分配器使用的例子1 - 这中就可以等同ETL 的方式 编译器确定这个 容器的最大SIZE
https://github.com/Sunrisepeak/DStruct/blob/dac34cca8417a32e85b34cc78de57ee16f622e66/examples/static_mem_allocator.cpp#L9C1-L41C2

SMA分配器使用的例子2 - 作为全局默认分配器 这个也是编译器确定内存大小, 但为所有容器提供内存支持
https://github.com/Sunrisepeak/DStruct/blob/main/port/static-memory/sma-dstruct-port.hpp

ETL 是包含编译期确定大小的静态容器及其他相关STL功能, DStruct 定位到数据结构(通用数据结构(std中的容器) + 特殊场景的数据结构) 算是交集

[Sunrisepeak]

后面我也会写几篇分配器相关的文档

https://github.com/Sunrisepeak/DStruct/pull/30/files#diff-eccc2c6184c0587652f5020960dc0cba857a3488ad3005c9bfe70beab887df31

[Sunrisepeak]

目前还有个关于数据结构的工作是 DSVisual (目前也是初期阶段
在基于DStruct做 数据结构的可视化, 目标是开发者(特别是初学者)像正常使用 数据结构库 或 std中的数据结构 一样 写自己的程序, 然后把这个数据结构及程序中运行时的操作及数据变化 给可视化出来

感兴趣的话可以了解了解
https://github.com/Sunrisepeak/DSVisual
https://www.bilibili.com/video/BV1xp4y1L7Vz/?spm_id_from=333.999.0.0&vd_source=eac75885a69b523024571c4df766896f