STL_vector

发表于 | 分类于
字数统计: 5.1k | 阅读时长 ≈ 24
富士山 -- 日本

STL_vector

1. 内部结构

将 stl_vector.h 分为了四个部分：

  • 头文件
  • 类型别名声明
  • 数据成员
  • 成员函数

1.1 头文件

1
2
3
#include <cstddef>      	// ptrdiff_t
#include "allocator.h"		// allocate
#include "uninitialized.h"	// uninitialize_fill()....

1.2 类型别名声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public:  // alias declarartions
    // 类型别名
    using value_type = T; 
    using pointer = value_type *;
    using iterator = value_type *;  // iterator is raw pointer
    using const_iterator = const value_type *;
    using reverse_iterator = __reverse_iterator<iterator>;
    using const_reverse_iterator = __reverse_iterator<const_iterator>;
    using reference = value_type &;
    using const_reference = const value_type &;
    using size_type = size_t;
    using difference_type = ptrdiff_t;

private:  // allocate and construct aux functions
    using data_allocator = Alloc;   // Alloc = simpleAlloc<T>

1.3 数据成员

1
2
3
4
5
6
private:  // data member
    // iterator to indicate the vector's memory location
    // 一共有三个数据成员，迭代器， 三个指针 所以 sizeof(vector) --> 12 bytes 
    iterator start;
    iterator finish;
    iterator end_of_storage;

1.4 成员函数

成员函数分为两种。更多的细节见下文。

对外可调用的接口函数（ public ）：

  • 构造函数，析构函数
  • 拷贝赋值运算符，移动赋值运算符
  • getter ，setter
  • 修改 size 和 capacity 的接口
  • 比较运算符
  • push 和 pop 操作
  • erase，insert，assign 操作

私有成员函数，实现接口函数功能（ private ）

2. 成员函数

2.1 构造函数，析构函数

函数声明或定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public:  // ctor && dtor
    vector() : start(nullptr), finish(nullptr), end_of_storage(nullptr) {}

	// 传入了 value_type 类型的对象，默认值是value_type对应的默认值  
    explicit vector(size_type n) { fill_initialize(n, value_type()); }          
	vector(size_type n, const value_type &value) { fill_initialize(n, value); }

    template <class InputIterator>
    vector(InputIterator first, InputIterator last) {                            
        initialize_aux(first, last, _is_integer_t<InputIterator>());  
    }

    vector(std::initializer_list<T>);   // vector{....} 
    vector(const vector &);             // 拷贝构造函数
    vector(vector &&) noexcept;         // 移动构造函数 

    ~vector() {                         // 析构函数 
        // destory in "construct.h"
        destroy(start, finish);         // 先对对象析构
        deallocate();                   // 后释放内存空间
    }

注意：

行: 5，传入参数为 value_type() 是一个对象，有默认值。

行: 5,6，调用 fill_initialize() 函数初始化，其内部使用 allocate_and_fill() 函数。

行: 8-11，传入参数是两个迭代器，会调用 initialize_aux()，会利用萃取机获得第三个参数。

行: 12-13，都调用了 allocate_and_copy() 函数，包含分配内存和 copy 操作。

行: 15，使用了浅拷贝，并将传入对象指针置空。

fill_initialize()

1
2
3
4
5
6
7
void fill_initialize(size_type n, const value_type &value) {
    // 调用 allocate_and_fill 函数，先分配内存，然后进行初始化操作
    start = allocate_and_fill(n, value);
    // 为 finish 和 end_of_storage 赋值
    finish = start + n;
    end_of_storage = finish;
}

allocate_and_fill()

1
2
3
4
5
6
7
iterator allocate_and_fill(size_type n, const value_type &value) {
    // 调用 allocated 分配内存，返回指针
    iterator result = data_allocator::allocate(n);
    // 对分配的内存进行初始化，调用 uninitialized_fill_n
    MiniSTL::uninitialized_fill_n(result, n, value);
    return result;
}  // 以上两个函数见 Allocator

initialize_aux()

_true_type 和 _false_type 见 Iterator

1
2
3
4
5
6
7
8
9
10
11
12
// _true_type
template <class Integer>
    void initialize_aux(Integer n, Integer val, _true_type) {
    fill_initialize(static_cast<size_type>(n),
                    static_cast<value_type>(val)); // 调用 fill_initialize
}												   // 内部调用 allocate_and_fill
// _false_type
template <class InputIterator>
    void initialize_aux(InputIterator first, InputIterator last, _false_type) {
    start = allocate_and_copy(first, last);  // 调用 allocate_and_copy
    finish = end_of_storage = start + MiniSTL::distance(first, last);
}

allocate_and_copy()

1
2
3
4
5
6
7
template <class InputIterator>  /* 分配内存并拷贝对应分为内的值，返回头迭代器 */
    iterator allocate_and_copy(InputIterator first, InputIterator last) {
    size_type n = MiniSTL::distance(first, last);
    iterator result = data_allocator::allocate(n);
    MiniSTL::uninitialized_copy(first, last, result);
    return result;
}

注意：

_true_type 代表了接受的为 int，_false_type 代表了接受的是迭代器。内部分别对应了使用 uninitialized_fill_n() 还是 uninitialized_copy()。

vector(const vector &)

1
2
3
4
5
6
7
template <class T, class Alloc> /* 拷贝构造函数 */
inline vector<T, Alloc>::vector(const vector &rhs) {
    start = allocate_and_copy(rhs.begin(), rhs.end());
    /* 可以发现拷贝构造函数只是分配拷贝元素的内存，finish == end_of_storage 
       这也就解释了 shrink_to_fit 函数的实现 */
    finish = end_of_storage = start + rhs.size();
}

vector(std::initializer_list<T>)

1
2
3
4
5
template <class T, class Alloc> /* 拷贝构造函数（初始化链表）*/
inline vector<T, Alloc>::vector(std::initializer_list<T> il) {
    start = allocate_and_copy(il.begin(), il.end());
    finish = end_of_storage = start + il.size();
}

vector(vector &&) noexcept

1
2
3
4
5
6
7
8
9
template <class T, class Alloc> /* 移动构造函数 */
inline vector<T, Alloc>::vector(vector &&rhs) noexcept {
    /* 交换指针, 浅拷贝 */
    start = rhs.start;
    finish = rhs.finish;
    end_of_storage = rhs.end_of_storage;
    /* 原指针置空 */
    rhs.start = rhs.finish = rhs.end_of_storage = nullptr;
}

2.2 拷贝赋值运算符，移动赋值运算符

vector &operator=(const vector &)

1
2
3
4
5
6
template <class T, class Alloc> /* 拷贝赋值运算符 */
inline vector<T, Alloc> &vector<T, Alloc>::operator=(const vector &rhs) {
    vector temp(rhs); /* 内部调用拷贝构造函数 */
    swap(temp);
    return *this;
}

vector &operator=(vector &&) noexcept

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T, class Alloc> /* 移动赋值运算符 */
inline vector<T, Alloc> &vector<T, Alloc>::operator=(vector &&rhs) noexcept {
    if (this != &rhs) { /* 自赋值的判断 */
        destroy_and_deallocate(); /* 先析构释放原内存 */
        /* 浅拷贝 */
        start = rhs.start;
        finish = rhs.finish;
        end_of_storage = rhs.end_of_storage;
        /* 将 rhs 指针置 nullptr */
        rhs.start = rhs.finish = rhs.end_of_storage = nullptr;
    }
    return *this;
}

注意：移动赋值运算符需要考虑自赋值！

2.3 getter

主要用来获取 vector 的一些数据，皆是 const 类型成员函数。

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
public:  // getter
    const_iterator begin() const noexcept { return start; }  
    const_iterator end() const noexcept { return finish; }
    const_iterator cbegin() const noexcept { return start; } 
    const_iterator cend() const noexcept { return finish; }
    const_reverse_iterator crbegin() const noexcept {
        return const_reverse_iterator(finish);
    }
    const_reverse_iterator crend() const noexcept {
        return const_reverse_iterator(start);
    }
    // TODO:
    // have no empty check
    const_reference front() const noexcept { return *begin(); }
    const_reference back() const noexcept { return *(end() - 1); }
    // TODO:
    // have no boundary check and don't use proxy
    const_reference operator[](const size_type n) const noexcept {
        return *(start + n);
    }
    size_type size() const noexcept {
        return static_cast<size_type>(finish - start);
    }
    size_type capacity() const noexcept {
        return static_cast<size_type>(end_of_storage - start);
    }
    bool empty() const noexcept { return start == finish; }

2.4 setter

与 getter 相呼应，提供一些用户可以获取并修改参数的接口。

1
2
3
4
5
6
7
8
public:  // setter
    iterator begin() noexcept { return start; }
    iterator end() noexcept { return finish; }
    reverse_iterator rbegin() noexcept { return reverse_iterator(finish); }
    reverse_iterator rend() noexcept { return reverse_iterator(start); }
    reference operator[](const size_type n) noexcept { return *(start + n); }
    reference front() noexcept { return *begin(); }
    reference back() noexcept { return *(end() - 1); }

2.5 修改 size 和 capacity 的接口

1
2
3
4
5
6
7
8
9
public:  // interface for size and capacity
    void resize(size_type, const value_type &); /* 修改 size */
    void resize(size_type new_size) { resize(new_size, value_type()); }
    void reserve(size_type);                    /* 修改 capacity */
    void shrink_to_fit() noexcept {             /* 将最大容量减少到它所需要的容量 */
        vector temp(*this);  /* 调用拷贝构造函数，注意拷贝构造函数只分配拷贝的元素所需的内存
                                所以此时 finish == end_of_storage */
        swap(temp); /* 交换数据 */
    } /* temp 在离开作用域后自动析构释放 */

注意：

行: 3，利用 value_type() 调用 resize(n, val) 版本重载。

行: 5-9，shrink_to_fit() 主要利用拷贝构造函数来实现。

C++ shrink_to_fit() 的实现

void resize(size_type, const value_type &)

1
2
3
4
5
6
7
8
9
template <class T, class Alloc>
inline void vector<T, Alloc>::resize(size_type new_size, const value_type &value) {
    /* 如果 new_size 小于当前 size 直接 erase 多余的即可*/
    if (new_size < size())
        erase(begin() + new_size, end());
    else
    /* 否则在后面填充 value 到指定 size 即可，调用 fill_insert 函数 */
        fill_insert(end(), new_size - size(), value);
}

注意：内部可能调用 erase() ，fill_insert() ，见下文。

void reserve(size_type)

1
2
3
4
5
6
7
8
9
10
11
12
template <class T, class Alloc> 
inline void vector<T, Alloc>::reserve(size_type new_capacity) {
    /* 如果修改成更小值，就什么都不操作 */
    if (new_capacity <= capacity()) return;
    /* 否则分配一个 new_capacity 的内存，并将当前对象都拷贝过去，并析构释放当前对象 */
    T *new_start = data_allocator::allocate(new_capacity);
    T *new_finish = MiniSTL::uninitialized_copy(start, finish, new_start);
    destroy_and_deallocate(); // 包含 destroy, deallocate 等操作
    start = new_start;
    finish = new_finish;
    end_of_storage = start + new_capacity;
}

注意：如果修改成更小值，什么都不操作，否则重新分配内存，并拷贝过去，释放就对象。

2.6 比较运算符

1
2
3
4
5
public:  // compare operator(member function)
    bool operator==(const vector &) const noexcept;
    bool operator!=(const vector &rhs) const noexcept {
        return !(*this == rhs); /* 调用 == 操作符 */
    }

注意：行: 3-5，可以发现不等于操作是基于等于操作实现的。

bool operator==(const vector &) const noexcept

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T, class Alloc>
bool vector<T, Alloc>::operator==(const vector &rhs) const noexcept {
    /* 如果 size 不同，直接返回 false */
    if (size() != rhs.size()) {
        return false;
    } else {
        iterator ptr1 = start;
        iterator ptr2 = rhs.start;
        /* 同时遍历，只要有一个元素值不相同就直接返回 false */
        for (; ptr1 != finish && ptr2 != rhs.finish; ++ptr1, ++ptr2)
            if (*ptr1 != *ptr2) return false;
        return true;
    }
}

2.7 push_back() 和 pop_back()

1
2
3
4
5
6
public:  // push && pop
    void push_back(const value_type &);
    void pop_back() {
        --finish;        /* 先 finish-- ，为之前 end() 前面指向的对象，也即是最后的元素*/
        destroy(finish); /* 然后析构 finish 处对象，不是放内存 */
    }

注意：行: 2-6，pop_back() 操作先 finish--，才可以对 finish 析构。

void push_back(const value_type &)

1
2
3
4
5
6
7
8
9
10
11
template <class T, class Alloc>
inline void vector<T, Alloc>::push_back(const value_type &value) {
    /* capacity 足够，直接在尾端使用构造函数即可 */
    if (finish != end_of_storage) {
        construct(finish, value);
        ++finish;
    }
    // 否则使用 insert_aux 接口，内部包含重新分配内存....
    else
        insert_aux(end(), value);
}

注意：内部可能调用 insert_aux() ，见下文。

2.8 erase 操作

1
2
3
4
5
6
public:  // erase
    iterator erase(iterator, iterator); /* 删除一串 */
    iterator erase(iterator position) { /* 删除一个，内部调用前者 */
        return erase(position, position + 1); 
    } 
    void clear() { erase(begin(), end()); } /* 全删 */

注意：行: 3-5,6，内部调用 iterator erase(iterator, iterator)

iterator erase(iterator, iterator)

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T, class Alloc>
inline typename vector<T, Alloc>::iterator // 返回值
    vector<T, Alloc>::erase(iterator first, iterator last) {
    /* 将 [last, finish) 数据拷贝到 [first, first + (finish - last)) 
       并返回 new_finish --> i */
    iterator i = MiniSTL::copy(last, finish, first);
    /* 析构 [i, finish) */
    destroy(i, finish);
    /* 更新 finish */
    finish -= (last - first);
    /* 返回的是 first 这个 原 last 后一个元素*/
    return first;
}

更直观见下图所示：

图 1 局部区间的清楚操作

《STL源码剖析》 – P123 - P124

2.9 insert 操作

1
2
3
4
5
6
7
8
public:  // insert
    iterator insert(iterator);                      /* 内部调用 insert */
    iterator insert(iterator, const value_type &);  /* 内部可能调用 insert_aux */
    template <class InputIterator> 					
    void insert(iterator pos, InputIterator first, InputIterator last) {
        insert_dispatch(pos, first, last, _is_integer_t<InputIterator>()); 
        /* 内部调用 fill_insert */
    }

注意：

行: 2，内部调用 iterator insert(iterator, const value_type &);

行: 5-8，传入参数是三个迭代器，内部调用 insert_dispatch()，会利用萃取机获得第四个参数。

iterator insert(iterator, const value_type &)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T, class Alloc>
inline typename vector<T, Alloc>::iterator 
vector<T, Alloc>::insert(iterator position, const value_type &value) {
    size_type n = position - begin();  /* position 以及之后的迭代器失效 */
    /* 如果插入位置是队尾，并且还有内存空间，
       则会在队尾直接使用构造函数来完成插入操作*/
    if (finish != end_of_storage && position == end()) {
        construct(finish, value);
        ++finish;
    } else
        /* 在队中调用 insert_aux 函数*/
        insert_aux(position, value); 
    return begin() + n;
}

void insert_aux(iterator, const value_type &)

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
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const value_type &value) {
    if (finish != end_of_storage) {  		/* 不需要扩展 */
        construct(finish, *(finish - 1));  	/* 以当前尾端元素构造一个新尾端 */
        ++finish;
        value_type value_copy = value;    	/* 保存需要插入的 value */
        MiniSTL::copy_backward(position, finish - 2, finish - 1); 
        /* 将 [position, finish - 2] 处的内存移动到 以 finish - 1 为尾部的区域 */
        *position = value_copy;    /* 修改 position 指向数据即可 */                   
    } else {  // expand
        const size_type old_size = size(); /* 此时 finish = end_of_storage 
                                              size() = capacity */
        /* 三元运算符，如果 old_size != 0 new_size 扩展两倍，否则 new_size = 1 */
        const size_type new_size = old_size ? 2 * old_size : 1;  
        iterator new_start = data_allocator::allocate(new_size);  /* 分配内存 */
        iterator new_finish = new_start;  /* 并初始化 new_start, new_finish */
        try {
            /* 先将 position 前面的数据拷贝到新内存，返回的其实是 position 迭代器*/
            new_finish = MiniSTL::uninitialized_copy(start, position, new_start); 
            construct(new_finish, value); /* 以 value 在返回迭代器处，调用构造函数 */
            ++new_finish;
            /* 最后把原 position 以及其后的元素拷贝到 new_finish 之后 */
            new_finish = MiniSTL::uninitialized_copy(position, finish, new_finish); 
        } catch (std::exception &) {
            // commit or rollback
            /* 如果构造失败，回滚，并抛出异常 */
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, new_size);
            throw;
        }
        /* 对原来的内存进行析构和释放内存 */
        destroy_and_deallocate();
        /* vector 数据成员更新为新的值 */
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + new_size;
    }
}

该函数实现，插入一个数。具体的实现见注释。

insert_dispatch()

1
2
3
4
5
6
7
8
9
10
11
/* _true_type 型别，使用 fill_insert */
template <class Integer>
    void insert_dispatch(iterator pos, Integer n, Integer value, _true_type) {     
    fill_insert(pos, static_cast<int>(n), value_type(value));
}
 /* _false_type 型别,使用 range_insert */
template <class InputIterator>
    void insert_dispatch(iterator pos, InputIterator first, InputIterator last,     
                         _false_type) {
    range_insert(pos, first, last, iterator_category_t<InputIterator>());
}

与前文相同，_true_type 主要针对 int，_false_type 主要针对迭代器，分别采用 fill_insert() 和 range_insert()。而后者会利用到萃取机推导第四个参数。

fill_insert()

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
template <class T, class Alloc>
void vector<T, Alloc>::fill_insert(iterator position, size_type n, const value_type &value) {
    if (n) {  
        // needn't expand
        if (static_cast<size_type>(end_of_storage - finish) >=  n) {  
            value_type value_copy = value;  /* 保存需要插入的值 */
            /* 求出插入位置及其后面有多少元素 */
            const size_type elems_after = finish - position;  
            iterator old_finish = finish;   /* 保存当前 finish */
            if (elems_after > n) {          /* 如果后面的元素个数大于 n */
			/* 1. 将[old_finish - n, old_finish) 内元素
			   拷贝到 [old_finish, old_finish + n) */
                MiniSTL::uninitialized_copy(finish - n, finish, finish);
                finish += n;
            /* 2. 将 [position, oid_finish - n] 内元素
               移动到 [position + n, old_finish] */
                MiniSTL::copy_backward(position, old_finish - n, old_finish);
			/* 3. [position, position + n) 填充 value */
                MiniSTL::fill(position, position + n, value_copy);
            } else {
            /* 1. 在 [old_finish, old_finish + n - elems_after) 填充 value */
                MiniSTL::uninitialized_fill_n(finish, n - elems_after, value_copy);
                finish += n - elems_after;
            /* 2. 将 [position, old_finish) 内元素拷贝到 [finish, old_finish + n) */
                MiniSTL::uninitialized_copy(position, old_finish, finish);
                finish += elems_after;
            /* 3. 将 [position, old_finish) 内元素填充为 value */
                MiniSTL::fill(position, old_finish, value_copy);  // complement
            }
        } else {  // expand
            const size_type old_size = size();
            const size_type new_size = old_size + MiniSTL::max(old_size, n);
            iterator new_start = data_allocator::allocate(new_size);
            iterator new_finish = new_start;
            try {
                /* 1. 复制 position 前面元素  */
                new_finish =
                    MiniSTL::uninitialized_copy(start, position, new_start);
                /* 2. 填充 n 个元素值为 value 的元素  */
                new_finish =
                    MiniSTL::uninitialized_fill_n(new_finish, n, value);
                /* 3. 复制 position 以及后面的数据到 new_finish 后  */
                new_finish =
                    MiniSTL::uninitialized_copy(position, finish, new_finish);
            } catch (std::exception &) {
                /* 如果构造失败，回滚，并抛出异常 */
                destroy(new_start, new_finish);
                data_allocator::deallocate(new_start, new_size);
                throw;
            }
            /* 对原来的内存进行析构和释放内存 */
            destroy_and_deallocate();
            /* vector 数据成员更新为新的值 */
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + new_size;
        }
    }
}

将 position 作为哨兵，可以将以上过程分为三种情况：

  • 备用空间足够

    • ① 插入点后的元素个数 elems_after 大于新增元素个数
    • ② 插入点后的元素个数 elems_after 小于等于新增元素个数

  • ③ 备用空间不足

具体的操作方式见注释，更形象的表示如下图所示：

图 2(a) 情况一
图 2(b) 情况二
图 2(c) 情况三

注意：其中的内存移动利用copy，插入使用 fill

《STL源码剖析》 – P125 - P128

range_insert()

range_insert() 的第四个参数由萃取机推导获得，有两种情况；

  • input_iterator_tag
  • forward_iterator_tag

也就对应了两种重载函数：

1
2
3
4
5
6
7
 /* 将指定范围内的元素，插入到指定位置*/
template <class InputIterator>                                                  
    void range_insert(iterator pos, InputIterator first, InputIterator last,       
                      input_iterator_tag);                                         
template <class ForwardIterator>
    void range_insert(iterator pos, ForwardIterator first, ForwardIterator last,
                      forward_iterator_tag);

两个的区别在于，input_iterator_tag 情况下没有 distance() 操作，只能单步执行 insert 操作来实现。

1
2
3
4
5
6
7
8
template <class T, class Alloc>
template <class InputIterator>
void vector<T, Alloc>::range_insert(iterator pos, InputIterator first, InputIterator last, input_iterator_tag) {
    for (; first != last; ++first) {
        pos = insert(pos, *first);   /* 内部调用 insert */
        ++pos;
    }
}

forward_iterator_tag 情况下有distance() 操作，可以提前知道插入多少个元素。采用更高效的插入方法，具体的插入方法与 fill_insert()完全相同，仅仅是插入的方式不同。具体的操作方式见 fill_insert()。

注意：

  • fill_insert()：其中的内存移动利用copy，插入使用 fill
  • range_insert() ：其中的内存移动利用copy，插入使用 copy
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
42
43
44
45
46
47
48
49
template <class T, class Alloc>
template <class ForwardIterator>
void vector<T, Alloc>::range_insert(iterator position, ForwardIterator first, ForwardIterator last, forward_iterator_tag) {
    /* 这里的操作与 fill_insert 几乎相同，只是 fill 操作 改为了 copy 操作 */
    if (first != last) {
        /* forward_iterator,可以使用 distance() 计算插入的元素个数 */
        size_type n = MiniSTL::distance(first, last);  
        /* 内存足够，不需要扩展 */
        if (static_cast<size_type>(end_of_storage - finish) >= n) {  
            const size_type elems_after = finish - position;  
            iterator old_finish = finish;
            if (elems_after > n) {
                MiniSTL::uninitialized_copy(finish - n, finish, finish);
                finish += n;
                MiniSTL::copy_backward(position, old_finish - n, old_finish);
                MiniSTL::copy(position, position + n, position);
            } else {
                ForwardIterator mid = first;
                advance(mid, elems_after);
                MiniSTL::uninitialized_copy(mid, last, finish);
                finish += n - elems_after;
                MiniSTL::uninitialized_copy(position, old_finish, finish);
                finish += elems_after;
                MiniSTL::copy(first, mid, position);
            }
        } else {  // expand
            const size_type old_size = size();
            const size_type new_size = old_size + MiniSTL::max(old_size, n);
            iterator new_start = data_allocator::allocate(new_size);
            iterator new_finish = new_start;
            try {
                new_finish =
                    MiniSTL::uninitialized_copy(start, position, new_start);
                new_finish =
                    MiniSTL::uninitialized_copy(first, last, new_finish);
                new_finish =
                    MiniSTL::uninitialized_copy(position, finish, new_finish);
            } catch (std::exception &) {
                destroy(new_start, new_finish);
                data_allocator::deallocate(new_start, new_size);
                throw;
            }
            destroy_and_deallocate();
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + new_size;
        }
    }
}

为什么STL的很多container的range version insert函数实现都有input iterator和forward iterator两个重载？

2.10 assign 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public:  // assign
    void assign(size_type n, const value_type &val) { fill_assign(n, val); }
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last) {
        /* 内部调用 assign_aux */
        assign_dispatch(first, last, _is_integer_t<InputIterator>());  
    }
    void assign(std::initializer_list<value_type> ils) { /* 初始化链表 */
        assign(ils.begin(), ils.end());
    }
	/* 拷贝赋值运算符（初始化链表）*/
    vector &operator=(std::initializer_list<value_type> ils) { 
        assign(ils);
        return *this;
    }

注意：

行: 2，内部调用 fill_assign()。

行: 4-7，传入参数是两个迭代器，内部调用 assign_dispatch()，会利用萃取机获得第三个参数。

行: 12-15，内部调用 void assign(std::initializer_list<value_type> ils) 重载函数。

行: 8-10，内部调用 void assign(InputIterator first, InputIterator last) 重载函数。

fill_assign()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T, class Alloc>
void vector<T, Alloc>::fill_assign(size_type n, const value_type &val) {
    /* 如果填充容量大于 capcity，构造一个新的 vector，并直接与当前 vector 交换 */
    if (n > capacity()) {
        vector<T, Alloc> temp(n, val);
        temp.swap(*this);
    } // temp 会在出作用域的时候释放
    /* 如果赋值容量大于目前的 size，先填充，后补全填充即可*/
    else if (n > size()) {
        MiniSTL::fill(begin(), end(), val);
        finish = MiniSTL::uninitialized_fill_n(finish, n - size(), val);
    }
    /* 如果填充的容量小于等于 size，先填充全部，之后删除多余的 */
    else
        erase(MiniSTL::fill_n(begin(), n, val), end());
}

具体的操作方式见注释。

assign_dispatch

1
2
3
4
5
// _true_type 内部调用 fill_assign()
template <class Integer>
    void assign_dispatch(Integer n, Integer val, _true_type) {
    fill_assign(static_cast<size_type>(n), static_cast<value_type>(val));
}
1
2
3
4
5
// _false_type 内部调用 assign_aux()
template <class InputIterator>
    void assign_dispatch(InputIterator first, InputIterator last, _false_type) {
    assign_aux(first, last, iterator_category_t<InputIterator>());
}

与前文相同，_true_type 主要针对 int，_false_type 主要针对迭代器，分别采用 fill_assign() 和 assign_aux()。而后者会利用到萃取机推导第三个参数。

assign_aux()

assign_aux() 的第三个参数由萃取机推导获得，有两种情况；

  • input_iterator_tag
  • forward_iterator_tag

也就对应了两种重载函数：

1
2
3
4
5
6
template <class InputIterator>
void assign_aux(InputIterator first, InputIterator last,
                input_iterator_tag);
template <class ForwardIterator>
void assign_aux(ForwardIterator first, ForwardIterator last,
                forward_iterator_tag);

两个的区别在于，input_iterator_tag 情况下没有 distance() 操作，只能单步执行 assign 操作来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T, class Alloc>
template <class InputIterator>  /* 不能使用 distance 计算赋值长度 */
void vector<T, Alloc>::assign_aux(InputIterator first, InputIterator last, input_iterator_tag) {
    iterator cur = begin();  /* cur 为当前 vector begin() */
    /* 将 [first last] 元素查覆到 begin()及其后面*/
    for (; first != last && cur != end(); ++cur, ++first) *cur = *first;
    /* 删除  end() - (last - first) 后多余的元素 */
    if (first == last)
        erase(cur, end());
    /* 如果 被赋值 vector 为空，直接调用 insert 操作 */
    else
        insert(end(), first, last);
}

forward_iterator_tag 情况下有distance() 操作，可以提前知道赋值多少个元素。采用更高效的赋值方法，具体的插入方法与 fill_assign完全相同，仅仅是插入的方式不同。具体的操作方式见注释。

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
template <class T, class Alloc>
template <class ForwardIterator>
void vector<T, Alloc>::assign_aux(ForwardIterator first, ForwardIterator last, forward_iterator_tag) {
    size_type len = MiniSTL::distance(first, last);
    /* capacity 不足 */
    if (len > capacity()) {
        /* 获得新的对象 */
        iterator temp = allocate_and_copy(first, last);
        destroy_and_deallocate(); /* 析构释放旧对象 */
        start = temp;
        end_of_storage = finish = start + len;
    } 
    /* size 足够 */
    else if (size() >= len) {
        /* 拷贝 size 大小部分，然后析构释放多余的*/
        iterator new_finish = MiniSTL::copy(first, last, start);
        destroy(new_finish, finish);
        finish = new_finish;
    }
    /* size < len <= capacity */
    else {
        /* 先找到 size 长度的部分 */
        ForwardIterator mid = first;
        MiniSTL::advance(mid, size());
        /* 先将前面 size 部分拷贝给目标 */
        MiniSTL::copy(first, mid, start);
        /* 再将后面剩下的拷贝给目标，会调用构造函数*/
        finish = MiniSTL::uninitialized_copy(mid, last, finish);
    }
}

2.11 补充

交换操作

1
2
3
4
5
6
template <class T, class Alloc> /* 交换操作 */
inline void vector<T, Alloc>::swap(vector &rhs) noexcept {
    MiniSTL::swap(start, rhs.start);
    MiniSTL::swap(finish, rhs.finish);
    MiniSTL::swap(end_of_storage, rhs.end_of_storage);
}

比较运算符(不是成员函数)

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
template <class T, class Alloc> /* A == B */
inline bool operator==(const vector<T, Alloc> &lhs, const vector<T, Alloc> &rhs) {
    return lhs.operator==(rhs);
}

template <class T, class Alloc> /* A != B */
inline bool operator!=(const vector<T, Alloc> &lhs, const vector<T, Alloc> &rhs) {
    return !(lhs == rhs);
}

template <class T>  /* A < B */
inline bool operator<(const vector<T> &lhs, const vector<T> &rhs) {
    return MiniSTL::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
                                            rhs.end());  // in stl_algobase.h
}

template <class T>   /* A > B */
inline bool operator>(const vector<T> &lhs, const vector<T> &rhs) {
    return rhs < lhs;
}

template <class T>  /* A <= B */
inline bool operator<=(const vector<T> &lhs, const vector<T> &rhs) {
    return !(rhs < lhs);
}

template <class T>  /* A >= B */
inline bool operator>=(const vector<T> &lhs, const vector<T> &rhs) {
    return !(lhs < rhs);
}

template <class T, class Alloc> /* 交换操作 */
inline void swap(const vector<T, Alloc> &lhs, const vector<T, Alloc> &rhs) {
    lhs.swap(rhs);
}

3 参考文献

《STL源码剖析》

C++ shrink_to_fit() 的实现

为什么STL的很多container的range version insert函数实现都有input iterator和forward iterator两个重载？



----------- 本文结束 -----------




0%