??學(xué)習(xí)筆記，慢慢補(bǔ)充。

• 總言
• 1、整體介紹：
• 2、常用各種接口介紹
• • 2.1、vector的基本結(jié)構(gòu)：構(gòu)造、析構(gòu)、賦值
  • • 2.1.1、總體情況預(yù)覽
    • 2.1.2、各項(xiàng)函數(shù)使用演示
  • 2.2、vector增刪查改相關(guān)
  • • 2.2.1、增刪查改總覽
    • 2.2.2、如何在vector中插入、刪除、遍歷數(shù)據(jù)
    • 2.2.3、front、back函數(shù)
  • 2.3、vector擴(kuò)容相關(guān)
  • • 2.3.1、容量問題總覽
    • 2.3.2、resize、reserve函數(shù)介紹
  • 2.4、其它一些函數(shù)介紹
  • • 2.4.1、find、insert函數(shù)介紹
    • 2.4.2、erase函數(shù)介紹
    • 2.4.3、vector排序問題：sort
  • 2.5、一些現(xiàn)象、問題說明
  • • 2.5.1、一個(gè)問題討論：vector存儲(chǔ)char字符與string的比較
    • 2.5.2、vector與string結(jié)合使用：vector< string >
• 3、相關(guān)練習(xí)題：
• • 3.1、只出現(xiàn)一次的數(shù)字
  • 3.2、楊輝三角：vector>嵌套使用
  • 3.3、刪除有序數(shù)組中的重復(fù)項(xiàng)
  • 3.4、電話號(hào)碼的字母組合

??
??

?? 該文章參考網(wǎng)站是cplusplus.com。

??1、vector是類模板，其有兩個(gè)模板參數(shù)class T、class Alloc = allocator。
??2、class Alloc = allocator：空間配置器(內(nèi)存池)。默認(rèn)配置了一個(gè)缺省參數(shù)，由庫提供這個(gè)內(nèi)存池。若自己有設(shè)計(jì)想法，也可自己顯示實(shí)現(xiàn)。

??
??

??1）、構(gòu)造函數(shù)總覽

??
??
??2）、析構(gòu)函數(shù)總覽
?? vector的析構(gòu)函數(shù)，出了作用域自動(dòng)調(diào)用。

??
??
??3）、賦值運(yùn)算符重載總覽
?? 賦值運(yùn)算符重載就涉及到后續(xù)深淺拷貝的問題。

??
??4）、小結(jié)
?? 上述幾個(gè)函數(shù)中，
?? ?? ①對(duì)構(gòu)造函數(shù)，使用最多的是無參構(gòu)造、拷貝構(gòu)造。
?? ?? ②對(duì)析構(gòu)函數(shù)調(diào)用默認(rèn)的即可，故不用太過理會(huì)。
?? ?? ③對(duì)賦值運(yùn)算符重載，偶爾用到。
??
??
??
??

??1）、演示構(gòu)造函數(shù)：

??①由下述代碼可知，vector是一個(gè)類模板，因此需要顯示實(shí)例化(詳細(xì)學(xué)習(xí)請(qǐng)見模板初階)。

template< class T, class Alloc = allocator>class vector;

??②以下即為常見的vector的構(gòu)造用法：

void test_vector01()
{vectorv1;//無參構(gòu)造
	vectorv2(5, 10);//n個(gè)val
	vectorv3(v2);//拷貝構(gòu)造
}

??③通過調(diào)試觀測如下：需要注意的是，對(duì)于vector的構(gòu)造函數(shù)，后續(xù)我們?cè)谀M實(shí)現(xiàn)時(shí)仍舊要解決深淺拷貝的問題。

??
??
??
??

??
??

??1）、對(duì)數(shù)據(jù)插入、刪除：
?? 根據(jù)上述總覽，目前我們知道可以使用push_back、pop_back、insert、erase來達(dá)成數(shù)據(jù)的插入刪除。

vectorv1;//構(gòu)造一個(gè)vector,名為v1
		v1.push_back(1);//尾插
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

??
??2）、對(duì)數(shù)據(jù)的遍歷：

方式一：下標(biāo)+[ ]

?? 相關(guān)函數(shù)：


?? 代碼演示：

//遍歷演示
		for (size_t i = 0; i< v1.size(); ++i)//vector::size
		{	cout<< v1[i]<< " ";//vector::operator[]
		}
		cout<< endl;

		//下標(biāo)訪問，遍歷自增
		for (size_t i = 0; i< v1.size(); ++i)
		{	v1[i]++;
		}

		//再次遍歷
		for (size_t i = 0; i< v1.size(); ++i)//vector::size
		{	cout<< v1[i]<< " ";//vector::operator[]
		}
		cout<< endl;

??
??

方式二：迭代器

?? 代碼演示：

//使用迭代器遍歷:需要注意的是這里迭代器對(duì)應(yīng)的vector使用了模板參數(shù)
		vector::iterator it = v1.begin();
		while (it != v1.end())
		{	cout<< *it<< " ";
			++it;
		}
		cout<< endl;

?? 涉及函數(shù)：

?? 支持迭代器，就支持范圍for：

//使用范圍for
		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;

??
??

??1）、簡介：
?? 獲取vector首元素和尾元素。 關(guān)于front和back二者的使用請(qǐng)見下述練習(xí)3.2。

??

??
??

??1）、擴(kuò)容機(jī)制的驗(yàn)證

//擴(kuò)容機(jī)制驗(yàn)證
	void TestVectorExpand()
	{size_t sz;
		vectorv;
		sz = v.capacity();

		cout<< "making v grow:\n";
		for (int i = 0; i< 100; ++i)
		{	v.push_back(i);
			if (sz != v.capacity())
			{		sz = v.capacity();
				cout<< "capacity changed: "<< sz<< '\n';
			}
		}
	}

??此處是以VS2019為例的運(yùn)行結(jié)果：

??
??2）、reserve、rsize介紹
?? 在已知要插入的數(shù)據(jù)量的情況下，我們可以提前擴(kuò)容：

void TestVectorExpand()
	{size_t sz;
		vectorv;
		//v.resize(100);//resize在開空間的同時(shí)還會(huì)進(jìn)行初始化，影響size。
		v.reserve(100);//reserve只負(fù)責(zé)開辟空間，可緩解vector增容的代價(jià)缺陷問題。
		sz = v.capacity();

		cout<< "making v grow:\n";
		for (int i = 0; i< 100; ++i)
		{	v.push_back(i);
			if (sz != v.capacity())
			{		sz = v.capacity();
				cout<< "capacity changed: "<< sz<< '\n';
			}
		}
	}

?? 在上述場景中不能使用resize，因?yàn)閞esize在開辟空間的同時(shí)進(jìn)行初始化數(shù)據(jù)。假如上述場景中使用了resize，相當(dāng)于我已經(jīng)在resize的幫助下?lián)碛辛?00個(gè)數(shù)據(jù)，后續(xù)的for循環(huán)又為我提供了100個(gè)數(shù)據(jù)。

??
??

??1）、對(duì)algorithm
?? 在vector中，可以看到并沒有單獨(dú)的find函數(shù)，是因?yàn)槲覀兺耆梢杂肹 ]來做到，另者，如果有需要，algorithm庫中提供了find函數(shù)。

??同理，vector也不像string一樣提供流插入、流提取。因?yàn)槲覀儗?duì)vector的一般是遍歷訪問，而string有整體打印字符串的需求。
??
??
??2）、對(duì)vector::insert
?? vector中insert的用法說明：注意iterator position，其使用的是迭代器。

iterator is a member type, defined as a random access iterator type that points to elements.

??
??3）、使用演示

vectorv1;//構(gòu)造一個(gè)vector,名為v1
		v1.push_back(1);//尾插
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		//使用find在v1中查找值：范圍[v1.begin(),v1.end()),val=3
		vector::iterator pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())//檢查是否找到相關(guān)值。此處find的last=v1.end()
		{	v1.insert(pos,30);
		}
		//遍歷：用于檢測是否成功插入數(shù)據(jù)
		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;

??
??
??4）、一個(gè)邊界說明
?? 如下圖，分析現(xiàn)象并說明原因：

?? 原因：在v1中尋找300，find返回結(jié)果為v1.end()下標(biāo)，相當(dāng)于尾插。
?? 說明：雖然此處沒有明確報(bào)錯(cuò)現(xiàn)象，但使用find找到值后最好還是檢查一下。
??
??

??1）、對(duì)erase

??2）、使用演示：

vectorv1;//構(gòu)造一個(gè)vector,名為v1
		v1.push_back(1);//尾插
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		//使用find在v1中查找值：范圍[v1.begin(),v1.end()),val=3
		vector::iterator pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())//檢查是否找到相關(guān)值。此處find的last=v1.end()
		{	v1.erase(pos);//刪除單個(gè)元素
		}
		
		//遍歷：用于檢測是否成功插入數(shù)據(jù)
		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;

??3）、不檢查find返回值情況驗(yàn)證：
?? 如下圖所示：報(bào)錯(cuò)。

??
??
??

??1）、基本介紹
?? ①sort也是一個(gè)函數(shù)模板，其底層使用的原理是快排，默認(rèn)排的是升序。

??
??2）、sort排升序

//亂序
		vectorv1;
		v1.push_back(11);
		v1.push_back(23);
		v1.push_back(6);
		v1.push_back(1);
		v1.push_back(9);
		v1.push_back(7);
		v1.push_back(3);
		v1.push_back(15);
		//排升序
		sort(v1.begin(), v1.end());
		//遍歷查看
		vector::iterator it = v1.begin();
		while (it != v1.end())
		{	cout<< *it<< " ";
			it++;
		}
		cout<< endl;

??
??3）、sort排降序
?? sort排降序涉及到Compare comp仿函數(shù)，此處我們只需要學(xué)習(xí)使用方法：
?? 兩個(gè)函數(shù)介紹：less、greater

介紹：
		less也是一個(gè)類模板，int為此處需要的數(shù)據(jù)類型
		greater同上，但使用greater需要包含頭文件。
		less不需要包含的這個(gè)頭文件的原因是，sort默認(rèn)升序。
		

		#includelessls;
		greatergt;
		
		//sort(v1.begin(), v1.end(), ls);
		sort(v1.begin(), v1.end(), gt);

??當(dāng)然，上述只是一種寫法介紹，也可以按照下述寫法進(jìn)行：

sort(v1.begin(), v1.end(), greater());

??此處相當(dāng)于匿名對(duì)象的使用。

??
??
??4）、sort在string中的使用演示

string s("hello string 1144579");
		sort(s.begin(), s.end());
		cout<< s<< endl;

?? sort在string中是按照ASCII碼排序的：

?? 也可以排降序：

string s("hello string 1144579");
		sort(s.begin(), s.end(), greater());
		cout<< s<< endl;

??
??
??

?? 問題描述：

vectorv;
		string s;

?? 上述二者有什么差異？能否用前者代替后者？
?? 回答：
?? ①string中s后面默認(rèn)追加\0；
?? ②相比于vector，string中的相關(guān)函數(shù)比較多，實(shí)現(xiàn)功能也更全，比如+=(一個(gè)字符/字符串)，流插入流提取，find(查字符串)，比較大小、to_string等。
??
??
??

//void push_back (const value_type& val);
		//void push_back (const T& val);

		vectorstrV;

		string str1("張龍");
		strV.push_back(str1);//深拷貝：push_back中val為什么要加&的原因

		strV.push_back(string("趙虎"));//匿名對(duì)象：push_back中val為什么要加const的原因

		strV.push_back("王朝");//日常使用習(xí)慣：隱式類型轉(zhuǎn)換

//for (auto str : strV)
		//{//	cout<< str<< endl;
		//}
		
		//1、這里也涉及一個(gè)深淺拷貝的問題，所以需要十分謹(jǐn)慎處理
		//2、如果不涉及改變內(nèi)容，可以加上const
		for (const auto& str : strV)
		{	cout<< str<< endl;
		}

??
??
??

?? 題源

?? 代碼如下：

class Solution {public:
    int singleNumber(vector& nums) {int value=0;
        for(auto e:nums)
        {value^=e;//異或
        }
        return value;
    }
};

?? 要滿足時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)，最簡單的方式就是使用異或。
?? 其余不滿足上述條件下，也可以使用排序遍歷、直接遍歷等方法。
??
??
??

class Solution {public:
    vector>generate(int numRows) {vector>vv;//定義一個(gè)vector>類型的數(shù)據(jù)
        vv.resize(numRows);//第一次開辟空間：numRows，表示總行數(shù)(整體大小)
        for(size_t i=0;ivv[i].resize(i+1,0);//第二次開辟空間，表示初始化楊輝三角的每行大小
            vv[i].front()=vv[i].back()=1;//楊輝三vv.size()角每行首尾數(shù)據(jù)為1

            //vv[i].resize(i+1,1);//上述代碼也可以合并為一行實(shí)現(xiàn)
        }

        for(size_t i=2;ifor(size_t j=1;jvv[i][j]=vv[i-1][j-1]+vv[i-1][j];
            }
        }

        return vv;
    }
};

int removeDuplicates(int* nums, int numsSize){int src,det;
det=0;src=1;
while(srcif(nums[src]!=nums[det])
    {nums[++det]=nums[src];
    }
    src++;
}
return det+1;
}

class Solution {public:
    int removeDuplicates(vector& nums) {int src,det;
    det=0;src=1;
    while(srcif(nums[src]!=nums[det])
        {nums[++det]=nums[src];
        }
        src++;
    }
    return det+1;
    }
};

nums.riseze(det+1);//此處det+1是因?yàn)槲覀冚斎氲膎是數(shù)據(jù)個(gè)數(shù)，而det標(biāo)記的是下標(biāo)。

class Solution {//numToStr：主要是用于映射2-9數(shù)字對(duì)應(yīng)的字母
    char* numToStr[10]={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    //string numToStr[10]={"","","abc","def","ghi"."jkl","mno","pqrs","tuv","wxyz"};

public:

    //digits:系統(tǒng)輸入的數(shù)字字符串
    //di：這些字符串對(duì)應(yīng)的順序：第一個(gè)、第二個(gè)
    //retV：用于存儲(chǔ)獲取的排列組合，總數(shù)目
    //combineStr：用于存儲(chǔ)單次遞歸獲取的組合
    void Combine(string digits,int di,vector& retV,string combineStr)
    {if(di==digits.size())
        {retV.push_back(combineStr);
            return;
        }
        
        int num=digits[di]-'0';//將輸入的數(shù)字字符轉(zhuǎn)換為數(shù)字
        string str=numToStr[num];//當(dāng)前數(shù)字對(duì)應(yīng)的字母
        for(auto ch :str)
        {Combine(digits,di+1,retV,combineStr+ch);
        }
    }



    vectorletterCombinations(string digits) {vectorv;
        if(digits.empty())//如果輸入的字符串為空時(shí)
        {return v;
        }
        string str;
        Combine(digits,0,v,str);
         return v;
    }
};