三十分钟掌握STL(2)

TAG:

三种插入迭代器如下：

· 普通插入器将对象插入到容器任何对象的前面。

· Front inserters 将对象插入到数据集的前面——例如，链表表头。

· Back inserters 将对象插入到集合的尾部——例如，矢量的尾部，导致矢量容器扩展。

使用插入迭代器可能导致容器中的其他对象移动位置，因而使得现存的迭代器非法。例如，将一个对象插入到矢量容器将导致其他值移动位置以腾出空间。一般来说，插入到象链表这样的结构中更为有效，因为它们不会导致其他对象移动。

Listing 5. insert.cpp

#include <iostream.h> 
#include <algorithm> 
#include <list> 
 
using namespace std; 
 
int iArray[5] = { 1, 2, 3, 4, 5 }; 
 
void Display(list<int>& v, const char* s); 
 
int main() 
{ 
list<int> iList; 
 
// Copy iArray backwards into iList 
copy(iArray, iArray + 5, front_inserter(iList)); 
Display(iList, "Before find and copy"); 
 
// Locate value 3 in iList 
list<int>::iterator p = 
    find(iList.begin(), iList.end(), 3); 
 
// Copy first two iArray values to iList ahead of p 
copy(iArray, iArray + 2, inserter(iList, p)); 
Display(iList, "After find and copy"); 
 
return 0; 
} 
 
void Display(list<int>& a, const char* s) 
{ 
cout << s << endl; 
copy(a.begin(), a.end(), 
    ostream_iterator<int>(cout, " ")); 
cout << endl; 
}

运行结果如下：

$ g++ insert.cpp
$ ./a.out
Before find and copy
5 4 3 2 1
After find and copy
5 4 1 2 3 2 1
可以将front_inserter替换为back_inserter试试。

如果用find()去查找在列表中不存在的值，例如99。由于这时将p设置为past-the-end 值。最后的copy()函数将iArray的值附加到链表的后部。

混合迭代器函数
在涉及到容器和算法的操作中，还有两个迭代器函数非常有用：

· advance() 按指定的数目增减迭代器。

· distance() 返回到达一个迭代器所需（递增）操作的数目。

例如：

list<int> iList; 
list<int>::iterator p = 
find(iList.begin(), iList.end(), 2); 
cout << "before: p == " << *p << endl; 
advance(p, 2); // same as p = p + 2; 
cout << "after : p == " << *p << endl; 
 
int k = 0; 
distance(p, iList.end(), k); 
cout << "k == " << k << endl;

advance()函数接受两个参数。第二个参数是向前推进的数目。对于前推迭代器，该值必须为正，而对于双向迭代器和随机访问迭代器，该值可以为负。

使用 distance()函数来返回到达另一个迭代器所需要的步骤。
注意

distance()函数是迭代的，也就是说，它递增第三个参数。因此，你必须初始化该参数。未初始化该参数几乎注定要失败。

函数和函数对象
STL中，函数被称为算法，也就是说它们和标准C库函数相比，它们更为通用。STL算法通过重载operator()函数实现为模板类或模板函数。这些类用于创建函数对象，对容器中的数据进行各种各样的操作。下面的几节解释如何使用函数和函数对象。

函数和断言
经常需要对容器中的数据进行用户自定义的操作。例如，你可能希望遍历一个容器中所有对象的STL算法能够回调自己的函数。例如

#include <iostream.h> 
#include <stdlib.h>     // Need random(), srandom() 
#include <time.h>       // Need time() 
#include <vector>       // Need vector 
#include <algorithm>    // Need for_each() 
 
#define VSIZE 24        // Size of vector 
vector<long> v(VSIZE); // Vector object 
 
// Function prototypes 
void initialize(long &ri); 
void show(const long &ri); 
bool isMinus(const long &ri); // Predicate function 
 
int main() 
{ 
srandom( time(NULL) ); // Seed random generator 
 
for_each(v.begin(), v.end(), initialize);//调用普通函数 
cout << "Vector of signed long integers" << endl; 
for_each(v.begin(), v.end(), show); 
cout << endl; 
 
// Use predicate function to count negative values 
// 
int count = 0; 
vector<long>::iterator p; 
p = find_if(v.begin(), v.end(), isMinus);//调用断言函数 
while (p != v.end()) { 
    count++; 
    p = find_if(p + 1, v.end(), isMinus); 
} 
cout << "Number of values: " << VSIZE << endl; 
cout << "Negative values : " << count << endl; 
 
return 0; 
} 
 
// Set ri to a signed integer value 
void initialize(long &ri) 
{ 
ri = ( random() - (RAND_MAX / 2) ); 
// ri = random(); 
} 
 
// Display value of ri 
void show(const long &ri) 
{ 
cout << ri << " "; 
} 
 
// Returns true if ri is less than 0 
bool isMinus(const long &ri) 
{ 
return (ri < 0); 
}

所谓断言函数，就是返回bool值的函数。

函数对象
除了给STL算法传递一个回调函数，你还可能需要传递一个类对象以便执行更复杂的操作。这样的一个对象就叫做函数对象。实际上函数对象就是一个类，但它和回调函数一样可以被回调。例如，在函数对象每次被for_each()或find_if()函数调用时可以保留统计信息。函数对象是通过重载operator()()实现的。如果TanyClass定义了opeator()(),那么就可以这么使用：

TAnyClass object; // Construct object
object(); // Calls TAnyClass::operator()() function
for_each(v.begin(), v.end(), object);
STL定义了几个函数对象。由于它们是模板，所以能够用于任何类型，包括C/C++固有的数据类型，如long。有些函数对象从名字中就可以看出它的用途，如plus()和multiplies()。类似的greater()和less-equal()用于比较两个值。

注意

有些版本的ANSI C++定义了times()函数对象，而GNU C++把它命名为multiplies()。使用时必须包含头文件<functional>。

一个有用的函数对象的应用是accumulate() 算法。该函数计算容器中所有值的总和。记住这样的值不一定是简单的类型，通过重载operator+()，也可以是类对象。

Listing 8. accum.cpp

#include <iostream.h> 
#include <numeric>      // Need accumulate() 
#include <vector>       // Need vector 
#include <functional>   // Need multiplies() (or times()) 
 
#define MAX 10 
vector<long> v(MAX);    // Vector object 
 
int main() 
{ 
// Fill vector using conventional loop 
// 
for (int i = 0; i < MAX; i++) 
    v[i] = i + 1; 
 
// Accumulate the sum of contained values 
// 
long sum = 
    accumulate(v.begin(), v.end(), 0); 
cout << "Sum of values == " << sum << endl; 
 
// Accumulate the product of contained values 
// 
long product = 
    accumulate(v.begin(), v.end(), 1, multiplies<long>());//注意这行 
cout << "Product of values == " << product << endl; 
 
return 0; 
}

编译输出如下：

$ g++ accum.cpp
$ ./a.out
Sum of values == 55
Product of values == 3628800
『注意使用了函数对象的accumulate()的用法。accumulate() 在内部将每个容器中的对象和第三个参数作为multiplies函数对象的参数,multiplies(1,v)计算乘积。VC中的这些模板的源代码如下：

// TEMPLATE FUNCTION accumulate 
 
template<class _II, class _Ty> inline 
 
    _Ty accumulate(_II _F, _II _L, _Ty _V) 
 
    {for (; _F != _L; ++_F) 
 
        _V = _V + *_F; 
 
    return (_V); } 
 
        // TEMPLATE FUNCTION accumulate WITH BINOP 
 
template<class _II, class _Ty, class _Bop> inline 
 
    _Ty accumulate(_II _F, _II _L, _Ty _V, _Bop _B) 
 
    {for (; _F != _L; ++_F) 
 
        _V = _B(_V, *_F); 
 
    return (_V); } 
 
        // TEMPLATE STRUCT binary_function 
 
template<class _A1, class _A2, class _R> 
 
    struct binary_function { 
 
    typedef _A1 first_argument_type; 
 
    typedef _A2 second_argument_type; 
 
    typedef _R result_type; 
 
    }; 
 
        // TEMPLATE STRUCT multiplies 
 
template<class _Ty> 
 
    struct multiplies : binary_function<_Ty, _Ty, _Ty> { 
 
    _Ty operator()(const _Ty& _X, const _Ty& _Y) const 
 
        {return (_X * _Y); } 
 
    };

引言：如果你想深入了解STL到底是怎么实现的，最好的办法是写个简单的程序，将程序中涉及到的模板源码给copy下来，稍作整理，就能看懂了。所以没有必要去买什么《STL源码剖析》之类的书籍，那些书可能反而浪费时间。』

发生器函数对象
有一类有用的函数对象是“发生器”(generator)。这类函数有自己的内存，也就是说它能够从先前的调用中记住一个值。例如随机数发生器函数。

普通的C程序员使用静态或全局变量 “记忆”上次调用的结果。但这样做的缺点是该函数无法和它的数据相分离『还有个缺点是要用TLS才能线程安全』。显然，使用类来封装一块：“内存”更安全可靠。先看一下例子：

Listing 9. randfunc.cpp

#include <iostream.h> 
#include <stdlib.h>    // Need random(), srandom() 
#include <time.h>      // Need time() 
#include <algorithm>   // Need random_shuffle() 
#include <vector>      // Need vector 
#include <functional> // Need ptr_fun() 
 
using namespace std; 

// Data to randomize 
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
vector<int> v(iarray, iarray + 10); 
 
// Function prototypes 
void Display(vector<int>& vr, const char *s); 
unsigned int RandInt(const unsigned int n); 
 
int main() 
{ 
srandom( time(NULL) ); // Seed random generator 
Display(v, "Before shuffle:"); 
 
pointer_to_unary_function<unsigned int, unsigned int> 
    ptr_RandInt = ptr_fun(RandInt); // Pointer to RandInt()//注意这行 
random_shuffle(v.begin(), v.end(), ptr_RandInt); 
 
Display(v, "After shuffle:"); 
return 0; 
} 
 
// Display contents of vector vr 
void Display(vector<int>& vr, const char *s) 
{ 
cout << endl << s << endl; 
copy(vr.begin(), vr.end(), ostream_iterator<int>(cout, " ")); 
cout << endl; 
} 
 
 
// Return next random value in sequence modulo n 
unsigned int RandInt(const unsigned int n) 
{ 
return random() % n; 
}

编译运行结果如下：

$ g++ randfunc.cpp
$ ./a.out
Before shuffle:
1 2 3 4 5 6 7 8 9 10
After shuffle:
6 7 2 8 3 5 10 1 9 4
首先用下面的语句申明一个对象：

pointer_to_unary_function<unsigned int, unsigned int>
ptr_RandInt = ptr_fun(RandInt);
这儿使用STL的单目函数模板定义了一个变量ptr_RandInt，并将地址初始化到我们的函数RandInt()。单目函数接受一个参数，并返回一个值。现在random_shuffle()可以如下调用：

random_shuffle(v.begin(), v.end(), ptr_RandInt);
在本例子中，发生器只是简单的调用rand()函数。

关于常量引用的一点小麻烦（不翻译了，VC下将例子中的const去掉） (karymay)

vector::erase()方法的详细介绍及问题解答	正确使用stl map的erase方法
warning C4251: 'vectortemp::m_Vector' : class 'std::vector'	C++ 标准模板库组件介绍
STL通用算法	C++常见错误之：no matching function for call to transform
stl 中list vector deque区别	stl中vector,list,deque的使用准则
详细解说 STL 排序(Sort)	STL 优先队列、队列、栈的使用

搜索

热门标签:

三十分钟掌握STL(2)