chapter6: container容器

1. 定义:
1). 顺序容器sequence container 拥有由单一类型元素组成的一个有序集合.两个主要的顺序容器是list, vector and deque
2).关联容器associative container 支持查询一个元素是否存在,并且可以有效地获取元素.两个基本的关联容器类型是map和set.

2. list and vector
1). 选用准则:
  如果我们需要随机访问一个容器,则vector 要比list 好得多.
  如果我们已知要存储元素的个数,则vector 又是一个比list 好的选择.
  如果我们需要的不只是在容器两端插入和删除元素,则list 显然要比vector 好.
  除非我们需要在容器首部插入和删除元素,否则vector 要比deque 好.
  如果有排序功能,选择用vector最好,因为排序需要随即访问能力.
2).vector 怎样自己增长
  实际上vector 并不是随每一个元素的插入而增长自己,而是当vector 需要增长自身时.它实际分配的空间比当前所需的空间要多一些,也就是说,它分配了一些额外的内存容量,或者说它预留了这些存储区.实际上,对于小的对象,vector 在实践中比list效率更高.

  对于int和简单的类型,用vector效率比指针效率高.
  对于指向大型的类和实例指针用vector.
  对于大型类和实例的存储需要用list比较好.
3. 初始化
1)为容器指定一个显式的长度,长度可以是常量也可以是非常量表达式.
const int list_size = 64;
也可以 int list_size = 64;
list< int > ilist( list_size ); //容器中的每个元素都被初始化为与该类型相关联的缺省值.对于整数将用缺省值0初值化所有元素,对于string 类每个元素都将用string 的缺省构造函数初始化.
2)指定一个值并用它来初始化每个元素.
list< int > ilist( list_size, - 1 ); //每个元素初始值都是-1
vector< string > svec( 24, "pooh" );//24个字符串元素,每个为"pooh".
3). 通过resize()操作重新设置容器的长度.

1. svec.resize( 2 * svec.size() ); //将svec 的长度加了一倍,每个新元素都被初始化为与元素底层类型相关联的缺省值.

svec.resize( 2 * svec.size(), "piglet" ); //将svec 的长度加了一倍,个新元素都被初始化为"piglet".
4). 用一个现有的容器对象初始化一个新的容器对象.
vector< string > svec2( svec ); //将容器svec初始化svec2, 相当于:
vector<string> svec2= svec.
list< int > ilist2( ilist );
5). 定义的容器的类型有三个限制

• 元素类型必须支持等于操作符.

• 元素类型必须支持小于操作符(所有关系操作符都用这两个操作符来实现).
  

• 元素类型必须支持一个缺省值(对于类类型即指缺省构造函数).

4. 迭代器

1. 迭代器iterator 提供了一种一般化的方法,对顺序或关联容器类型中的每个元素进行连续访问, 每种容器类型都提供一个begin()和一个end()成员函数.

• begin()返回一个iterator ,它指向容器的第一个元素.
• end()返回一个iterator ,它指向容器的末元素的下一个位置.

   2. 除了iterator 类型, 每个容器还定义了一个const iterator 类型, 后者对于遍历const 容器是必需的. const iterator 允许以只读方式访问容器的底层元素.
   const vector<int> *pvec;
   vector<int>::const_iterator c_iter = pvec->begin(); //必须声明一个const_iterator, 才能够遍历pvec.
   vector<int>::const_iterator c_iter_end = pvec->end();
   3. iterator 算术运算, 只适用于vector 或deque , 而不适用于list .因为list 的元素在内存中不是连续存储的.
   ilist.begin() + 2; //不正确的,因为在list 中向前移动两个元素,需要沿着内部next 指针走两次.
    但list<string>::iterator it=ilist.begin();
       ++it; //正确的，因为他是迭代运算泛型算法对++操作符已经重载，相当于链表中next的指针。
   4. 容器对象也可以用"由一对iterator 标记的起始元素和未元素后一位置之间的拷贝"来初始化, 或用部分元素初始化.
   vector<string> svec2( svec.begin(), svec.end() );//sevc的所有元素初始化svec2
  vector<string>::iterator it =svec.begin() + svec.size()/2;
  vector<string> svec3( svec.begin(), it ); //用svec的前半部分初始化svec3.
   5. istream_iterator 类型:
   可以更直接地向svec 插入文本元素.
   istream_iterator<string> infile( cin ); // 将输入流iterator 绑定到标准输入上.
   istream_iterator<string> eos; // 标记流结束位置的输入流iterator
   vector<string> svec( infile, eos ); // 利用通过cin 输入的值初始化svec
   6. 通过传递数组的首元素指针和末元素后一位置的指针来初始化容器:
   string words[4] = {"stately", "plump", "buck", "mulligan"};
   vector< string > vwords( words, words+4 );
   int ia[6] = { 0, 1, 2, 3, 4, 5 };
   list< int > ilist( ia, ia+6 );
   7. 迭代只能用内置的函数得到地址,而不能用地址来初始化
    vector<string>::iterator it = &svec[0]; //错误, 不可以用地址赋值.
    vector<string>::iterator it = sevc.begin()//正确。
5. 顺序容器操作

1. insert(position, value), 第一个参数是一个位置, 指向容器中某个位置的iterator,  第二个参数是将要被插入的值, 这个值被插入到此iterator 指向的位置的前面；

     insert()方法的第二种形式支持“在某个位置插入指定数量的元素”
      vector<string> svec;
      string anna( "Anna" );
      svec.insert( svec.begin(), 10, anna ); //在vector 的开始处插入10 个Anna。

     insert()方法的最后一种形式“支持向容器插入一段范围内的元素”
      string sarray[4] = { "quasi", "simba", "frollo", "scar" };
      svec.insert( svec.begin(), sarray, sarray+4 );

    2. find()返回被查找元素在容器中的位置，或者返回容器的end()。 iterator 表明这次查询失败。 
   string son( "Danny" );
   list<string>::iterator iter;
   iter = find( slist.begin(), slist.end(), son ); //得到元素的位置
   slist.insert( iter, spouse );//将spouse插入到son的元素前面。

    3. 删除操作
    删除容器内元素的一般形式是一对erase()方法,一个删除单个元素,另一个删除由一对iterator 标记的一段范围内的元素,删除容器末元素的简短方法由pop_back()方法支持.
   string searchValue( "Quasimodo" );
   list< string >::iterator iter =find( slist.begin(), slist.end(), searchValue );  //得到元素的位置。
   if ( iter != slist.end() ) //表示查询有相匹配的元素。
       slist.erase( iter );
  
    删除某段元素：
    slist.erase( slist.begin(), slist.end() ); //删除所有元素。

   如同在容器尾部插入一个元素的push_back()方法相仿，pop_back()方法删除容器的末元素——它不返回元素，只是简单地删除它。
   vector< string >::iterator iter = buffer.begin();
   for ( ; iter != buffer.end(); iter++ )
   {
    slist.push_back( *iter );
    if ( ! do_something( slist ))
    slist.pop_back();  //尾部删除，
   }
6. 赋值和对换
  等于操作符：=
  // slist1 含有10 个元素
  // slist2 含有24 个元素
  slist1 = slist2; // 赋值之后都含有24 个元素， slist1 中的前10 个元素被删除。
  swap()可以被看作是赋值操作符的互补操作。
  slist1.swap( slist2 );//slist1有slist2中的24个元素，slist2中有slist1中的10个元素。
7. list 泛型算法：
   见url：http://www.cppblog.com/mzty/archive/2005/12/16/1828.html

8. getline()
  istream& getline( istream &is, string str, char delimiter ); //getline()读取istream 对象,向string 对象插入字符,包括空格.直到遇到分割符/文件结束或者被读入的字符序列等于string 对象的max_size()值,在该点处读入操作失败.
ifstream infile( file_name.c_str(), ios::in );
if ( ! infile ) {
cerr << "oops! unable to open file "
<< file_name << " -- bailing out!\n";
exit( -1 );
}

vector<string, allocator> *lines_of_text =new vector<string,allocator>; //元素指针集合的向量。
string textline;

while ( getline( infile, textline, '\n' )) {
lines_of_text->push_back( textline );
}

9. string 类查找函数find
1). 提供了一套查找函数,都以find 的各种变化形式命名.find()是最简单的实例, 给出一个字符串它返回匹配子串的第一个字符的索引位置,或者返回一个特定的值:
  string::npos  //表明没有匹配.
如下：
string name( "AnnaBelle" );
int pos = name.find( "Anna" );
if ( pos == string::npos )
 cout << "Anna not found!\n";
else
 cout << "Anna found at pos: " << pos << endl; //find返回的索引类型差不多总是int 类型。

2). 但是更严格的可移植的正确声明应该使用以下形式 string::size_type来保存从find()返回的索引值。
string::size_type pos = name.find( "Anna" );

3). find_first_of()查找与被搜索字符串中任意一个字符相匹配的第一次出现,并返回它的索引位置.
string numerics( "0123456789" );
string name( "r2d2" );
string::size_type pos = name.find_first_of( numerics );

find_first_of( numerics, pos )//返回从第pos位置开始向后第一个匹配的位置。
string::size_type pos = 0;
while (( pos = name.find_first_of( numerics, pos ))!= string::npos ){
pos++；
} //查找所有匹配numerics的位置。

4). substr()操作,生成现有string 对象的子串的一个拷贝.它的第一个参数指明开始的位置, 第二个可选的参数指明子串的长度.(如果省略第二个参数将拷贝字符串的余下部分).
vector<string> words;
while (( pos = textline.find_first_of( ' ', pos ))!= string::npos )
{
  words.push_back( textline.substr(prev_pos, pos-prev_pos));
  prev_pos = ++pos;  //前一个空格位置和单词的长度。
}

5). rfind() 查找最后即最右的指定子串的出现.
string river( "Mississippi" );
string::size_type first_pos = river.find( "is" ); //find()返回索引值1 表明第一个"is" 的开始.
string::size_type last_pos = river.rfind( "is" ); //rfind()返回索引值4 表明"is" 的最后一个出现的开始.

6).find_first_not_of()查找第一个不与要搜索字符串的任意字符相匹配的字符.
string elems( "0123456789" );
string dept_code( "03714p3" );
string::size_type pos = dept_code.find_first_not_of(elems);// returns index to the character 'p',找到第一个非数字字符。

7). find_last_of()查找字符串中的与搜索字符串任意元素相匹配的最后一个字符.

8). find_last_not_of()查找字符串中的与搜索字符串任意字符全不匹配的最后一个字符.

9). 以上这些函数都有一个可选的第二参数来指明起始的查找位置。

10. 用数组下标定位容器元素。
string aa[]{"test", "test","god","my"};
vector<string> aa(aa, aa+4);

1. STL iterator:
 for(vector<string>::iterator it=aa.begin(); it != aa.end(); ++it)
  cout << *it <<endl;

2. array:
  for(int i=0; i < aa.size(); ++i)
    cout << aa[i];  //if the pointer to vector(vector<string> *aa, use the (*aa)[i];

11). pair & make_pair
pair<short,short>
make_pair( line_pos, word_pos )

10. 字符串删除字符
erase()操作的第一个参数表示字符串中要被删除的字符的开始位置，第二个参数是可选的表示要被删除的字符的个数。如果我们省略第二个参数，则erase()将删除从pos 到字符串结束的所有字符。
word.erase(pos, 1); //删除word的pos位置的字符。

11. string的其他操作
1). isalpha() isdigit() ispunct() isspace() toupper()
标准C++库定义了一个ctype类它封装了标准C 库函数的功能以及一组非成员函数,如toupper() tolower()等等.
必须包含标准C++头文件
#include <locale>

2). erase()的第二种形式用一对迭代器iterator 作参数标记出要被删除的字符的范围.
typedef string::size_type size_type;
size_type startPos = name.find( 'L' );
size_type endPos = name.find_last_of( 'a' );
name.erase( name.begin()+startPos,name.begin()+endPos );//第二个iterator 指向的字符不属于要被删除的字符范围.
3). assign()和append()字符串操作, 顺次地把一个string 对象的部分拷贝或连接到另一个string 对象上.
string s1( "Mississippi" );
string s2( "Annabelle" );
string s3;
s3.assign( s1, 0, 4 ); // 拷贝s1 的前4 个字符 "Miss"
s3 += ' '; // "Miss "
s3.append( s2, 0, 4 ); // "Miss Anna"
等价于：
s3.assign( s1, 0, 4 ).append( ' ' ).append( s2, 0, 4 );

4). at()提供了运行时刻对索引值的范围检查,如果索引是有效的,则at()返回相关的字符元素与下标操作符的方式相同.但是如果索引无效则at()抛出out_of_range 异常.
void mumble( const string &st, int index )
{
try {
  char ch = st.at(index);
    }
    catch( std::out_of_range ) { ... }
}

5). compare()字符串操作提供了两个字符串的字典序比较:
 s1.compare( s2 );
则compare()返回三个可能值之一:
1 如果s1 大于s2 则compare()返回一个正值
2 如果s1 小于s2 则compare()返回一个负值
3 如果s1 等于s2 则compare()返回0

6).replace():第一个参数代表开始位置,第二个参数代表从position 开始的字符串的长度, 第三个参数代表新的字符串.
string new_str( "Abstract Data Type" );
sentence.replace( position, length, new_str );