void test_vector1()
{
	string s;
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//string和vector底層都是用數(shù)組實(shí)現(xiàn)的，所以他們都支持迭代器、范圍for、下標(biāo)+[]的遍歷方式
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";//string和vector的底層都是數(shù)組，所以可以使用[]，但list就不能使用[]了，所以萬(wàn)能的方法是迭代器。
	}
	cout << endl;

	vector<int>::iterator it = v.begin();//iterator實(shí)際是某種類型的重定義，在使用時(shí)要指定好類域。
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : v)//不就是迭代器嗎？
	{
		cout << e << " ";
	}
	cout << endl;

	cout << v.max_size() << endl;//int是10億多，因?yàn)閕nt占4個(gè)字節(jié)，42億÷4。
	cout << s.max_size() << endl;//max_size的大小是數(shù)據(jù)的個(gè)數(shù)，我的編譯器的char是21億多。不用管他，這接口沒(méi)價(jià)值。

	//vector<char> vstr;
	//string str;
	//vector<char>不能替代string，即使兩者都是字符數(shù)組也不行，因?yàn)閟tring有\(zhòng)0
}

void test_vector2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	//resize和reserve對(duì)于vector和string是獨(dú)有的，對(duì)于list而言，就沒(méi)有reserve和resize

	cout << v.capacity() << endl;
	v.reserve(10);
	cout << v.capacity() << endl;
	v.reserve(4);
	cout << v.capacity() << endl;//并不會(huì)縮容，縮容并不會(huì)提高效率，縮容是有代價(jià)的，某種程度上就是以空間換時(shí)間。

	v.resize(8);//int、指針這些內(nèi)置類型的默認(rèn)構(gòu)造就把他們初始化為0和空指針這些。
	v.resize(15, 1);
	v.resize(3);//不縮容，也是采用惰性刪除的方式，將size調(diào)整為3就可以了，顯示數(shù)組內(nèi)容的時(shí)候按照size大小顯示就可以了。
}

void test_vector_expand()//擴(kuò)容機(jī)制大概是1.5倍進(jìn)行擴(kuò)容
{
	size_t sz;
	vector<int> v;

	//v.reserve(100);//已知開辟空間大小時(shí)，我們應(yīng)該調(diào)用reserve來(lái)提前預(yù)留空間，進(jìn)行擴(kuò)容。

	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';
		}
	}
}

void test_vector7()
{
	vector<int> v;
	v.reserve(10);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	
	//C++不會(huì)太推薦使用malloc來(lái)進(jìn)行空間的初始化了，因?yàn)楹苡锌赡艽嬖谧远x類型對(duì)象沒(méi)有初始化的問(wèn)題，如果用new會(huì)自動(dòng)調(diào)用構(gòu)造。

	//設(shè)計(jì)理念就是不去縮容，因?yàn)楫惖乜s容的代價(jià)很大，所以就算你用reserve或是resize調(diào)整大小以改變capacity，但編譯器不會(huì)管你。
	// 因?yàn)樗脑O(shè)計(jì)理念不允許它這么做，而遇到shrink_to_fit就沒(méi)轍了，因?yàn)樗强s容函數(shù)?。。?
	//---不動(dòng)空間，不去縮容，以空間換時(shí)間的設(shè)計(jì)理念，因?yàn)榭s容雖然空間資源多了，但是時(shí)間就長(zhǎng)了，為了提高時(shí)間，就用空間換。
	//shrink_to_fit就是反面的函數(shù)，進(jìn)行了縮容。
	v.reserve(3);
	cout << v.size() << endl;
	cout << v.capacity() << endl;

	//設(shè)計(jì)理念：以時(shí)間換空間，一般縮容都是異地縮容，代價(jià)不小，一般不要輕易使用。通常情況下，我們是不缺空間的，缺的是時(shí)間。
	v.shrink_to_fit();//縮容函數(shù)，代價(jià)很大，通常的縮容的方式，就是找一塊新的較小的空間，然后將原有數(shù)據(jù)拷貝進(jìn)去
	

	v.resize(3);
	cout << v.size() << endl;
	cout << v.capacity() << endl;

	v.clear();//clear都是不動(dòng)空間的
}

//后臺(tái)實(shí)現(xiàn)的地方：int returnSize=0;int returnColumnSizes[];
//grenerate(num,&returnSize,&returnColumnSizes);//函數(shù)調(diào)用
int** generate(int numRows, int* returnSize, int** returnColumnSizes) 
{
    int** p = (int**)malloc(numRows * sizeof(int*));
    *returnSize = numRows;
    *returnColumnSizes = (int*)malloc(sizeof(int) * numRows);
    for (int i = 0; i < numRows; i++)
    {
        p[i] = (int*)malloc(sizeof(int) * (i + 1));//給每一個(gè)二維數(shù)組的元素動(dòng)態(tài)開辟一個(gè)空間
        (*returnColumnSizes)[i] = i + 1;
        p[i][0] = p[i][i] = 1;
        //for(int j = i; j < i + 1; j++)//條件控制有問(wèn)題
        //for (int j = 0; j < i + 1 ; j++)
        for (int j = 1; j < i ; j++)
        {
            if (p[i][j]!=1)
            {
                p[i][j]=p[i-1][j-1]+p[i-1][j];
            }
        }
    }
    return p;
}

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //第二個(gè)參數(shù)不傳就是匿名對(duì)象，會(huì)自動(dòng)調(diào)用容器中元素的構(gòu)造函數(shù)。內(nèi)置類型或自定義類型的構(gòu)造。
        for(size_t i=0; i<vv.size(); i++)
        {
            vv[i].resize(i+1, 0);//給每一個(gè)vector<int>容器預(yù)留好空間并進(jìn)行初始化
            vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        }
        for(int i=0; i<vv.size(); i++)
        {
            for(int j=0; j<vv[i].size(); j++)
            {
                if(vv[i][j]==0)
                {
                    vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
                }
            }
        }
        return vv;

    }
};

void test_vector4()
{
	vector<int> v;
	v.reserve(10);
	//這是一段經(jīng)典的錯(cuò)誤代碼。reserve改變的是capacity主要解決的是插入數(shù)據(jù)時(shí)涉及到的擴(kuò)容問(wèn)題。
	//resize改變的是size，平常對(duì)于vector的容量增加，還是resize多一點(diǎn)，resize可以直接包攬reserve的活，并且除此之外還能初始化空間。
	for (size_t i = 0; i < 10; i++)
	{
		//v[i] = i;
		//對(duì)于[]的使用實(shí)際會(huì)有一個(gè)assert的越界斷言的檢查。assert(i<v.size())，你的下標(biāo)不能超過(guò)size。
		//雖然reserve的確把空間開辟好了，你也能用這個(gè)空間，但是[]他有size和下標(biāo)的越界檢查，所以你的程序就會(huì)報(bào)錯(cuò)。
		//reserve=開空間+初始化（有默認(rèn)值）
		v.at(i) = i;//拋異常

		//斷言報(bào)錯(cuò)真正的問(wèn)題是在于,release版本下面，斷言就失效了，斷言在release版本下面是不起作用的。
	}
}
int main()
{
	//test_vector1();
	//test_vector2();
	//test_vector_expand();
	try
	{
		//test_vector6();
	}
	catch (const exception& e)
	{//在這個(gè)地方捕獲異常然后進(jìn)行打印
		cout << e.what() << endl;//報(bào)錯(cuò)valid vector subscript，無(wú)效的vector下標(biāo)
	}
	//test_vector4();
	//test_vector5();
	//test_vector6();
	test_vector7();

	//string算是STL的啟蒙，string的源碼我們就不看了
	return 0;
}

void test_vector5()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//void assign(size_type n, const value_type & val);前后類型分別為size_t和模板參數(shù)T的類型typedef，那就是int類型
	v.assign(10, 1);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	//template <class InputIterator> void assign(InputIterator first, InputIterator last);
	v.assign(v1.begin(), v1.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	string str("hello world");
	v.assign(str.begin(), str.end());//assign里面的迭代器類型是不確定的，既有可能是他自己的iterator也有可能是其他容器的迭代器類型。
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.assign(++str.begin(), --str.end());//你可以控制迭代器的區(qū)間，指定assign的容器元素內(nèi)容的長(zhǎng)度。
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

}

void test_vector6()//測(cè)試insert和find
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);

	v.insert(v.begin(), 4);
	v.insert(v.begin() + 2, 4);
	//vector的迭代器能夠直接+2，源自于vector的底層是連續(xù)的空間，迭代器也就是連續(xù)的，而list的底層不是連續(xù)空間，而是一個(gè)個(gè)的節(jié)點(diǎn)，
	//所以迭代器就不能++來(lái)進(jìn)行使用了

	//如果要在vector里面的數(shù)字3位置插入一個(gè)元素的話：std::find，find的實(shí)現(xiàn)就是遍歷一遍迭代器，找到了就返回對(duì)應(yīng)位置的迭代器。
	//而vector、list、deque等容器都會(huì)用到find，所以find直接實(shí)現(xiàn)一個(gè)模板即可。
	vector<int>::iterator it = std::find(v.begin(), v.end(), 3);
	//string沒(méi)有實(shí)現(xiàn)find的原因是string不僅僅要找某一個(gè)字符，而且還要找一個(gè)字串，所以算法庫(kù)的find就不怎么適用，string就自己造輪子
	v.insert(it, 30);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector8()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	vector<int> v1;
	v1.swap(v);
	swap(v1, v);//一不小心這樣用呢？那也不會(huì)去調(diào)用算法庫(kù)里面的三次深拷貝的swap
	//這里會(huì)優(yōu)先匹配vector的類外成員函數(shù)，既然有vector作為類型實(shí)例化出來(lái)的swap函數(shù)模板，就沒(méi)有必要調(diào)用算法庫(kù)里面的模板進(jìn)行實(shí)例化
	//template <class T, class Alloc>
	//void swap(vector<T, Alloc>&x, vector<T, Alloc>&y);
}