casyup.me@outlook.com

0%

other/vector

Posted on

emm…

网络看过了, 多线程看过了, 操作系统看过了, mysql看过了, linux看过了, 数据结构和算法也看过了…

大多需要的东西我都有看过 (虽然还需大量训练💪), 想了想, 是时候看源码了.

第一次看源码应该是在一年前, 当时结合<STL源码剖析>, 没看几页就歇气了, 不知道那里去找源码. 也不知道怎么入手. 随着自己不断进步, 这些问题也变得可以解决了.

prepare

首先, 源码选用哪套呢? 想了想还是 boost 好了.

然后, 书籍的话, 就不读之前那本书了, 网上搜了相关书籍, 很少, 看了看感觉并不适合. 所以选用了 boost 的官方文档.

一开始就遇到了之前的问题: 不知道从哪里开始. 想去看看 vector 的实现. 但是一搜文档, 有很多出都有 vector 关键字.

脑壳疼…

好在这个问题可以通过官方文档上来解决:

找到相关的位置就好了, 所以, 就先从 vector 开始吧 :)

vector

按照文档记载, vector 的默认容器类型是 unbounded_array. 这点 boost 做得不太友好. 因为这个默认类型在 fwd.hpp 文件中才能看到. (在文件中有这么一行 “fwd.hpp is essentially used to forward declare the main types” 应该在很多地方都会有)

vector 所继承的父类经查看, 并无太大的实质改变.

它的名字或许有歧义, 因为容器是由 A 决定的, 其父类提供的是一些功能性函数, 并无实际数据成员.

一开始是一些类型的定义:

其中比较令人在意的是:

  • difference_type

    1
    2
    3
    4
    BOOST_UBLAS_INLINE
         reference operator [] (difference_type n) const {
         return *(it_ + n);
    }

    这个类型实际是元素距离类型? 那不应该叫 distance_type 么? 好奇怪的命名…

  • type_traits

    应该是一些类型特性相关的东西.

  • vector_reference, closure_type, const_closure_type

    这貌似是一个封装了自身内部容器类型的类.

  • storage_category

    这好像是一个以类类型为识别的标识, emm… 用 enum 会不会好点?

接下来就是一些普通的成员函数, 其中几个比较在意的: 

1
2
3
4
5
6
7
8
9
10
11
template<class AE>
BOOST_UBLAS_INLINE
vector (const vector_expression<AE> &ae):
	vector_container<self_type> (),
	data_ (ae ().size ()) {
    vector_assign<scalar_assign> (*this, ae);
}

// vector_expression 就是 vector 表达式, 其包含 + - * / 四则运算等等
// 可以参考 vector_expression.hpp 文件.
// 我也不是十分清楚这是啥玩意 = = , 看起来是封装了一些列运算的类.

还有一个比较奇怪的 resize

1
2
3
4
5
6
7
8
9
10
BOOST_UBLAS_INLINE
void resize (size_type size, bool preserve = true) {
	if (preserve)
		data ().resize (size, typename A::value_type ());
	else
		data ().resize (size);
}

// preserve 决定了数据是否保留, 不保留的话会截断. 
// 很多函数都只有2, 3行, vector 可以理解为一个包装, 底层数据的控制在其 container 内.

比较好奇 data 哪里来的, vector 只有 data_ 这一个成员. 结果看到 = =

data 是 public 的, 这里加 data() 感觉有点多余. 或者说, 存在它说的 “very specific case” ?

在其他地方也有看到调用的是 data(), 而并非 data_ . 或许是为了功能性? 

1
2
3
4
5
6
7
BOOST_UBLAS_INLINE
void clear () {
	std::fill (data ().begin (), data ().end (), value_type/*zero*/());
}

// 它调用的是 std 的 fill 函数, 其自身也实现了一个 std 的 fill, 不过是一个比较普通的 fill
// memset 是否会更好?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<class C>          // Container assignment without temporary
BOOST_UBLAS_INLINE
vector &operator = (const vector_container<C> &v) {
    resize (v ().size (), false);
    assign (v);
    return *this;
}

template<class AE>
BOOST_UBLAS_INLINE
vector &operator = (const vector_expression<AE> &ae) {
    self_type temporary (ae);
    return assign_temporary (temporary);
}

// 这是个赋值操作符重载, 但是, 问题是
// 是否可以规避部分 resize 操作? 比如 v 长度为 10, 那么至多 10 个元素不需要 resize
// 交给后续的 assign 就好了
// 还要注意的是, expression 的赋值有临时值, 但 container 没有, 虽然这很正常.

template<class AE>
BOOST_UBLAS_INLINE
vector &assign (const vector_expression<AE> &ae) {
	vector_assign<scalar_assign> (*this, ae);
	return *this;
}

// ... 啊啊啊 绕来绕去, 要吐了 = =
// 不过这里有一个收获就是, 之前为什么用类类型当 tag, 明明只是一个空数据结构

请看这里! 它使用了这个类类型来重载模板.

不过… 我记得有用值来指定的方式 = =.

我突然发现一个很严肃的问题, 上述的部分函数中, 返回值直接是 vector, 而并非 vector<T, A> …

而我试了一下, 发现是可以编译通过的 = =, 而 google 上几乎示例都告诉我要加 , 我是不是该再看一下模板?

iterator

boost 将 vector 的 iterator 实现为内部类的形式.

1
2
3
// Use the storage array iterator
typedef typename A::const_iterator const_subiterator_type;
typedef typename A::iterator subiterator_type;

它使用的是底层容器的 iterator, 它和 vector 类似, 也是一个包装类. 看来一切的核心在底层容器中

1
2
3
4
5
6
7
/// Serialize a vector into and archive as defined in Boost
/// \param ar Archive object. Can be a flat file, an XML file or any other stream
/// \param file_version Optional file version (not yet used)
     template<class Archive>
     void serialize(Archive & ar, const unsigned int /* file_version */){
         ar & serialization::make_nvp("data",data_);
     }

哦哦哦, 不愧是 boost, 很方便嘛.

unbounded_array

1
2
3
// Storage types
template<class T, class ALLOC = std::allocator<T> >
class unbounded_array;

(ノ｀Д)ノ 你…

(顺便, 在这段期间我折腾了一下 IDE, Clion, xcode, visual studio. 最后还是 vs 好. 对于这种源码级别的符号解析, 其他 IDE 好像都不怎么聪明. 但是很可惜 vs mac 的支持并不好. 而且没有 vs 插件)

1
2
3
4
typedef const T *const_pointer;
typedef T *pointer;
typedef const_pointer const_iterator;
typedef pointer iterator

所以迭代器只是一种概念, 一种机制, 其内部还是指针.

1
2
3
ALLOC alloc_;
size_type size_;
pointer data_

data_ 应该就是数据存储所在.

1
2
3
4
5
6
7
BOOST_UBLAS_INLINE
void swap (unbounded_array &a) {
	if (this != &a) {
	std::swap (size_, a.size_);
	std::swap (data_, a.data_);
	}
}

所以, swap 是轻量级的, 只有内部元素交换.

老夫突然发现一件很要命的事情…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BOOST_UBLAS_INLINE
reference insert_element (size_type i, const_reference t) {
	return (data () [i] = t);
}

BOOST_UBLAS_INLINE
void erase_element (size_type i) {
	data () [i] = value_type/*zero*/();
}

reference operator [] (size_type i) {
    BOOST_UBLAS_CHECK (i < size_, bad_index ());
    return data_ [i];
}

这是 vector 的插入和删除元素, 以及插入元素内部 [] 的重载… 这…

boost 的 vector 就是数组… 还是不会自动变长的那种…

是的, 再三对比文档和源码, 插入只有 insert_element 一处. 而插入时会先进行界限判定, 如果越界, 则直接报错…

想不到你是这样的 boost. 我看错你了!

啊, 不知不觉这个文档已经要初次结尾了呢 :) 虽然后续应该有很多补充内容, 比如标准的 vector 是如何做的. 底层其他容器的特性…

现在还剩的是: 内存是怎么分配的. 其实, 比意料之中的还要简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
_NODISCARD _DECLSPEC_ALLOCATOR _Ty* allocate(_CRT_GUARDOVERFLOW const size_t _Count) {
    return static_cast<_Ty*>(_Allocate<_New_alignof<_Ty>>(_Get_size_of_n<sizeof(_Ty)>(_Count)));
}
// 调用了 _Allocate 

template <size_t _Align, class _Traits = _Default_allocate_traits,
    enable_if_t<(!_HAS_ALIGNED_NEW || _Align <= __STDCPP_DEFAULT_NEW_ALIGNMENT__), int> = 0>
_DECLSPEC_ALLOCATOR void* _Allocate(const size_t _Bytes) {
    // allocate _Bytes when !_HAS_ALIGNED_NEW || _Align <= __STDCPP_DEFAULT_NEW_ALIGNMENT__
#if defined(_M_IX86) || defined(_M_X64)
    if (_Bytes >= _Big_allocation_threshold) { // boost the alignment of big allocations to help autovectorization
        return _Allocate_manually_vector_aligned<_Traits>(_Bytes);
    }
#endif // defined(_M_IX86) || defined(_M_X64)

    if (_Bytes != 0) {
        return _Traits::_Allocate(_Bytes);
    }

    return nullptr;
}
// 要么执行优化版本的分配, 要么直接分配, 我们看看直接分配的就好
// 在 _Default_allocate_traits 下: 

struct _Default_allocate_traits {
    _DECLSPEC_ALLOCATOR static void* _Allocate(const size_t _Bytes) {
        return ::operator new(_Bytes);
    }

#ifdef __cpp_aligned_new
    _DECLSPEC_ALLOCATOR static void* _Allocate_aligned(const size_t _Bytes, const size_t _Align) {
        return ::operator new (_Bytes, align_val_t{_Align});
    }
#endif // __cpp_aligned_new
};

#if defined(_M_IX86) || defined(_M_X64)
constexpr size_t _Big_allocation_threshold = 4096;
constexpr size_t _Big_allocation_alignment = 32;

// 意料之外的简单(当然, 再看 new 底部就不那么简单了)