-
关于OpenFOAM模板类"List"的翻译:
虽然在STL中list对应的数据结构是链表,但是OpemFOAM中List对应的数据结构是数组容器,在OF List的基类UList的定义中有:
//- Number of elements in UList label size_; //- Vector of values of type T T* __restrict__ v_; // Private Member Functions //- Disallow default shallow-copy assignment //
List中对v_的内存分配操作为:
template<class T> inline void Foam::List<T>::alloc() { if (this->size_ > 0) { this->v_ = new T[this->size_]; } }
实际在堆上为v_分配了大小为(this->size)*(size_of(T))的连续空间,因此能够根据下标访问元素,插入时先重新分配size+1的空间之后拷贝,复杂度O(n)
实际OpenFOAM中链表容器的基类为DLListBase(双向链表)和SLListBase(单向链表),位于src\OpenFOAM\containers\LinkedLists目录下
以单向链表为例
void Foam::SLListBase::insert(SLListBase::link* a) { nElmts_++; if (last_) { a->next_ = last_->next_; } else { last_ = a; } last_->next_ = a; }
插入时将链表尾部指针指向新元素,复杂度为常数。访问使用内部迭代器遍历,复杂度O(n),
在《OpenFOAM用户指南-5.0》中东岳老师将继承自List模板的类翻译成链表,个人建议将其翻译成数组或者列表更合理,这样能够减少使用者定义底层数据时的困惑。