Standard Template Library

2017年8月17日

9:30

推荐阅读

Algorithms + Data Structures

= Programs

1976 wirtten by

Niklasu Wirth

Pascal语言之父

·C++基本语法

·模版(template)基础

-事半功倍

·数据结构(data structures)和算法(algorithms)概念

-如鱼得水

三

想

GNU-C V2.9.1 && V4.9

标准库版本，Visual C++

源代码分布：

file layout

VS2013

…\include子目录

Dec+C++ 5.1.1 with GNU V4.9.2

…\include\c++内并非实做内容

…\include\c++\ext

blabla allocator

OOP (Object-oriented programming)vs. GP(Generic Programming)

2017年8月21日

11:27

查看大型OOP库的难点

继承关系复杂、

虚函数

OOP 企图将datas和methods关联在一起

 

template<class T,

    calss Alloc = alloc>

class list{

…

void sort();

};

标准库没有这种困扰

list不能使用::sort()的原因

 

*first + *(last - first)/2

只有RandomAccessIterator

才能如此操作

而list的iterator并不是这种类型

所以，不能使用

GP将datas和methods分开来

 

采用GP：

·Containers和Algorithms团队可以各自

闭门造车，其间以Iterator沟通即可

·Algorithms通过Iterators确定操作范围

，并通过Iterators取用Container元素

所有algorithms，其内最终

涉及元素本身的操作，无非

就是比大小

阅读C++标准库源码的必要基础

2017年8月21日

11:50

·Operator Overloading

迭代器重载

 

·Templates

-Class Templates，类模板

-Function Templates，函数模板

实参推导

-Member Templates，成员模板

Specialization，特化

template<>

struct __type_traits<int>

{

…

};

__type_traits<Foo>::has_trivial_destructor

template<> || __STL_TEMPLATE_NULL

Partial Specialization，偏特化

malloc

VC6附加标准库的allocator

分配器 调用 operator new

operator new 调用malloc

VC6 & BC++ & GCC2.9

的allocator只是以

::operator new和

::operator delete完成

allocate()和dellocate()

没有任何特殊设计

malloc附带额外开销

allocator

区块小 开销比例大 -->难以接受

区块大 开销比例小

GNU-C 2.9比较好 GNU-C 4.9又回到了VC BC的模式

GNU-C 2.9版本的alloc还在 在G4.9中改名为__pool_alloc

G2.9 alloc 容器模式下 不带cookie 额外开销

 

容器之间的实现关系与分类

2017年8月21日

14:55

容器，结构与分类

 

容器list

2017年8月21日

15:03

一大堆typedef

node->link_type->list_node*

 

sizeof(list)应该是4

 

template<class T>

struct __list_node

{

typedef void* void_pointer;

void_pointer pre;

void_pointer next;

T data;

}

所有的容器必然有一个typedef  blablabla iterator

所有iterator都必须typedef五个类型

 一大组的操作符重载

list's iterator

list<Foo>::iterator it;

postfix form ++

前++ 返回reference

后++ 返回非reference 禁止连续++

 

像偶像(int)致敬

 

->和* 提取值

*返回T&

->返回T*

容器list

2017年8月22日

15:08

G2.9

一堆typedef + 一堆操作符重载

G4.9相较于G2.9：

·模板参数只有一个(易理解)

·node结构有其parent

·node的成员type较精确

G4.9

迭代器设计原则

2017年8月22日

15:23

traits : 特征、特性、特质

人为设置的一种萃取机制

iterator需要遵循的原则

算法和容器之间的桥梁

 

iterator_category

difference_type

value_type

reference

pointer

iterator associated type

iterator traits

type traits

character traits

pointer traits

算法rotate 调用std::__rotate()

 

std::__rotate(…, std::__iterator_category(__first));

iterator traits诞生的因由：

iterator并不是一个class而是native pointer的时候

无法回答这五个问题

（native pointer 被视为一种退化的iterator）

迭代器设计原则

2017年8月22日

15:42

银弹

判断扔进去的是否为class形式的iterator

如果是 则采用问答方式得出

如果不是 偏特化 typedef  代其回答

容器vector

2017年8月22日

15:57

template<class T, class Alloc = alloc>

class vector

{

public:

typedef T                      value_type;

typedef value_type*  iterator;

typedef value_type& reference;

typedef size_t             size_type;

protected:

iterator start;

iterator finish;

iterator end_of_storage;

public:

iterator begin() { return start;}

iterator end() {return finish;}

size_type size() const {return size_type(end() - begin());}

…

};

NOTICE：大量调用拷贝构造和析构

vector's iterator

public继承

是一种

is-a关系

array和forwardlist

2017年8月22日

16:34

容器array

单向链表只能++ 往一个方向走

关于作业

2017年8月25日

11:08

创建一个list容器，放置6个整型数值[0, 1, 30, 20, 10, 0]

1. 从后向前打印出容器内的元素

2. 向list容器后面添加两个元素，并对容器内的值求和并打印

3. 打印链表的中间元素

4. 找到不为0的元素，复制到一个vector中并打印vector元素

来自 <http://mooc.study.163.com/learn/GeekBand-2001184001?tid=2001361008#/learn/hw?id=2001591031&r=true>

创建一个list容器 放置整形值

list<int> i_list

以一个数组进行容器的初始化

所以需要先声明并给这个数组赋值

int src_int[6] = {0, 1, 30, 20, 10, 0};

list的构造函数允许将两个其他容器的迭代器

作为参数传入进行list的构造

list<int> i_list(&src_int[0], &src_int[6]);         //创建list容器，并将6个数值放入

 

 

1.从后向前打印出容器内的元素

list自身携带逆序迭代器，想要从后向前打印list内

元素，则采用逆序迭代器遍历输出即可

 

for (auto it = i_list.rbegin(); it != i_list.rend(); ++it) //采用逆序迭代器从后向前打印出容器内的元素

{

cout << *it << " ";

}

cout << "\r\n打印完毕" << endl;

2.向list容器后面添加两个元素并对容器内的值求和并打印

先使用cin获得需要添加的两个元素

调用push_back()将这两个元素添加到list的末尾

初始化和sum为0

采用迭代器遍历整个容器，将所有值叠加至sum即为所有元素的和

int a, b;

cout << "请输入需要添加的元素的值:" << endl;

cin >> a >> b;

i_list.push_back(a);

i_list.push_back(b);

int sum = 0;

for (auto it = i_list.begin(); it != i_list.end(); ++it)

{

sum += (*it);

}

 

关于作业

2017年8月25日

11:15

3.打印链表的中间元素

 

考虑到链表的长度(size)可能为奇数也可能为偶数

 

当长度为奇数时 正中间的元素即为中间元素

当长度为偶数时 中间的两个元素均为中间元素

实现如下：

if (i_list.size()%2 != 0)//如果链表size为奇数则打印正中间元素

{

for (size_t i = 1; i < (i_list.size() + 1)/2; ++i)//从链表第一个元素开始到链表长度一半的偏移量

{

tar_it++;

}

cout << "链表的中间元素为:"         << *tar_it << endl;

}

else//如果链表size为偶数则打印中间两个元素

{

for (size_t i = 1; i < i_list.size()/2 ; ++i) //从链表第一个元素开始到链表长度一半的偏移量

{

tar_it++;

}

cout << "链表的中间元素为:"         << *tar_it << "和";

tar_it++;

cout << *tar_it << endl;

}

 

4.找到不为0的元素，插入到vector，并打印

声明vector，置空

遍历list 判断元素是否为0，不为0则插入到vector

遍历vector输出每个元素

实现如下：

vector<int> i_vector;

i_vector.clear();

for (auto it = i_list.begin(); it != i_list.end(); ++it)

{

if (*it != 0)//不为0的元素

{

i_vector.push_back(*it);

}

}

cout << "将不为0的元素拷贝到vector中后打印结果如下:" << endl;

for (auto value: i_vector)

{

cout << value << " ";

}