65.9K
CodeProject 正在变化。 阅读更多。
Home

理解 STL

Jais Joy
starIconstarIconstarIconemptyStarIconemptyStarIcon

3.00/5 (24投票s)

2003年12月19日

9分钟阅读

viewsIcon

59724

本文解释STL的内部机制。

引言

STL拥有许多强大的功能，但许多程序员对此并不了解。模板的复杂性阻碍了人们发现STL的真正潜力。在这里，我将通过使用常用数据类型的模板生成代码来消除这种复杂性。本文旨在激发您探索STL的内部机制并利用其强大功能。一旦您理解了STL的特性，您将沉迷于在开发中使用它。解释所有容器和算法的内部机制超出了本文的范围。我选择vector和一些示例算法来解释STL的用法。

什么是STL？

标准模板库（STL）是一个通用的C++算法和数据结构库，由Alexander Stepanov和Meng Lee创建。STL基于称为泛型编程的概念，是标准ANSI C++库的一部分。STL是通过C++模板机制实现的，因此得名。虽然该库的某些方面非常复杂，但它通常可以以非常直接的方式应用，从而促进了其包含的复杂数据结构和算法的重用。

我为什么要学习STL？

STL提供了可以应用于这些集合的通用集合和算法。STL代码可以在不同平台之间使用。由于STL容器和算法是C++模板，因此只要满足模板的要求，您就可以使用任何数据类型。您可以创建通用代码，它将接受所有类型的容器类。STL容器的示例包括deque、list、map、multimap、multiset、set和vector；算法的示例包括find、copy、remove、max、sort和accumulate。

Vector和算法的关系

让我们尝试了解算法“remove”如何在vector上工作。Vector是一个STL容器，它动态增长并具有类似数组的特性。

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
using namespace std;
void main()
{  
    typedef /*list/deque*/vector<int > intVect ;
    typedef intVect::iterator intVectIt ;
    intVectIt end ,it,last;
            
    intVect Numbers ;  
    Numbers.push_back ( 10 );Numbers.push_back ( 33 ); Numbers.push_back(50);
    Numbers.push_back(33);    
    cout << "Before calling remove" << endl ;
    end = Numbers.end();
    cout << "Numbers { " ;
    for( it = Numbers.begin(); it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
    last = remove(Numbers.begin(), end, 33) ;
    cout << "After calling remove" << endl ;
    cout << "Numbers { " ;
    for(it = Numbers.begin(); it != last; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
}

程序输出

Before calling remove
Numbers { 10 33 50 33  }
 
After calling remove
Numbers { 10 50  }

在上面的例子中，我们将10、33、50和33插入到vector Numbers中。算法‘remove’用于删除所有值为33的元素。‘remove’在此操作中使用vector的迭代器。迭代器与指针类似，用于遍历对象数组。在实现vector<int>时，其迭代器是int*。

现在，将第一行的vector更改为deque或list。您会发现我们的程序与vector情况完全相同！要更改容器实现，我们只需要更改一行代码。这是STL提供的巨大优势之一。现在，将上述代码片段带到其他操作系统（我在Windows和Linux上进行了测试），构建并运行它。无需任何更改即可工作！这是STL提供的另一个巨大优势。您可以尝试使用除int之外的其他数据类型作为vector容器。

vector的构造函数

现在，让我们看看默认构造函数和带有整数参数的构造函数是如何工作的。我将使用以下类的对象来插入到vector中。

class A
{
    int iValue;
    A()
    {
        cout << "A()" << endl;
    }
};

类vector<A>有四个成员变量：allocator、_First、_Last和_End。allocator的类型为std::allocator<A>，而_First、_Last和_End是迭代器，最终为A*。vector<A>的默认构造函数使用std::allocator<A>对象初始化allocator。_First、_Last、_End被初始化为null指针。

现在，让我们看看构造函数vector(size_type _N, const _Ty& _V = _Ty(), const _A& _Al = _A())是如何工作的。通过移除类A的模板变量，构造函数的原型变为

vector ( unsigned int _N , const A& _V = A(), 
  const std::allocator<A> & _A1 = std::allocator<A> () )

此构造函数通过执行以下操作来初始化其成员变量：

  1. _First = allocator.allocate(_N, (void *)0);
  2. _Ufill(_First, _N, _V);
  3. _Last = _First + _N;
  4. _End = _Last;

allocator.allocate调用模板函数_Allocate，传递要创建的对象数量（_N）。对于类A，此模板函数将生成为A* _Allocate ( int , A * )。

此函数分配_N * sizeof ( A )内存并返回起始地址。该地址被赋给_First。_Ufill执行类似的操作

for (; 0 < _N; --_N, ++_F)
    allocator.construct(_F, _X);

在此，_F (类型为A* )指向对象将被构造的地址，通过_X使用A ( const A & )构造。

_Ufill将已构造的一个对象（const引用到对象_V。参见第2行。）复制到所有_N个位置。allocator.construct调用模板函数_Consturct，传递相同的参数。在位置_F处，使用新的placement new运算符，根据对对象_X的引用创建一个新对象。在第3行，_Last被赋值为最后一个对象之后的地址。_End和_Last指向同一位置。

现在，让我们看看析构函数是如何工作的。Vector的析构函数执行以下操作：

_Destroy(_First, _Last);
allocator.deallocate(_First, _End - _First);
_First = 0, _Last = 0, _End = 0;

_Destroy从_First到_Last为每个A* _F调用allocator.destroy ( _F )。此函数将显式调用析构函数~A()来销毁对象（记住，我们是使用placement new运算符分配的）。allocator.deallocate删除由（_First）指向的内存，这将释放为vector中所有对象分配的内存。

push_back是如何工作的？

vector中最复杂也最常用的函数是push_back。让我们分析一下push_back是如何工作的？push_back将在vector的末尾插入新数据。它调用insert ( end(), _X)。（成员函数end()返回_Last，_X是对要添加的对象（类A）的引用。）insert调用另一个重载函数insert (_Last , 1 , _X)。

对于类A，此函数定义变为

void insert(A* _P, unsigned int _M, const A& _X)
{
    if (_End - _Last < _M)
    {
        unsigned int _N = size() + (_M < size() ? size() : _M);
        A* _S = allocator.allocate(_N, (void *)0);
        A* _Q = _Ucopy(_First, _P, _S);
        _Ufill(_Q, _M, _X);
        _Ucopy(_P, _Last, _Q + _M);
        _Destroy(_First, _Last);
        allocator.deallocate(_First, _End - _First);
        _End = _S + _N;
        _Last = _S + size() + _M;
        _First = _S;
    }
    else if (_Last - _P < _M)
    {
        _Ucopy(_P, _Last, _P + _M);
        _Ufill(_Last, _M - (_Last - _P), _X);
        fill(_P, _Last, _X);
        _Last += _M; 
    }
    else if (0 < _M)
    {
        _Ucopy(_Last - _M, _Last, _Last);
        copy_backward(_P, _Last - _M, _Last);
        fill(_P, _P + _M, _X);
        _Last += _M; 
    }
}

在解释此代码之前，我们应该了解_End和_Last之间的区别。_End是为vector分配的缓冲区末尾，而_Last是最后一个插入值的位置。为了清楚起见，假设vector当前包含三个对象，并且_End和_Last指向同一位置。在这种情况下，即使我们只需要插入一个对象，分配器也会为3+3个对象分配内存。这是为了减少重新分配的次数。在push_back之后，_End将指向第6个对象的末尾，而_Last将指向第4个对象的末尾。在push_back期间，insert会检查是否需要重新分配（(_End - _Last < _M)）。如果需要重新分配，它将分配两倍大小或size() + _M（以较大者为准）。它会将所有数据复制到新缓冲区并删除旧缓冲区。然后，它会在_Last位置插入新数据，并重新分配_Last和_End。如果我们有足够的空间插入新元素（即_End - _Last > _M），则新元素将插入到_Last，并且_Last将被重新分配。

STL算法（它如何与vector配合使用）

在理解算法之前，我们需要学习函数对象是如何工作的。函数对象类定义了operator()()。结果是，模板函数无法区分您传递的是函数指针还是具有operator()()的类的对象。以下示例将使您对函数对象有清晰的认识：

#include <iostream.h>
void  f ()
{
    cout << "f()" << endl;
}
 
class X
{
public:
    void operator()()
    {
        cout << "X::operator()" << endl;
    }
};
 
template < class T >
void test_func ( T f1 )
{
    f1();
}
void main()
{
    X a;
    test_func(f );
    test_func(a);
}

程序输出为：

f()
X::operator()

函数对象可以分为生成器（无参数）、一元函数（单个参数）和二元函数（接受两个参数）。一元函数和二元函数的特殊情况是谓词（UnaryPredicate、BinaryPredicate），它们的意思是函数返回一个bool值。STL在其头文件<functional>中包含一组模板，可以自动为您创建函数对象。它之所以强大，不仅因为它是一个相当完整的工具库，而且因为它提供了一种思考问题解决方案的词汇，并且它是创建额外工具的框架。

copy是如何工作的？

问题：将一个vector<A>的所有数据复制到另一个vector<A>。

分析：对于类A，函数定义变为（您必须传递支持operator ++ ()和operator *()的参数。您可以将*和++应用于迭代器。）

copy ( A* first , A* last , A* x )

函数copy对范围[0, last-first]内的所有N求*(x+N) = * ( first + N )。它返回x+N。考虑vector<A>对象sourceA、DestA。要将sourceA的所有数据复制到DestA，您必须调用copy (sourceA.begin() , sourceA.end() , DestA.begin())。

在调用copy之前，请确保目标vector有足够的空间来容纳源vector中的所有数据。

transform是如何工作的？

问题：您有一个包含三个成员的vector<int>，并且您想将每个元素的平方存储在另一个vector<int>中。

解决方案：以下代码段可以帮您完成任务：

int square_it ( const int x)
{
    return x*x;
}
void main ()
{
    vector < int > v1, v2(3);
    v1.push_back(2);
    v1.push_back(5);
    v1.push_back(83);
    transform ( v1.begin() , v1.end() , v2.begin() , square_it );
    for ( vector<int>::iterator it = v2.begin(); it != v2.end() ; it++ )
        cout << *it;
}

对于上述代码，为transform生成的函数原型为：

int * trnsform ( int * First , int * Last , int* x, int (*f) (const int) )

transform在范围[0, Last - First]内的所有N上求*(x + N ) = square_it (*(First + N ) )。注意：在调用transform之前，v2已分配足够的内存（三个整数的内存）。

generate是如何工作的？

问题：在不使用push_back的情况下，将三个递增的数字插入到vector中。

解决方案：以下代码段可以帮您完成任务：

int f ()
{
    static int x = 1;
    return ++x;
}
void main ()
{
    vector < int > v2(3);
    generate ( v2.begin() , v2.end() , f );
    for ( vector<int>::iterator it = v2.begin(); it != v2.end() ; it++ )
        cout << *it;
}

对于上述代码，为‘generate’生成的函数原型为：

void generate ( int* first , int* last , int (*f)() )

generate在范围[0 , last - first]内的所有N上求*(first + N ) = f ( )。

replace_if是如何工作的？

问题：将vector<int>中的所有0替换为-1。

解决方案：假设vector<int> v包含整数1、2、0、6、0。以下代码会将所有0替换为-1：

int f (const int x)
{
   if ( x ==  0 )
       return true;
   else
       return false;
}
replace_if( v.begin() , v.end() , f , -1);

为replace_if生成的原型为：

void replace_if ( int * first , int * last , int (*f) ( const int) , -1 )

对于范围[0, last-first]内的所有N，replace_if的计算方式为：

if ( f ( *(first+N) ) )
    *(first + N ) = -1;

for_each是如何工作的？

问题：打印vector的所有成员。

解决方案：以下代码段可以帮您完成任务：

void f (const int x)
{
    cout << x << endl;
}
for_each ( v.begin() , v.end() , f);

为上述代码生成的原型为：

void for_each ( int * first , int* last , void (*f) (const int ) );

for_each的计算方式为：

f ( *( first + N ) ) for all N in the range [0 , last - first ]

fill是如何工作的？

问题：将vector<int> v填充为值10。

解决方案：以下代码可以完成任务：

fill ( v.begin() , v.end() , 10 );

为上述fill调用生成的函数原型为：

void fill(int * first, int * last, const int &) ;

fill在范围[0, last - first]内的每个N上求*(first + N) = x一次。

count_if是如何工作的？

问题：计算整数数组中'2'的数量。

解决方案：以下代码可以完成任务：

bool f2 ( const int x )
{
    if ( x == 2 )
        return true;
    else
        return false;
}

假设vector<int> v包含整数。以下代码将返回vector中'2'的数量：

int iNoof2s = count_if( v.begin() , v.end() , f2 );

为上述代码生成的函数原型为：

unsigned int count_if (  int * first , int * last , bool (*fn) ( const int ) );

count_if将计数n设置为零。然后，对于范围[0, last - first]内使谓词fn(*(first + N))为true的每个N，它执行++n。它正好执行last - first次谓词评估。

结论

您已经对vector和一些算法的工作原理有了一定的了解。尝试使用其他容器并探索更多算法。您将发现更多有趣的东西。祝您使用STL编码愉快。

© . All rights reserved.