C++STL详解（二）— string类模拟实现

string类成员函数

构造函数

string类构造函数产生过程

简易版构造函数：
1：创建一个传来的字符串大小的空间（ +1是为了储存’\0’），
2：分别对string类内置成员函数进行初始化。
3：将字符串的内容拷贝到新的空间之中。

但是，这样没有默认构造函数，当我们用户不传参时想创建一个空类时这样编译就会发生错误。
如果我们用nullptr去构造函数时，如果调用return_str函数（以下会讲）时又会访问到空字符串而发生错误。

所以：我们可以写默认构造函数，防止构造时出现空类的情况。用" "(‘\0’) 结束字符代表空字符串时的构造，可以防止访问到空指针的情况。
此时又因为在简易版时，我们使用了三个strlen，而strlen函数的时间复杂度为O（n）。为了更加的高效简洁，我们尽量使用一次strlen。另外为了避免对于内置类型使用初始化列表时出现初始化顺序而出错的情况，我们可以采用在函数体内进行初始化。

最终版：

拷贝构造函数

我们知道，对于内置类型不写默认拷贝构造，编译器会默认生成，且一般都是值拷贝。但是当变量关于数组等资源进行浅拷贝时会将一个指针的值给另外一个指针，进而会造成两个指针指向同一块区域，当函数结束时，会分别调用两个类的析构函数，同一块空间 被两次销毁，这样会导致程序崩溃。
简单来说，对于日期类的话我们可以进行浅拷贝，对于string类来说，我们必须采用深拷贝。

深拷贝：
1：创建一个和被拷贝对象空间大小一致的空间并进行构造。
2：分别对string类的内置成员进行初始化。
3：将被拷贝对象的内容拷贝给新的空间。

析构函数

我们知道对于malloc动态申请的空间一个函数周期结束时并不会被释放，除非是整个程序结束时才会被释放。所以我们设置析构函数，在类的生命周期结束时自动调用。
注意：
delete函数面对空指针是不会做任何事情的，但是在C++中是可以被定义的，也就是说可以delete空指针。

赋值运算符重载函数

对于string类，当我们不写赋值运算符重载时，编译器会默认生成，但是编译器调用默认的赋值运算符重载一般采用的是值拷贝。例如：当 s1 = s2时
1：此时，当该对象生命周期结束时，编译器会调用两次构造函数，所以会造成同一块空间被两次delete而造成崩溃。
2： 原本s1和s2同指一块空间，此时还会造成原来s1指向的空间丢失，进而难以被析构函数析构，造成野指针的问题。

传统写法

1：删除原来的空间。
2：创建新空间。
3：将数据拷贝在_str中。
4：将string类中变量进行初始化。
5：注意不要让相同的类进行赋值，防止又再一次发生拷贝构造而影响效率。

String& operator=(const String& s)
		{
			if (this != &s)       //确报是两个不同的类赋值。
			{
				delete[] _str;
				_str = new char[s._capacity + 1];
				strcpy(_str,s._str);
				_str = tmp;
				_capacity = s._capacity;
				_size = s._size;
			}
			return *this;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

现代写法

相对于传统写法，现代写法指在函数作用域内去一个临时对象，让这个临时对象采用swap函数进行分别对string类内置成员进行初始化。
：注意：
1：这里我们采用自定义的swap是因为库里面的swap函数会调用 赋值运算符，而赋值运算符又会调用swap函数，依次循环，造成程序崩溃。
2：并且库里面的swap函数，还会构造一个对象c，两次采用赋值运算赋重载即采用了两次深拷贝造成效率底下等问题。

void swap(String& tmp)
		{
		   std::swap(_capacity, tmp._capacity);
		   std::swap(_size, tmp._size);
		   std::swap(_str, tmp._str);
		}

String& operator=(const String& s)
		{
		    if (this != &s)
		    {
		   	 String tmp(s._str);
		   	 swap(tmp);
		    }
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

现代写法二：
现代写法二的特征就是采用传值传参，让s作为临时对象去swap,而此时的临时对象的地址就变成了原来拷贝对象的地址，出了这个函数后，指向的空间自动调用析构函数进行消除。相对于现代写法一，这种方法更加简洁。

String& operator=(String s)
		{
		    if (this != &s)
		    {
		   	 swap(s);
		    }
		}
1
2
3
4
5
6
7

void swap(String& tmp)
		{
		   std::swap(_capacity, tmp._capacity);
		   std::swap(_size, tmp._size);
		   std::swap(_str, tmp._str);
		}

1
2
3
4
5
6
7

迭代器函数

begin函数和end()函数

模拟实现迭代器并进行访问

范围for

因为范围for的底层由迭代器实现，此时使用范围for更加简洁。

容量相关函数

reserve函数

创建n个空间的容量，避免频繁扩容。

	void reserve(size_t n)  //帮助扩容，如果我需要多少字符，提前开n个来避免频繁扩容。
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];
				strcpy(tmp,_str);
				delete[]_str;//注意delete删除位置，要先删除再重新给_str赋值。
				_str = tmp;
				_capacity = n;  //扩容之后要记得将内置变量类型属性改变。
			}
		}
1
2
3
4
5
6
7
8
9
10
11

resize函数

设置需要的数据个数，并对需要的数据根据情况进行初始化。
1：如果需要的字符个数大于原来的字符个数时：
（1）例如：
如果string类 s中已经有了字符串，则要在后面的字符串中加上所需要的初始值，直到数据n满。
(2) 如果没有初始值，则默认为’\0’
2：如果需要的数据n个数小于原来的数据_size，则要删除多余的数据。此时的删除后续的数据一般指无法进行访问的意思。

void resize(size_t n, char s = '\0')
		{
			if (n > _size)
			{
				reserve(n);
				int i;
				for (i = _size; i < n; i++)
				{
					_str[i] = s;
				}
				_str[i] = '\0';
				_size = n;
			}
			else  //如果n小于这个数的话，则要进行删除。
			{
				_str[n] = '\0';
				_size = n;
			}

		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

string类的增删查改

push_back

简单的进行尾插，注意设置字符串的结束符’\0’。

void push_back(char ch)                        //一个一个字符的尾插；
		{
			if (_size == _capacity)   //如果插满了，则要进行扩容。
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			_str[_size++] = ch;      //扩完了就插入一个字符。
			_str[_size] = '\0';
		}

1
2
3
4
5
6
7
8
9
10

append

在字符串的尾部增加一个字符串。

	void append(const char* s)
		{
     size_t len = strlen(s);  
   if (len + _size > _capacity)   //如果要加的数据于原先的数据之和大于容量则要进行扩容。
			{
				reserve(len + _size);
			}
		strcpy(_str + _size, s);   //扩完容之后要记得将原来的数据进行拷贝。
			_size += len;   //更新字符串里面的数据个数。
		}
1
2
3
4
5
6
7
8
9
10

operator[]

operator[]有针对返回值有两种情况：
1：当不想让用户修改返回值而影响该字符串数据时，const对象就会调用第一种
2：如果可以修改则不用加const。

//一：
const  char& operator[](size_t pos) const     //如果返回所传的数据为const
		{
			assert(pos >= 0 && pos < _size);
			return _str[pos];
		}
//二：
		char& operator[](size_t pos)
		{
			assert(pos >= 0 && pos < _size);
			return _str[pos];
		}
1
2
3
4
5
6
7
8
9
10
11
12

总结：
const一般是针对某种场合的作用域变量进行修饰的，比如const修饰的对象，经过
调用没有添加const修饰的函数的返回值而进行访问修改时，仍然可以被修改，因为const类修饰的是函数体内的this指针，它的作用范围只在函数体内的值不可被修改，而返回值的修改属于在外界的修改，并非在函数体内。
简单来说，const在哪里修饰，在哪里生效都是有固定规则的。

函数后面加从上const可以扩大该string类调用范围，让可读可修改的类和可读不可修改的类都能调用。

operator+=

增加一个字符，复用puch_back；
增加一个字符串，复用append；

      String& operator+=(const char ch)  //这里不能加const，*this会被修改
		{
			puch_back(ch);
			return *this;
		}
	String& operator+=(const char* s) //这里不能加const，*this会被修改
		{
			append(s);
			return *this;
		}
1
2
3
4
5
6
7
8
9
10

insert

在对应位置内插入n个字符。
1: 判断pos的数值是否具有合理性。
2：考虑是否扩容等情况。
3：将数据进行移动，留出足够的空位。
4：将n个字符拷贝到对应的位置。

//（一）

		String& insert(size_t pos,const char s)
		{
			assert(pos <= _size);
			if (_size == _capacity)                
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			size_t end = _size + 1;;
			while ( end > pos)                        //留一个空位置。
			{
				_str[end] = _str[end-1];
				--end; //不要一次性减太多，防止无符号整数为负号时会被看作很大的整数，从而导致访问越界情况。
			}
			_str[pos] = s;                           //插入位置，修改值。
			_size++;
			return *this;
		}
		
//（二）

		String& insert(size_t pos, const char* s)
		{
			assert( pos <= _size );
			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			size_t len = strlen(s);
			size_t end = _size + len;
			while (end > pos + len)  //时刻注pos的位置。
			{
				_str[end] = _str[end - len];
				--end;              // 不能使用end -= len 容易发生越界。
			}
			 //留出空位后再进行 ,再将字符串进行插入。
			strncpy(_str + pos, s, len);
			_size += len;
			return *this;
		}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

erase

删除n个pos位置后的字符。

	void erase(size_t pos, size_t len = npos) 
	 //len等于要求删除的字符个数。如果不明确写则要删除pos之后所有的字符个数或者要删除的字符的个数大于剩下的字符。
		{
			assert(pos <= _size);
			if (pos == npos || pos + len > _size)   
			//如果不显示写，全删。如果显示写了，但是要删除的数据大于pos位置之后的数据则将pos位置的数据全部删除。
			{
				_str[pos] = '\0';
				_size = pos;
			}
			else
			//进行覆盖删除。
			{
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

substr函数

从pos位置取个数为n的子字符串。
注意：
有的小伙伴们可能会觉得最后采取strncpy函数选取len长度的字符串直接拷贝更加合适，但是我们要知道s2是没有经过扩容的，这样会产生访问野指针的问题。

String substr(size_t pos, size_t len = npos) const
		{
			  
			if (len == npos )
			{
				int reallen = _size - pos;
				len = reallen;
			}
			String s2;
//尾加
			for (size_t i = pos; i < len; ++i)
			{
				s2 += _str[i];
		   }

			return s2;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

find

从pos位置处寻找符合目标字符的n个字符，遍历即可。
1：进行基本的参数判断。
2：针对不同的参数情况做出不同的回应。

//(一）对于一个字符的寻找
size_t find(const char ch, size_t pos = 0) const
		{
			assert(pos < _size);
			for (int i = pos; i < _size; i++)
			{
				if (_str[i] == ch)
				{
					return i;
				}
			}
			return npos;
		}
//(二)//对于一个字符串的查找
	size_t find(const char* sub, size_t pos = 0) const
		{
			assert(pos < _size);
			const char* ptr = strstr(_str + pos, sub);
			if (ptr == nullptr)  //如果字符串为为空直接返回npos.
			{
				return npos;
			}
			else
			{
				return  ptr - _str;    //每个字符相差一个比特位，与首地址相减就等于它们之间的下标；
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

关系运算符重载函数

在C++中，由bool类型用于判断逻辑语句真假，如果bool 等于 1，则为真，如果bool等于0，则为假。

bool operator>(String& s)
		{
			return strcmp(Return_Str(), s.Return_Str()) > 0;
		}
		bool operator==(String& s)
		{
			return strcmp(Return_Str(), s.Return_Str()) == 0;
		}
		//复用前面的，＞或者＝
		bool operator>=(String& s)
		{
			return ( * this > s) || ( *this==s);
		}

		bool operator<(String& s)
		{
			return !(* this >= s);
		}
		
		bool operator<=(String& s)
		{
			return !(*this > s);
		}
		bool operator!=(String& s)
		{
			return !(*this == s);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

>> 和 << 重载函数

1：对于>>，使用cin流并不会提取到’\0’或者’\n’，所以我们就算在屏幕上输入了’\0’也并没有让cin结束，我们不断输入，只能系统便会不断提取。
2：如果不设置缓冲区的话，当我们输入的字符的串过长，就会导致频繁扩容等问题。为了避免，我们可以设置一个特定数据的缓冲区，将流提取的字符一个个添加到缓冲区中。直到缓冲区满了之后，就插入到string类中进行扩容。并对缓冲区进行重头开始进行储存字符串。
3：在C++std库里面，我们发现当我们在原来的类中重新输入时，是会消除原来的数据而进行流提取的。所以我们在String类模拟实现中也要先清除原来类中的数据，直接将string类头位置的值设为空，并将_size的数据个数设为0即可。后面在添加字符串时会在原位置对字符串进行覆盖式输入。

   void  operator>>(istream& in, String& s)            //
	{
		s.clear(s);
        char ch;
		ch = in.get();      
		const size_t NUM = 32;
		char buffer[NUM];                         //注意数组类型。      
		size_t i = 0;
		while (ch != ' ' && ch != '\n')
		{
			buffer[i++] = ch;
			if (i == NUM - 1)                  //将字符一批一批的尾插给string类，防止频繁扩容。
			{
				buffer[i] = '\0';
				s += buffer;
				i = 0;
			}
			ch = in.get();
			//如果还在缓冲区的但是并没有将缓冲区装满的字符串应该继续进行流提取，但是还要靠考虑原来没有被覆盖的字符串
			//又正好此时i的值就为最后一个数据的下一个位置。
		}
		
		buffer[i] = '\0';
		s += buffer;
	} 
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

代码总览

using namespace std;
#include 
#include 
#include "assert.h"
#include 
#include 
namespace yzh
{
	class String
	{
	public:
		//	""代表'\0'的意思，"\0"代表字符串即'\0'后面又加了一个'\0’
		//使用迭代器来遍历。
		//深拷贝则需要使用拷贝构造
		typedef const  char* _iterator;
	   const _iterator begin() const   //字符串的首位置
		{
			return _str;
		}
	    const _iterator end() const     //字符串的最后一个数据的下一个位置。
		{
			return _str + _size;
		}


		typedef  char* iterator;
		 iterator begin()   //字符串的首位置
		{
			return _str;
		}
		 iterator end()    //字符串的最后一个数据的下一个位置。
		{
			return _str + _size;
		}
		 void clear(String& s)
		 {
			 s._str[0] = '\0';  //先销毁。
			 _size = 0;
		 }


		String(const char* str = "")  //默认构造函数
		{
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

		String(const String& s)         //拷贝构造。
			:_str(new char[s._capacity + 1])
			, _capacity(s._capacity)
			, _size(s._size)
		{
			strcpy(_str, s._str);
		}

		~String()                             //删除函数。
		{
			delete[] _str;         //如果delete的为空指针，那么delete就不会做任何事情。 
			_str = nullptr;
			_size = _capacity = 0;
		}
		char* Return_Str() const
		{
			return _str;
		}
		size_t size() const
		{
			return _size;
		}
		size_t capacity()
		{
			return _capacity;
		}
		 char& operator[](size_t pos) const  //用于被const修饰的变量传递，返回的值只可以读，不可以写。
		{
			assert(pos < _size);
			return _str[pos];
		}
		char& operator[](size_t pos)                 //取[]操作符。
		{
			assert(pos < _size);
			{
				return _str[pos];
			}
		}
		//String& operator=(const String& s)                       //赋值运算符重载
		{   
			if (this != &s)
			{ //注意s1不能给s1赋值。
				_str = new char[s._capacity + 1];      //如果new失败了它就会直接走到catch中调用catch中的语句。
				strcpy(_str, s._str);
				delete[]_str;                         //为了防止new失败，原对象反而被破环了，我们可以先拷贝完数据再删除。
				_capacity = s._capacity;
				_size = s._size;
			}
			return*this;
		}

		bool operator>(String& s)
		{
			return strcmp(Return_Str(), s.Return_Str()) > 0;
		}
		bool operator==(String& s)
		{
			return strcmp(Return_Str(), s.Return_Str()) == 0;
		}
		//复用前面的，＞或者＝
		bool operator>=(String& s)
		{
			return ( * this > s) || ( *this==s);
		}

		bool operator<(String& s)
		{
			return !(* this >= s);
		}
		
		bool operator<=(String& s)
		{
			return !(*this > s);
		}
		bool operator!=(String& s)
		{
			return !(*this == s);
		}

		void swap(String& tmp)
		{
			::swap(_str, tmp._str);
			::swap(_size, tmp._size);
			::swap(_capacity, tmp._capacity);

		}
		String(const String& s3)            //因为最后函数结束的时候tmp类会调用析构函数，着this指向的是
			:_str(nullptr)
			, _size(0)
			, _capacity(0)				   //不属于自己的空间，在析构时因进行初始化。
		{
			String tmp(s3._str);            //重新去构造一个类tmp然后再进行交换。
			swap(tmp);
		}
		String& operator=(const String& s3)
		{
			if (&s3 != this)
			{
				String tmp(s3);
				swap(tmp);
			}
			return *this;
		}


		void reserve(size_t n)          //帮助扩容，如果我需要多少字符，提前开1000个来避免扩容。
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];
				strcpy(tmp,_str);
				delete[]_str;                         //注意delete删除位置，要先删除再重新给_str赋值。
				_str = tmp;
				_capacity = n;                       //扩容之后要记得将内置变量类型属性改变。
			}
		}
		void resize(size_t n, char s = '\0')
		{
			if (n > _size)
			{
				reserve(n);
				int i;
				for (i = _size; i < n; i++)
				{
					_str[i] = s;
				}
				_str[i] = '\0';
				_size = n;
			}
			else  //如果n小于这个数的话，则要进行删除。
			{
				_str[n] = '\0';
				_size = n;
			}

		}


		void push_back(char ch)                        //一个一个字符的尾插；
		{
			if (_size == _capacity)                 //如果插满了,或者有可能为空类的情况。
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			_str[_size++] = ch;                                      //扩完了就插入一个字符。
			_str[_size] = '\0';
		}


		String& operator+=(char ch)                //复用push_back就行。
		{
			push_back(ch);
			return *this;  
		}
		String& operator+=(const char* s)
		{
			append(s);
			return *this;
		}
		void append( const char* s)
		{
			if (strlen(s) + _size > _capacity)
			{
				reserve(strlen(s) + _size);
			}
			strcpy(_str + _size, s);   // 注意使用strcat的话就会造成每次添加都要重新去找被追加数组的地址。时间的复杂度为O（n^2);
			_size += strlen(s);        //看问题以后要从代码跳出来宏观看待。
		}
		void append(const String& s)
		{
			assert(s._str);
			append(s._str);
		} 

		String& insert(size_t pos,const char s)
		{
			assert(pos <= _size);
			if (_size == _capacity)                
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			size_t end = _size + 1;;
			while ( end > pos)                        //留一个空位置。
			{
				_str[end] = _str[end-1];
				--end;
			}
			_str[pos] = s;                           //插入位置，修改值。
			_size++;
			return *this;
		}


		String& insert(size_t pos, const char* s)
		{
			assert( pos <= _size );
			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			size_t len = strlen(s);
			size_t end = _size + len;
			while (end > pos + len)
			{
				_str[end] = _str[end - len];
				--end;                           // 不能使用end -= len 容易发生越界。
			}
			 //流出空位后再进行 ,再将字符串进行插入。
			strncpy(_str + pos, s, len);
			_size += len;
			return *this;
		}


		
        
		void resize(size_t n, char s = '\0')
		{
			if ( n > _size )
			{
				reserve(n);
				int i;
				for ( i = _size; i < n; i++)
				{
					_str[i] = s;
				}
				_str[i] = '\0';
				_size = n;
			}
			else  //如果n小于这个数的话，则要进行删除。
			{
				_str[n] = '\0';
				_size = n;
			}

		}
		void erase(size_t pos, size_t len = npos)  //npos等于要求删除的字符个数。如果不明确写则要删除pos之后所有的字符个数。
		{
			assert(pos <= _size);
			if (pos == npos || pos + len > _size)   //要删除pos之后的数太多了。文字描述转化为数学关系解题。
			{
				_str[pos] = '\0';
				_size = pos;
			}
			else
			{
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
		}
		size_t find(const char ch, size_t pos = 0) const
		{
			assert(pos < _size);
			for (int i = pos; i < _size; i++)
			{
				if (_str[i] == ch)
				{
					return i;
				}
			}
			return npos;
		}
		//在一个字符串的某个位置中查找,如果找到返回一个错误码，如果没找到返回这个这个子字符串的地址。
		size_t find(const char* sub, size_t pos = 0) const
		{
			assert(pos < _size);
			const char* ptr = strstr(_str + pos, sub);
			if (ptr == nullptr)
			{
				return npos;
			}
			else
			{
				return  ptr - _str;    //每个字符相差一个比特位，与首地址相减就等于它们之间的下标；
			}
		}
		String substr(size_t pos, size_t len = npos) const
		{
			  
			if (len == npos )
			{
				int reallen = _size - pos;
				len = reallen;
			}
			String s2;
			for (size_t i = pos; i < len; ++i)
			{
				s2 += _str[i];
		   }

			return s2;
		}
		
		 const  static size_t npos = -1;                //静态成员类型的特例。
	private:
		char* _str;
		size_t _size;
		size_t _capacity;
	};
	ostream& operator <<(ostream& out, const String& s)                //为了保持让ostream和intream输入输出的合理位置，应该在类外进行定义
	{
		for( int i = 0; i < s.size(); i++)
		{
			cout << s.Return_Str()[i];
		}
		return out;
	}
	
      void  operator>>(istream& in, String& s)            //
	{
		  s.clear(s);
        char ch;
		ch = in.get();      
		const size_t NUM = 32;
		char buffer[NUM];                         //注意数组类型。      
		size_t i = 0;
		while (ch != ' ' && ch != '\n')
		{
			buffer[i++] = ch;
			if (i == NUM - 1)                  //将字符一批一批的尾插给string类，防止频繁扩容。
			{
				buffer[i] = '\0';
				s += buffer;
				i = 0;
			}
			ch = in.get();
			//如果还在缓冲区的但是并没有将缓冲区装满的字符串应该继续进行流提取，但是还要靠考虑原来没有被覆盖的字符串
			//又正好此时i的值就为最后一个数据的下一个位置。
		}
		
		buffer[i] = '\0';
		s += buffer;
	} 
	};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384