重庆专业的网站建设公司哪家好,平面设计公司起名,wordpress主页主题,太仓网页制作招聘前言#xff1a;之前看过侯老师的《STL源码剖析》但是那已经是多年以前的#xff0c;现在工作中有时候查问题和崩溃都需要了解实际工作中使用到的STL的实现。因此计划把STL的源码再过一遍。 摘要#xff1a;本文描述了llvm中libcxx的std::vector的实现。 关键字之前看过侯老师的《STL源码剖析》但是那已经是多年以前的现在工作中有时候查问题和崩溃都需要了解实际工作中使用到的STL的实现。因此计划把STL的源码再过一遍。 摘要本文描述了llvm中libcxx的std::vector的实现。 关键字vector 其他参考代码LLVM-libcxx vector是标准库中的连续存储的容器也就是容器中说任意两个索引上相邻的元素的地址也是相邻的可以通过索引随机访问。vector中的元素默认是通过堆内存管理的在进行空间分配时一般会比时机需求的空间要大即capacity_size这样能够避免在插入元素时频繁申请内存导致的性能问题如果频繁申请内存导致页置换的话还是很耗时的。
1 vector 先看下容器的定义和其他容器一样都是一个模板类。_Tp就是类型而_Allocator是进行内存管理的分配器默认分配器就是通过::operator new和::operator delete申请和释放内存的。
template class _Tp, class _Allocator /* allocator_Tp */
class _LIBCPP_TEMPLATE_VIS vectorvector的内存布局比较简单如下图有三个指针分别指向了对应的开始地址已使用部分的尾地址申请到的内存的尾地址[__begin_, __end_)之间是已经使用的内存部分[__end_, __end_cap_)是申请了但是未使用的部分保留这一部分是为了避免插入元素时频繁allocate而可能出现的性能问题。
private:pointer __begin_ nullptr;pointer __end_ nullptr;__compressed_pairpointer, allocator_type __end_cap_ __compressed_pairpointer, allocator_type(nullptr, __default_init_tag());构造和销毁 vector的构造比较简单就是先通过allocator申请一块内存然后通过for循环逐个构造对象。构造时通过for循环实现由于没有利用CPU的一些SMID指令的优化必然效率不是很好。
vector(size_type __n, const value_type __x, const allocator_type __a) : __end_cap_(nullptr, __a){std::__debug_db_insert_c(this);if (__n 0){__vallocate(__n);__construct_at_end(__n, __x);}
}vector_Tp, _Allocator::__construct_at_end(size_type __n, const_reference __x){_ConstructTransaction __tx(*this, __n);const_pointer __new_end __tx.__new_end_;for (pointer __pos __tx.__pos_; __pos ! __new_end; __tx.__pos_ __pos) {__alloc_traits::construct(this-__alloc(), std::__to_address(__pos), __x);}
}销毁就比较直接通过一个包装器__destroy_vector先clear再调用deallocate释放内存。
__vec_.__clear();
__alloc_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.capacity());;clear clear函数只会针对析构容器中的每一个函数并不会释放当前容器中的内存。因此在进行容器释放时需要注意如果期望释放内存的话可以通过vector().swap(vec)的方式或者在调用clear之后调用shrink_to_fit 调整内存大小。
void clear() _NOEXCEPT{size_type __old_size size();__clear();__annotate_shrink(__old_size); //看源码里面什么也不会做std::__debug_db_invalidate_all(this);
}void __clear() _NOEXCEPT {__base_destruct_at_end(this-__begin_);}
void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {pointer __soon_to_be_end this-__end_;while (__new_last ! __soon_to_be_end) //依然是一个完整的循环析构__alloc_traits::destroy(__alloc(), std::__to_address(--__soon_to_be_end));this-__end_ __new_last;
}push_back push_back时如果当前有足够的的大小则会在尾部构建一个对象扩容的大小是按照现有大小的2倍来即std::min(max_size(), std::max(current_cap 1, 2 * current_cap))简单的理解就是在条件允许的情况下扩容2倍。
void vector_Tp, _Allocator::__push_back_slow_path(_Up __x){allocator_type __a this-__alloc();//__split_buffer就是一个包装器__split_buffervalue_type, allocator_type __v(__recommend(size() 1), size(), __a);// __v.push_back(std::forward_Up(__x));__alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward_Up(__x));__v.__end_;__swap_out_circular_buffer(__v);//这个函数没有干什么就是将__v中的size设置给当前的vector
}emplace_back emplace_back和push_back基本相同都是向容器中插入元素如果对于插入vector::value_type类型的对象二者是没有区别的push_back也实现了右值的重载不存在push_back对于右值会多次拷贝的情况。主要的区别是emplace_back通过可变参数模板将参数直接传递给了构建器也就意味着同样的代码emplace_back直接在对应的内存上构建对象而相比之下push_back是先构建再拷贝。
void vector_Tp, _Allocator::emplace_back(_Args... __args)resize resize的实现比较直接内存小了就扩容大了就析构但是并不释放内存。
void vector_Tp, _Allocator::resize(size_type __sz, const_reference __x){size_type __cs size();if (__cs __sz)this-__append(__sz - __cs, __x);else if (__cs __sz)this-__destruct_at_end(this-__begin_ __sz);//只会析构对象不会释放内存
}shrink_to_fit
vectorbool, _Allocator::shrink_to_fit() _NOEXCEPT{if (__external_cap_to_internal(size()) __cap()){vector(*this, allocator_type(__alloc())).swap(*this);}
}vectorbool基本上被建议放弃使用了所以就不深入了。 2 array array的实现比较简单就是一个简单的栈数组的包装器。就不详细描述了。
template class _Tp, size_t _Size
struct _LIBCPP_TEMPLATE_VIS array
{// types:typedef array __self;typedef _Tp value_type;typedef value_type reference;typedef const value_type const_reference;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type* pointer;typedef const value_type* const_pointer;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef _VSTD::reverse_iteratoriterator reverse_iterator;typedef _VSTD::reverse_iteratorconst_iterator const_reverse_iterator;_Tp __elems_[_Size];
};3 参考文献
stackoverflow——push_back vs emplace_backProposed Wording for Placement Insert
