STL實踐與分析

--順序容器的定義、迭代器

一、順序容器的定義

順序容器

容器適配器

vector

支持快速隨機訪問

stack

後進先出(LIFO)

list

支持快速插入/刪除

queue

先進先出(FIFO)

deque

雙端隊列

priority_queue

有優先級管理的隊列

1、容器類型的操作集合形成了以下層次結構：

1）一些操作適用於所有容器類型；

2）另外一些操作只適用於順序或關聯容器；

3）還有一些操作只適用於順序或關聯容器類型的一個子集。

2、容器構造函數

Cc;

創建一個名為c的空容器。C是容器類型名,如vector,T是元素類型,如int或string適用於所有容器

Cc(c2);

創建容器c2的副本c;c和c2必須具有相同的容器類型,並存放相同類型的元素。適用於所有容器。

Cc(b,e);

創建c,其元素是迭代器b和e標示的范圍內元素的副本。

適用於所有容器

Cc(n, t);

用n個值為t的元素創建容器c,其中值t必須是容器類型C的元素類型的值,或者是可轉換為該類型的值。

只適用於順序容器

Cc(n);

創建有n個值初始化元素的容器c

只適用於順序容器

3、將一個容器初始化為另一個容器的副本

將一個容器復制給另一個容器時，類型必須匹配：容器類型和元素類型都必須完全相同。

	vector ivec;
	vector ivec2(ivec);	//OK
	vector dvec(ivec);	//Error
	list ilist(ivec);		//Error

4、初始化為一段元素的副本

系統允許通過一對迭代器間接實現不同種容器之間進行復制：使用迭代器時，不要求容器類型相同，容器內元素類型也可以不相同，只要他們相互兼容，能夠將要復制的元素轉換為所構建的新容器的元素類型，即可實現復制。

    vector svec;
    //...
    list slist(svec.begin(),svec.end());	//OK

    vector::iterator mid = svec.begin() + svec.size()/2;
    deque front(svec.begin(),mid);			//OK
    deque back(mid,svec.end());				//OK

    char *word[] = {"stately","plump","buck","mulligan"};
    list slist2(word,word + sizeof(word)/sizeof(*word));	//OK

    vector ivec;
    //...
    vector dvec(ivec.begin(),ivec.end());	//OK

5、分配和初始化指定數目的元素

不提供元素初始化式時，標准庫將為該容器實現值初始化，采用這種類型的初始化，元素類型必須是內置或復合類型，或者是提供了默認構造函數的類類型。如果元素類型沒有默認構造函數，則必須顯式的指定其元素初始化式。

接受容器大小做形參的構造函數只適用於順序容器，而關聯容器不支持這種初始化。

	const list::size_type list_size = 64;
	list ilist(list_size);		//OK
	list slist(list_size);	//OK

        list strList(list_size,"Ha~");	//OK

//P267 習題9.2
	vector strVec1;
	vector strVec2(strVec1);
	vector strVec3(strVec2.begin(),strVec2.end());
	vector strVec4(strVec3.size());
	vector strVec5(strVec4.size(),"ANS");

6、容器內元素的約束

C++語言中,大多數類型都可用作容器的元素類型。容器元素類型必須滿足

以下兩個約束:

?元素類型必須支持賦值運算。

?元素類型的對象必須可以復制。

容器操作的特殊要求

支持復制和賦值功能是容器元素類型的最低要求。此外,一些容器操作對元素類型還有特殊要求。如果元素類型不支持這些特殊要求,則相關的容器操作就不能執行:我們可以定義該類型的容器,但不能使用某些特定的操作。

class Foo
{
public:
    Foo(int x)
    {

    }
};

int main()
{
    vector empty;		//OK
    vector bad(10);	//Error
    vector ok(10,1);	//OK
}

有在同時指定每個元素的初始化式時,才能使用給定容器大小的構造函數來創建同類型的容器對象。

7、容器的容器

因為容器受容器類型的約束，所以可定義元素是容器的容器：

	vector< vector > vvec;

【注意：】

在指定容器元素為容器類型時,必須如下使用空格：

	vector< vector > vvec;		//OK
	vector< vector> bad_vvec;	//Error

//P268 習題9.4
	list< deque > dList;

//習題9.6
class Foo
{
public:
    Foo(int x)
    {

    }
};

int main()
{
	list FList(10,1);
}

二、迭代器和迭代器范圍

所有標准庫都提供的迭代器運算

*iter

返回迭代器iter所指向的元素的引用

iter-> mem

對iter進行解引用,獲取指定元素中名為mem的成員。等效於(*iter).mem

++iter/iter++

給iter加1,使其指向容器裡的下一個元素

--iter/iter--

給iter減1,使其指向容器裡的前一個元素

iter1== iter2

iter1!= iter2

比較兩個迭代器是否相等(或不等)。當兩個迭代器指向同一個iter2容器中的同一個元素,或者當它們都指向同一個容器的超出末端iter1!=的下一位置時,兩個迭代器相等.

vector和deque類型迭代器支持的操作

iter+ n

iter- n

在迭代器上加(減)整數值n,將產生指向容器中前面(後面)第n個元素的迭代器。新計算出來的迭代器必須指向容器中的元素或超出容器末端的下一位置

iter1+= iter2

iter1-= iter2

這裡迭代器加減法的復合賦值運算:將iter1加上或減去iter2的運算結果賦給iter1

iter1- iter2

兩個迭代器的減法,其運算結果加上右邊的迭代器即得左邊的迭代器。這兩個迭代器必須指向同一個容器中的元素或超出容器末端的下一位置

只適用於vector和deque容器

>,>=,<,<=

迭代器的關系操作符。當一個迭代器指向的元素在容器中位於另一個迭代器指向的元素之前,則前一個迭代器小於後一個迭代器。關系操作符的兩個迭代器必須指向同一個容器中的元素或超出容器末端的下一位置

只適用於vector和deque容器

關系操作符只適用於vector和deque容器，因為只有這兩種容器為其元素提供快速、隨機的訪問。

    vector ivec;
    //...
    vector::iterator mid = ivec.begin() + ivec.size()/2;	//OK

    list ilist(ivec.begin(),ivec.end());
    list::iterator iter = ilist.begin() + ilist.size()/2;	//Error
    list::iterator iter1 = ilist.begin(),
                        iter2 = ilist.end();
    if (iter1 < iter2)	//Error
    {
        //...
    }

list容器的迭代器既不支持算術運算符，也不支持關系運算符，它只是提供前置/後置的自增、自減運算以及相等/不等運算。

//P270 習題9.9
int main()
{
    list iList;
    for (size_t i = 0; i != 15; ++i)
    {
        iList.push_back(i+1);
    }
    for (list::iterator iter = iList.end(); iter != iList.begin();)
    {
        cout << *(--iter) << endl;
    }
}

1、對形成迭代器范圍的迭代器的要求

迭代器 first和last如果滿足以下條件,則可形成一個迭代器范圍:

?它們指向同一個容器中的元素或超出末端的下一位置。

?如果這兩個迭代器不相等,則對first反復做自增運算必須能夠到達last。換句話說,在容器中,last絕對不能位於first之 前。【P270，編譯器自己也不能保證上述要求】

2、使用左閉右開區間的意義

1）當first與last相等，迭代器范圍為空

2）當first與last不相等時，迭代器范圍內至少有一個元素：size= last – fist

//P271 習題9.12
bool findVal(vector::const_iterator beg,vector::const_iterator end,int val)
{
	while (beg != end)
	{
		if (*beg == val)
		{
			return true;
		}
		++ beg;
	}
	return false;
}

int main()
{
	vector ivec;
	for (int i = 0;i != 20; ++i)
	{
		ivec.push_back(i);
	}
	vector::const_iterator mid = ivec.begin() + ivec.size()/2;
	cout << findVal(ivec.begin(),ivec.end(),10) << endl;
	cout << findVal(ivec.begin(),mid,10) << endl;
}

//習題9.13
vector::const_iterator findVal(vector::const_iterator beg,
                                    vector::const_iterator end,
                                    int val)
{
    while (beg != end)
    {
        if (*beg == val)
        {
            return beg;
        }
        ++ beg;
    }
    return beg;
}

//習題9.14
int main()
{
//	freopen("input","r",stdin);
	vector strVec;
	string val;
	while (cin >> val)
	{
		strVec.push_back(val);
	}
	for (vector::iterator iter = strVec.begin(); iter != strVec.end(); ++iter)
	{
		cout << *iter << endl;
	}
}

//習題9.15
int main()
{
//	freopen("input","r",stdin);
    list strVec;	//修改vector -> list
    string val;
    while (cin >> val)
    {
        strVec.push_back(val);
    }
    //修改vector -> list
    for (list::iterator iter = strVec.begin(); iter != strVec.end(); ++iter)
    {
        cout << *iter << endl;
    }
} 

3、使迭代器失效的容器操作

一些容器的操作會修改容器的內在狀態或移動容器內的元素。這樣的操作使所有指向被移動的元素的迭代器失效,也可能同時使其他迭代器失效。使用無效迭代器是沒有定義的,可能會導致與懸垂指針相同的問題。使用無效迭代器將會導致嚴重的運行時錯誤。

無法檢查迭代器是否有效,也無法通過測試來發現迭代器是否已經失效。任何無效迭代器的使用都可能導致運行時錯誤,但程序不一定會崩潰,否則檢查這種錯誤也許會容易些o(∩∩)o...。

【建議：】

使用迭代器時,通常可以編寫程序使得要求迭代器有效的代碼范圍相對較短。 然後,在該范圍內,嚴格檢查每一條語句,判斷是否有元素添加或刪除,從而相應地調整迭代器的值。