STL入门

C++标准函数库中80%是STL，其中广泛使用了泛性编程思想.

STL分为几大部分。

语言支持部分。
诊断部分。包含了异常处理，断言，错误代码三大方式。
通用工具部分。包括动态内存管理工具，日期/时间处理工具等。
字符串处理部分。
国际化部分。使用Locale和facet可以为程序提供多国际化支持，包括各种字符集，日期时间，数值货币处理的支持。
容器（containers）部分。STL重要部分，包含了许多数据结构，有vector（动态增加的数组），queue（队列），stack（堆栈）……甚至也包括string，它也可以看做为一种容器，并且适用所有的容器可用的方法。
算法（algorithms）部分。STL重要部分，包含了70多个通用算法，都是优化的效率很高的，用来控制各种容器，内建数组等。例如find可以用来在容器中查找某特定值的元素，for_each可以用来将函数应用到容器元素之上，sort用于对容器中的元素排序。
迭代器（iterators）STL重要组成部分，每个容器都有自己的迭代器，只有容器才可以进行访问自己的元素，它类似指针，将算法和容器中的元素联系起来。
数值（numerics）部分。包含了一些数学运算的功能库，对复数运算提供了支持。
输入输出（I/O）部分。摸版化的IOStream部分。他提供了对C++程序的支持，并且对原有的iostream兼容。

所以，总体看来，C++标准函数库，包含的10大块内容中，STL主要包含了四个部分，迭代器，容器，算法。和额外的一个字符串。

OOP（面向对象编程）和GP（泛性编程）

STL是基于GP设计的，OOP并不要求很高。而在纯OOP的JAVA中，由于不支持泛性编程，所以STL难以支持。

STL不同版本

HP STL始祖级的STL，第一个实现版本，因为不是考古学家，不管是谁做的了，只需要知道，现在很少使用了。
P.J.Plauger STL。VC的Include目录下的就是它。对 queue组件支持不足。
Rouge Wave STL。C++ Builder中的Include目录下就是它。由于更新不足，已被淘汰，可读性比较好。
STLport。比Rouge Wave STL更符合C++标准，运行速率比VC中的STL快，移植性好，在C++Builder6。0开始使用他。在Include目录下。
SGI STL。为GCC（Linix下的C++编译器）使用，同样可以在Include中找到它。它对C++语言标准十分支持，所以在Linix下性能很出色，并且可读性很好。

STL入门代码。

假设我们要实现一个功能，获取用户输入，对用户输入的数字进行排序，输出。这样一个基本的流程，现在以三种办法来实现，1：不使用STL，纯C++写。2：使用部分STL。3：将STL功能发挥到极至。

1：完全不使用STL

#include <stdlib.h>
#include <iostream>
using namespace std;

int Compare( const void *arg1, const void *arg2 );

void main( void )
{
const int MAX_SIZE = 10; // 数组允许元素的最大数
int nNum[MAX_SIZE];    // 整形数组

// 从标准输入设备读入整数，同时累计输入个数
// 直到输入的是非整形数据为止
int nInputNumLength;
for ( nInputNumLength = 0; cin >> nNum[nInputNumLength]; ++nInputNumLength );

// C标准库中的快速排序函数quick-sort
// 参数依次为需排列的数组名，数组长度，
// 数组元素大小，比较函数的指针
qsort( nNum, nInputNumLength, sizeof(int), Compare );

// 将排序完的结果输出到标准输出设备
for ( int nTemp = 0; nTemp < nInputNumLength; ++nTemp )
{
   cout << nNum[nTemp] << "\n" ;
}
}

// 进行整数大小的比较函数
int Compare( const void *arg1, const void *arg2 )
{
return (*(int *)arg1 < *(int *)arg2) ? -1 : (*(int *)arg1 > *(int *)arg2) ? 1 : 0;
}

上面的代码段可以很明显的发现其健壮性不足，我们设置了常量来控制了数组上限，若我们输入更多的数，将会数组越界。此时，我们可以三种办法。

大容量静态数组分配。把MAX_SIZE改成几万。而他不能解决根本问题。
限制用户输入数字个数。在for循环中加入些条件，使用户之后的越界后的输入无效化，显然，这个方法失去了程序的灵活性。
那么动态内存分配，无疑这Z是最好的办法，但是同时最复杂也可能出更多的错误。我们可能需要new,delete,malloc(),free()，要知道，这些指针，内存分配的都是BUG之源。

有点困难是么，我们看看STL。

2:部分使用STL

#include <iostream>
#include <vector>    // vector容器 
#include <algorithm>   // 算法
using namespace std;

void main( void )
{
vector<int> stlVector;
int nElement;

// 从标准输入设备中读入整数
// 将此数压入容器堆栈
while ( cin >> nElement )
{
   stlVector.push_back( nElement ); 
}

// STL中的排序算法
sort( stlVector.begin(), stlVector.end() );

// 将排序后的结果进行输出
for ( int nTemp = 0; nTemp < stlVector.size(); ++nTemp )
{
   cout << stlVector[nTemp] << "\n";
}
}

这个代码显然简洁了许多，其中的vector还可以自己动态的对长度进行增减，sort中有最优化的排序算法，这点已经不需要你去操心。一个健壮的程序很容易的就做完了，我们没有必要去拒绝STL，它已经十足的优秀。

3：几乎完全使用STL

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>    // 迭代器
using namespace std;

void main( void )
{
vector<int> stlVertor; // STL中的Vector容器

// 从标准输入设备读入整数，直到输入的非整形数据为止
copy( istream_iterator<int>(cin), istream_iterator<int>(), 
   back_insert_iterator< vector<int> >( stlVertor ) );

// STL中的排序算法
sort( stlVertor.begin(), stlVertor.end() );

// 将排序结果输出到标准输出设备
copy( stlVertor.begin(), stlVertor.end(), ostream_iterator<int>( cout, "\n" )); 
}

若你是新入门STL，可能会一下子晕掉，然而不必担心，我们实际上没必要这样去写，除非之后很精通了STL再考虑，一般我们使用第二种方法就足够节省我们相当的时间，提高程序速度和健壮性了。

STL入门常用流程，用途，注意事项概述

1：生成容器，用它来存放对象或者指向对象的指针。

例如：

class MyClass;
typedef list<MyClass> MyClassList;         // 用来存放对象的list容器
typedef list<MyClass*> MyClassPtrList;     // 用来存放对象指针的list容器

若容器保存的是普通对象，在容器析构时会自动的清理释放这些对象，但是，如果里面存放的是指针类型，那么需要我们手工的删除指针。

2：若我们使用容器来保存类的对象时，类中最好有自我拷贝构造函数，可以的话最好还重载操作符。

例如：

class MyClass
{
    public:
    MyClass();

    // 自我拷贝构造函数
    MyClass( const MyClass& myClass )
    {
       *this = myClass;
    }  

    // 重载操作符
    MyClass& operator= ( const MyClass& myClass );
};

当我们将一个对象的实例插入容器中时，STL会自己重新生成一个这个对象的拷贝，因此拷贝构造函数就成为必须的了，若我们没有正确的拷贝构造函数，就有可能造成容器中的对象的某些数据成员没有初始化。

3：将一个对象插入容器

MyClass myClass;
MyClassList myClassList;
MyClassList::iterator it;

it = myClassList.insert( myClassList.end(), myClass );
MyClass *myClass = &(*it);

此时我们将一个对象插入了容器之中，并且获得了容器中对象的指针，我们有必要来保存这个指针。但是若我们容器中保存的不是对象，而本身就是对象指针，那么我们就没有必要来额外保存它了，因为它已经保存在list表中了。

4：遍历一个容器并删除。

MyClass *pMyClass;
MyClassList::iterator it;

for( it = myClassList.begin(); it != myClassList.end(); ++it )
{
     pMyClass = *it;   // 容器中保存的是对象的指针
     pMyClass = &(*it);   // 容器中保存的是对象的值

     if( pMyClass 符合某些条件 )
     MyClassList.erase( it );

     // 若容器中保存的是指针，则还需要delete pMyClass;
}

STL组成模块

一：容器

包括向量vector,双端队列deque,链表list,队列queue,堆栈stack，集合set,多重集合multiset,映射map,多重映射mutlimap.

vector在中，它对元素访问和修改都是常数时间复杂度。它在序列尾部进行插入删除元素时候比较方便，在向量头部添加删除时，将会消耗大量时间。

deque在中，它与向量基本相同，特点是在针对头部元素时，插入和删除元素也很快，具有常数时间复杂度。

list在中，他对元素的访问时间，与序列双端距离是正比，但是插入和删除元素，则仅需花费常数时间。

queue在中，遵循先进先出原则，它只允许从后进行插入，从前进行删除，查找和修改。

stcak在中，它遵循后进先出原则，而且它是个有限的序列，只能实时进行动态内存分配，对它的查找，删除，修改等工作只能对最近插入序列方便。

set在中，它是由节点组成的红黑树，每个节点包含一个元素，节点之间以某种作用于元素的谓词排列，有着很快速的查找功能，但是牺牲了插入，删除等操作的能力。

multiset在中，他和set基本相同，但是可以支持重复元素的快速查找。

map在中，它是由[Key, Value]组成的集合，拥有快速查找的能力。

multimap在中，和map类似，但是同一键支持对应多个Value值，同样具有快速查询能力。

二：算法

算法部分包括头文件三大块组成。

其中包含了大堆的模版函数，这些函数主要可以实现比较，交换，查找，遍历，复制，修改，反转，排序，合并等功能。仅仅包括了一些在序列上面的简单数学运算的模版函数，包括加法和乘法。则定义了一些模版类来声明函数对象。

STL的算法是很优秀的，但是值得注意的是，由于容器集合的不同，我们尽量使用该容器自带的一些算法函数进行运算，因为他针对本容器集合进行了专门的优化，会比通用性的算法性能更好。

三；迭代器

它的具体实现实在中，这个之后我查看STL源码刨析时候再详细学习，现在我们可以把它想象为一个指针，而实际上，指针本身就是一种迭代器，但并不是所有的迭代器都是指针。前期学习，我们可以暂时的把这两者故意搞混，方便理解。

每一个容器，都有自己的迭代器，所以我们将迭代器分类：

输入迭代器。istream中使用它。它的功能是“向前读”操作。
输出迭代器。ostream,inserter中使用它。它的功能是“向前写”操作。
前向迭代器。它的功能是“向前读写”操作。虽然STL中没有，但是单向链表和Hash容器都是使用该类迭代。
双向迭代器。它的功能是“向前向后都可读写”操作。例如：list,set,multiset,map,multimap
随机迭代器。它的功能是“随机读写”操作。例如:vector,deque,array,string等其中，指针最类似随机迭代器。

接下来，我们来用段代码来测试，向几种不同容器中添加大段数据时的速度问题。

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <time.h>
#include <conio.h> // 非标准函数库文件，主要是实现DOS窗口的一些处理。其中有getch()函数。
using namespace std;


// 对数组array插入数据
template < typename T > 
void ArrayInsert( T *a, T *s, long size )
{
for ( int i = 0; i < 10; ++i )
{
   for ( long k = 0; k < size; ++k )
   {
    a[k] = s[k];
   }
}
}

// 对向量vector插入数据
template < typename T >
void VectorInsert( vector<T> *v, T *s, long size )
{
for ( int i = 0; i < 10; ++i )
{
   for ( long k = 0; k < size; ++k )
   {
    v->push_back( s[k] );
   }
}
}

// 对链表中插入数据
template < typename T >
void ListInsert( list<T> *l, T *s, long size )
{
for ( int i = 0; i < 10; ++i)
{
   for ( long k = 0; k < size; ++k )
   {
    l->push_back( s[k] );
   }
}
}

// 对多重集合中插入数据
template < typename T >
void MultisetInsert( multiset<T> *sl, T *s, long size )
{
for ( int i = 0; i < 10; ++i )
{
   for ( long k = 0; k < size; ++k )
   {
    sl->insert( s[k] );
   }
}
}

// 生成随机数
int *GetRandomInt( long size )
{
int *data = new int[size];
generate( &data[0], &data[size], rand );
return data;
}

// 主函数
int main( void )
{
const long size = 100000;
int *s_data;
int array1[size]; // 因为数组最大无法达到100000，所以此处不可size*10
double begin;
double end;
vector< int > vector1;
list< int > list1;
multiset< int > multiset1;

// 获取随机数
s_data = GetRandomInt( size );

clock();
cout << "计时开始" << endl;

begin = ( double )clock()/CLOCKS_PER_SEC;
ArrayInsert< int >( array1, s_data, size );
end = ( double )clock()/CLOCKS_PER_SEC;

cout << "填入Array    中1000000个元素消耗时间为：" << ( end - begin ) << endl;
getch();

begin = ( double )clock()/CLK_TCK;
VectorInsert< int >( &vector1, s_data, size );
end = ( double )clock()/CLK_TCK;

cout << "填入Vector   中1000000个元素消耗时间为：" << ( end - begin ) << endl;
getch();

begin = ( double )clock()/CLK_TCK;
ListInsert< int >( &list1, s_data, size );
end = ( double )clock()/CLK_TCK;

cout << "填入List     中1000000个元素消耗时间为：" << ( end - begin ) << endl;
getch();

begin = ( double )clock()/CLK_TCK;
MultisetInsert< int >( &multiset1, s_data, size );
end = ( double )clock()/CLK_TCK;

cout << "填入Multiset中1000000个元素消耗时间为：" << ( end - begin ) << endl;
getch();

free( s_data );
return 0;
}


/*
* 结果如下：
* Array:   0.016
* Vector:   1.016
* List:   5.093
* Multiset: 30.953
*/

从这个例子中，我们可以很明显的看出部分容器在插入性能上差于其他容器，但是它们是否没有存在意义了呢？否定的。插入慢的容器在查询上的优势是其它序列容器不可比拟的。没有一种容器是万能的，各自在一些部分有其优势。学习STL，很重要的一部分就是学习如何根据情况有效的选择适当容器。

STL入门

STL分为几大部分。

OOP（面向对象编程）和GP（泛性编程）

STL不同版本

STL入门代码。

1：完全不使用STL

2:部分使用STL

3：几乎完全使用STL

STL入门常用流程，用途，注意事项概述

1：生成容器，用它来存放对象或者指向对象的指针。

2：若我们使用容器来保存类的对象时，类中最好有自我拷贝构造函数，可以的话最好还重载操作符。

3：将一个对象插入容器

4：遍历一个容器并删除。

STL组成模块

一：容器

二：算法

三；迭代器

FreeKnight.Wong

周记20230220-20230226

周记20230213-20230219

周记20230130-20230212

周记20230122-20230129

周记20230114-20230121

2023年，一切重新开更

双月记202102-03

月记202101

美术流程整理

2020年记