The C++ Standard Library 学习笔记（一）第6章

6. STL 容器

6.1 容器共同的限制和操作

复制和swap

如果要将一个容器的元素拷贝到另一个容器，并且先前的容器将不再使用，则可以用swap实现高效的拷贝，因为swap只交换容器内部数据而不影响实际存储数据。

从标准输入读入元素

Container<T> c((istream_iterator<T>(cin),

istream_iterator<T>()));

6.2 vector

删除所有的值为val的元素

vec.erase(remove(vec.begin(), vec.end(), val), vec.end());

仅删除第一个值为val的元素

vector<T>::iterator iter = find(vec.begin(), vec.end(), val);

if (iter != vec.end())

{

vec.erase(iter);

}

缩减vector的容量

vector<T>(vec).swap(vec);

6.3 deque

deque和vector一样将元素存储在动态数组中，但它是一个两端开放的容器，因此在头和尾的插入删除操作都很快。

deque占用的内存大小会自动释放，当它的元素被删除时。

6.4 list

STL中的list是一个双向链表。链表的插入和删除操作都是常数时间，同时，list还提供了容器内部和list容器之间移动元素的操作。

6.5 set和multiset

6.5.1 set的排序条件

set的排序条件必须是严格弱排序（strict weak ordering）

这就意味着：

1. 它必须是反对称的

即：若 x < y 为真，则 y < x 为假，也即：若 op(x, y) == true，则 op(y, x) == false

2. 它必须是可传递的

即：若 x < y 且y < z，则 x < z，也即：若 op(x, y) == true，op(y, z) == true，则 op(x, z) == true

3. 它必须是非自反的

即：x < x 永远为假，也即 op (x, x) === false

因此元素x，y的相等条件是 op(x, y) == false 且 op(y, x) == false;

特殊的搜索操作

lower_bond(elem) 返回第一个elem可以插入的位置，即：>= elem 的第一个元素的位置

upper_bond(elem) 返回最后一个elem可以插入的位置，即：> elem的第一个元素的位置

equal_range(elem) 则返回第一个和最后一个可以插入的位置组成的pair。

multiset仅删除第一个值为val的元素

std::multiset<T>::iterator pos = aset.find(val);

if (pos != aset.end())

{

aset.erase(pos);

}

一个运行时决定排序条件的例子：

#include <iostream>

#include <set>

using namespace std;

template<class Container>

void print(const Container& c, const char* promption)

{

cout << promption << endl;

copy(c.begin(), c.end(), ostream_iterator<Container::value_type>(cout, " "));

cout << endl;

}

template<class T>

class RuntimeCmp

{

public:

enum CmpMode {NORMAL, REVERSE};

//constructor decides the sort criterion

RuntimeCmp(const CmpMode mode_ = NORMAL)

: _mode(mode_)

{

//empty

}

//Compare the elements according to the mode

bool operator() (const T& t1_, const T& t2_)

{

return ((NORMAL == _mode) ? t1_ < t2_ : t1_ > t2_);

}

//comparision of sorting criterion

bool operator==(const RuntimeCmp& rc_)

{

return (_mode == rc_._mode);

}

private:

CmpMode _mode;

};

typedef set<int, RuntimeCmp<int> > IntSet;

void fill(IntSet& set)

{

set.insert(4);

set.insert(7);

set.insert(5);

set.insert(1);

set.insert(6);

set.insert(2);

set.insert(5);

}

int main()

{

//create a set with default sorting cirterion

IntSet set0;

fill(set0);

print(set0, "set0:");

//create a set with reverse sorting cirterion

RuntimeCmp<int> reverse_order(RuntimeCmp<int>::REVERSE);

IntSet set1(reverse_order);

fill(set1);

print(set1, "set1:");

//assign elements

set0 = set1;

set0.insert(3);

print(set0, "set0 after assignment:");

//just make sure...

if(set0.value_comp() == set1.value_comp())

{

cout << "set0 and set1 have same sorting cirterion" << endl;

}

else

{

cout << "set0 and set1 have different sorting cirterion" << endl;

}

getchar();

return 0;

}

输出

set0:

1 2 4 5 6 7

set1:

7 6 5 4 2 1

set0 after assignment:

7 6 5 4 3 2 1

set0 and set1 have same sorting cirterion

6.6 map 和 multimap

map是键值对的容器，又叫关联数组。它以键排序，它的排序条件也必须是“严格弱排序”的。

删除值为val的元素的正确方法

MapType map;

MapType::iterator pos, tmp_pos;

for (pos = map.begin(); pos != map.end(); )

{

if (pos->second == val)

{

map.erase(pos++);

}

else

{

pos++;

}

}

6.7 其他STL容器

6.7.1 STL容器String

STL的String可以看成是chars的容器，它提供了STL的容器接口，它提供了begin，end，push_back等成员函数。

6.7.2 普通数组作为STL容器

很多数组可以用于普通数组上，数组的指针可以看成是它的迭代器。

例子：

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

int main()

{

int coll[] = { 5, 6, 2, 4, 1, 3 };

//square all elements

transform (coll, coll+6, // first source

coll, // second source

coll, // destination

multiplies<int>()); // operation

//sort beginning with the second element

sort (coll+1, coll+6);

//print all elements

copy (coll, coll+6,

ostream_iterator<int>(cout," "));

cout << endl;

getchar();

}

输出：

25 1 4 9 16 36

6.8 引用计数实现的智能指针

一个用引用计数实现智能指针的类

#ifndef __SHARED_PTR_H__

#define __SHARED_PTR_H__

template<class T>

class SharedPtr

{

public:

explicit SharedPtr(T* p_ = 0)

:_p(p_), _count(new long(1))

{

}

SharedPtr(const SharedPtr<T>& rhs_)

:_p(rhs_._p), _count(rhs_._count)

{

++*_count;

}

~SharedPtr() throw ()

{

dispose();

}

SharedPtr& operator = (const SharedPtr<T>& rhs_)

{

if (this != &rhs_)

{

dispose();

_p = rhs_._p;

_count = rhs_._count;

++*_count;

}

return *this;

}

T* operator -> () const { return _p; }

T& operator * () const { return *_p; }

private:

void dispose() throw ()

{

if (0 == --*_count)

{

delete _p;

delete _count;

_p = 0;

_count =(long*)0;

}

}

private:

T* _p;

long* _count;

};

#endif //__SHARED_PTR_H__

6.9 何时使用何种容器

基本的指导是：

1. 一般来说，使用vector已能满足大部分的需求，它有最简单的内部数据结构，可以随机访问元素。

2. 如果你需要经常在容器头和尾插入删除元素，可以考虑使用deque，它还有个好处：能自动在删除元素的时候收缩空间。

3. 如果你需要经常在容器的中间插入和删除元素，你可以使用list，他插入和删除元素都是常数时间，无论元素在什么地方，并且由于它是基于节点的容器，它不易使迭代器失效。

4. 如果你需要一个容器的操作具有原子性，可以考虑使用list或者关联容器，但要注意某些算法会破坏这个特性。

5. 如果你需要经常在容器里根据某个条件搜索某个元素，你可以使用set或multiset。

6. hash_table 通常比二叉树实现的set或map快5到10倍，如果不依赖元素的顺序（hash_table的元素没有顺序）你可以考虑使用hash_table来提高效率。

需要字典，使用multimap。