STL学习笔记--关联式容器

关联式容器依据特定的排序准则，自动为其元素排序。缺省情况下以operator<进行比较。set multiset map multimap是一种非线性的树结构，具体的说是采用一种比较高效的特殊平衡检索二叉树--红黑树结构。

1、set

set和multiset会根据特定的排序准则，自动将元素排序。两者的不同处在于multiset允许元素重复，而set不允许。

template<class _Kty,

class _Pr = less<_Kty>,

class _Alloc = allocator<_Kty> >

class set

...

从set的原型声明可以看出，在实例化一个set的时候需要指定一个排序准则，如果没有传入特别的排序准则，就采用缺省准则 less--这是一个预定义的函数对象，以operator<对元素进行比较。

set的特点：

(1) 自动排序，故搜索性能很好。但造成了一个重要限制：不能直接改变元素值，因为这样会打乱原本正确的的顺序。因此要改变元素值，必须先删除旧元素，在插入新元素。

(2) set不提供用来直接存取元素的任何操作函数。

(3) 通过迭代器进行元素的间接存取，重迭代器的角度来看，元素值是常量。

(4) set在元素快速搜寻方面有优化设计，提供了特殊的搜寻函数，这些函数比同名的STL通用算法效率高。

cout << "test set:\n";

set<int> c;

c.insert(1);

c.insert(10);

c.insert(1);

c.insert(8);

c.insert(9);

c.insert(1000);

std::copy(c.begin(), c.end(),std::ostream_iterator<int>(cout," "));

cout << endl;

cout << c.count(1) << endl;//返回“元素值为elem”元素个数

set<int>::iterator iter;

iter = c.find(1000); //返回元素值为elem的第一个元素的位置，如果找不到返回end()

if (iter != c.end())

{

	cout << "Find it!\n";

}

int elem = 1001;

//返回 elem 的第一个可以安插的位置，也就是 (元素值 >=elem)的第一个元素位置

c.lower_bound(elem);

//返回 elem 的最后一个可以安插的位置，也就是(元素值 > elem)的第一个元素位置

c.upper_bound(elem);

//返回 elem 可以安插的第一个位置和最后一个位置，也就是(元素值 == elem) 的元素区间

c.equal_range(elem) ;

定义set排序准则

有两种方式可以定义排序准则：

(1) 以template参数定义之,这种情况下，排序准则就是型别的一部分。

如：std::set<int,std::greater<int> > coll;

(2) 以构造函数参数定义之，这种情况下，同一个型别可以运行不同的排序准则，而排序准则的初始值或状态值也可以不同。如果是执行期才获得排序准则，而且需要不同的排序准则（但数据型别必须相同），这种方式可以派上用场。

执行期指定排序准则：

//排序准则，拥有状态，根据状态，确定不同的排序方式

template <typename T>

struct RuntimeCmp

{

public:

	enum CMP_MODE

	{

		NORMAL,

		REVERSE

	};

private:

	CMP_MODE _mode;

public:

	RuntimeCmp(CMP_MODE m = NORMAL)

		: _mode(m)

	{

	}

	bool operator() (const T & t1, const T & t2)

	{

		return (_mode == NORMAL) ? t1 < t2 : t2 < t1;

	}

	bool operator==(const RuntimeCmp & cmp)

	{

		return _mode == cmp._mode;

	}

};

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

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

RuntimeCmpSet coll(cmp); //通过构造函数传递排序准则

for (int val = 10; val > 0; --val)

{

	coll.insert(val);

}

std::copy(coll.begin(),coll.end(),std::ostream_iterator<int>(cout," "));

set的插入与删除操作

c.insert(elem) : 安插一份elem副本，返回pair结构

pair结构的second成员表示是否安插成功

pair结构的first成员返回新元素的位置，或返回已经存在的元素位置。

//set插入元素,返回pair对组

set<int> cc;

cc.insert(1);

std::pair<set<int>::iterator,bool> status = cc.insert(2);

if (status.second)

{

	cout << *(status.first) << " insert success!" << endl;

}

else

{

	cout << "element already exists!" << endl;

}

删除操作：

c.erase(elem);	//删除与elem相等的所有元素，返回被删除的元素个数

c.erase(pos);  //删除迭代期pos所指位置的元素，

c.erase(beg,end); //移除区间[beg,end)内的所有元素

相关的操作函数可以查询C++在线参考手册 cplusplus，上面有更多详细的关于STL的介绍。

2、map

map和multimap将key/value pair当作元素，进行管理。根据key的排序准则自动将元素排序。multimap允许重复元素，map不允许。

template<class _Kty,

class _Ty,

class _Pr = less<_Kty>,

class _Alloc = allocator<pair<const _Kty, _Ty> > >

class map

...

由上面的定义可以看出，如果使用者为传入特定的排序准则，就使用缺省的排序准则 less 即使用operatror<来进行比较，关于排序准则，可以参见上述的set排序准则。

map的搜索操作

和set一样，map也提供特殊的搜寻函数，以便利用内部树状结构获取较好的性能。

成员函数find用来搜寻拥有某个key的第一个元素，并返回一个迭代器，指向该位置，如果没有找到，则返回end()。注意：不能用find()来搜寻有某特定value的元素，这时必须使用通用算法find_if,或者写一个显示循环。

map的插入操作

map的插入与set类似，当然map的元素是key/value pair，用法稍微复杂些。

安插一个pair对组时，注意，在map内部，key视为常数，所以要不提供正确的型别，要不就得提供隐式或显式型别转换。

map<int,string> m;

//map插入元素

//运用value_type

m.insert(map<int,string>::value_type(1,"cm"));

//运用pair

m.insert(std::pair<const int,string>(2,"ranger"));

//使用make_pair

m.insert(std::make_pair(3,"PLA"));

map的下标运算符

map提供subscript操作符，可直接存取元素。

//下标运算符

m[2] = "rrrr";

m[3] = "dddd";

关于下标运算符需要注意的是：

m[key]返回一个reference,指向键值为key的元素，如果该元素尚未存在，就安插该元素，新元素的的value由默认构造函数构造。

不过这种方式可说是毁誉参半。

优点

可以通过更方便的接口对map安插新元素。

缺点

可以会不小心误置新元素，造成意想不到的结果。

这种方式比一般的map安插元素的方式慢，原因是新元素必先使用default构造函数将value初始化，而这个初值有马上被覆盖了。即调用了一次构造函数，又调用了一次赋值操作。

map的删除操作

map元素是移除与set类似，就不再详述了，这里要注意，移除元素时，当心发生意外情况，及迭代器失效的问题，如下：

//移除元素

string val = "dddd";

for (map<int,string>::iterator iter = m.begin(); iter != m.end(); ++iter)

{

	if (iter->second == val)

	{

		m.erase(iter); //RUNTIME ERROR!

	}

}

对iter所指元素实施erase操作，会使iter失效，此后再对iter操作，会发生未定义的行为。

正确的做法如下：

for (map<int,string>::iterator iter = m.begin(); iter != m.end();)

{

	if (iter->second == val)

	{

		m.erase(iter++);

		//iter = m.erase(iter); //这样也可以 C++11已经支持

	}

	else

	{

		++iter;

	}

}

巴特西

STL学习笔记--关联式容器

1、set

2、map

最新文章

热门文章