更多算法例題鏈接: 【數(shù)據(jù)結構與算法】遞推法和遞歸法解題（遞歸遞推算法典型例題）

C++ 內(nèi)置模板(STL)

迭代器講解

什么是迭代器(iterator)

迭代器(iterator)的定義：迭代器是一種檢查容器內(nèi)元素并遍歷元素的數(shù)據(jù)類型。
迭代器提供對一個容器中的對象的訪問方法，并且定義了容器中對象的范圍。
容器vector和string有迭代器類型同時擁有返回迭代器的成員。

如：容器有成員 .begin() 和 .end()，其中 .begin() 成員復制返回指向第一個元素的迭代器，即指向第一個元素的“地址”，而 .end() 成員返回指向容器尾元素的下一個位置的迭代器.
即 .begin() 指向的是第一個合法元素的位置，.end() 指向是容器后第一個不合法元素的地址。

示例
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(4);
    nums.push_back(8);
    nums.push_back(16);

    vector<string> fruits;
    fruits.push_back("orange");
    fruits.push_back("apple");
    fruits.push_back("raspberry");

    vector<char> empty;

    // 求和 vector nums 中的所有整數(shù)（若存在），僅打印結果。
    int sum = 0;
    for (vector<int>::iterator it = nums.begin(); it != nums.end(); ++it)
        sum += *it;
    cout << "Sum of nums: " << sum << "\n";

    // 打印 vector fruits 中的首個 fruis ，不檢查是否有一個。
    if (!fruits.empty())
        cout << "First fruit: " << fruits.front() << "\n";

    if (empty.empty())
        cout << "vector 'empty' is indeed empty.\n";
    
    return 0;
}

/*輸出：
Sum of nums: 31
First fruit: orange
vector 'empty' is indeed empty
*/

相應的還有容器反向迭代器成員 .rbegin() .rend()，.rbegin() 返回容器的元素前最后一個不合法的地址，rend() 返回容器的最后一個合法地址。

容器迭代器的使用

每種容器類型都定義了自己的迭代器類型：
vector：vector<int>::iterator iter;//定義一個名為iter的變量

數(shù)據(jù)類型是由vector<int>定義的 iterator 類型。簡單說就是容器類定義了自己的 iterator 類型，用于訪問容器內(nèi)的元素。每個容器定義了一種名為iterator的類型，這種類型支持迭代器的各種行為。

容器(vector)(線性表的使用)

Vector 容器（類:線性表中有 vector 和 list，兩者作用比較相似。vector 的主要作用就是可變長度的數(shù)組，就把他當成數(shù)組使用即可。

#include <iostream>
#include <vector>
 
int main()
{
    // 創(chuàng)建含有整數(shù)的 vector
    std::vector<int> v = {7, 5, 16, 8};
 
    // 將二個整數(shù)添加到 vector
    v.push_back(25);
    v.push_back(13);
 
    // 迭代并打印 vector 的值
    std::cout << "v = { ";
    for (int n : v)
        std::cout << n << ", ";
    std::cout << "};\n";
}

/*輸出：
v = { 7, 5, 16, 8, 25, 13, };
*/

1. vector容器的定義

#include <vector>   //頭文件
vector<int> a;      //定義了一個int類型的vector容器a
vector<int> b[100]; //定義了一個int類型的vector容器b組

struct rec
{
    ···
};

vector<rec> c;            //定義了一個rec類型的vector容器c
vector<int>::iterator it; //vector的迭代器，與指針類似

2. vector容器的操作

a.size()           //返回實際長度（元素個數(shù)），O(1)復雜度
a.empty()      //容器為空返回1，否則返回0，O(1)復雜度
a.clear()      //把vector清空
a.begin()      //返回指向第一個元素的迭代器，*a.begin()與a[0]作用相同
a.end()        //越界訪問，指向vector尾部，指向第n個元素再往后的邊界
a.front()      //返回第一個元素的值，等價于*a.begin和a[0]
a.back()       //返回最后一個元素的值，等價于*--a.end()和a[size()-1]
a.push_back(x) //把元素x插入vector尾部
a.pop_back()   //刪除vector中最后一個元素

3. 遍歷容器的方法

(1)迭代器使用與指針類似，可如下遍歷整個容器。

 for ( vector<int>::iterator it=a.begin() ; it!=a.end() ; it++ )
    cout<<*iterator<<endl;

(2) 當成數(shù)組使用。

for( int i=0;i<a.size();i++) cout<<a[i]<<endl;

代碼示例：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    // 創(chuàng)建含有整數(shù)的 vector
    vector<int> v ;
    v.push_back(7);
    v.push_back(5);
    v.push_back(16);
    v.push_back(8);
 
    // 將二個整數(shù)添加到 vector
    v.push_back(25);
    v.push_back(13);
 
    // 迭代并打印 vector 的值
    cout << "v = { ";
    for ( vector<int>::iterator it=v.begin() ; it!=v.end() ; it++ )
        cout << *it << ", ";
    cout << "};\n";
    cout << "v = { ";
    for (int j = 0; j < v.size(); ++j) {
            cout << v[j] << ", ";
        }
    cout << "};\n";
}

隊列的使用

隊列的使用:
1.queue的定義方法

queue<string> myqueue;
queue<int> myqueue_int;

2. queue的基本操作

front()：返回 queue 中第一個元素的引用。
back()：返回 queue 中最后一個元素的引用。
push(const T& obj)：在 queue 的尾部添加一個元素的副本。
pop()：刪除 queue 中的第一個元素。
size()：返回 queue 中元素的個數(shù)。
empty()：如果 queue 中沒有元素的話，返回 true

集合（set）的使用

在C++中，set是一個基于紅黑樹實現(xiàn)的關聯(lián)容器，它可以自動將元素排序并保持唯一性。默認情況下，set使用元素類型的<運算符來比較和排序其元素。如果你想要一個自定義的排序準則，可以在聲明set時指定一個比較函數(shù)或函數(shù)對象。

#include <bits/stdc++.h>
using namespace std;

// 1.set 的定義 set<數(shù)據(jù)類型> 變量名

set<int> intSet;
set<string> stringSet;

int main()
{
    string s1="測試1";
    string s2="測試2";
    string s3="測試3";

    //2. 插入操作
    stringSet.insert(s3);
    stringSet.insert(s1);

    //5. 返回集合元素數(shù)量
    printf("前2次插入操作完成后的元素數(shù)量為%d\n",stringSet.size());
    stringSet.insert(s2);
    printf("前3次插入操作完成后的元素數(shù)量為%d\n",stringSet.size());

    //6.遍歷整個集合，借助迭代器實現(xiàn)
    //定義方式   容器類型< type> ::iterator name
    set<string> ::iterator  setStringIterator;
    for(setStringIterator=stringSet.begin();setStringIterator!=stringSet.end();setStringIterator++)
        cout<<*setStringIterator<<" ";
    puts("");

    //3. 刪除操作
    stringSet.erase(s3);
    printf("刪除操作完成后的元素數(shù)量為%d\n",stringSet.size());

    for(setStringIterator=stringSet.begin();setStringIterator!=stringSet.end();setStringIterator++)
        cout<<*setStringIterator<<" ";
    puts("");

    //4. 判斷是否由此元素
    if(stringSet.count(s2)!=0) cout<<"存在元素"<<s2<<endl;
}

映射（map）的使用

map 是一個關聯(lián)容器，它提供一對一的 hash。

第一個可以稱為關鍵字(key)，每個關鍵字只能在 map 中出現(xiàn)一次
第二個可能稱為該關鍵字的值(value)

map 以模板（泛型）方式實現(xiàn)，可以存儲任意類型的數(shù)據(jù)，包括使用者自定義的數(shù)據(jù)類型。Map 主要用于資料一對一映射（one-to-one）的情況，map 在 C++ 的內(nèi)部的實現(xiàn)自建一顆紅黑樹，這顆樹具有對數(shù)據(jù)自動排序的功能。在 map 內(nèi)部所有的數(shù)據(jù)都是有序的。
比如，像是管理班級內(nèi)的學生，Key 值為學號，Value 放其他信息的結構體或者類。

1. map 的定義：

//map的定義
map<char, int> mymap1;
map<string, int> mymap2;

2. 容量：

int map.size();//查詢map中有多少對元素
bool empty();// 查詢map是否為空

3. 插入

    map.insert(make_pair(key,value));
    //或者
    map.insert(pair<char, int>(key, value))
    //或者
    map[key]=value

4. 遍歷

map<string, string>::iterator it;
for (it = mapSet.begin(); it != mapSet.end(); ++it)
{
    cout << "key" << it->first << endl;

    cout << "value" << it->second << endl;
}

5. 查找

m.count(key)：//由于map不包含重復的key，因此m.count(key)取值為0，或者1，表示是否包含。
m.find(key)：//返回迭代器，判斷是否存在。

整體應用代碼示例：

#include<bits/stdc++.h>
//#include<vector>
//#include<stack> 
//#include<string>
//#include<queue> 
//#include<deque>
//#include<map>
using namespace std;

//map是每個鍵對應一個值
//映射類似于函數(shù)的對應關系，每個x對應一個y.

//map特性：map會按照鍵的順序從小到大自動排序，鍵的類型必須可以比較大小
void test01(){
	//初始化定義
	map<int, string> mp;

    // 插入元素
    mp.insert(make_pair(1, "One"));
    mp.insert(make_pair(2, "Two"));
    mp.insert(make_pair(3, "Three"));
    mp.insert(make_pair(4, "Four"));

    // 查看元素是否存在
    if (mp.count(2) > 0) {
        cout << "Key 2 exists!" << endl;
    }

    // 查找元素
    map<int,string>::iterator it = mp.find(3);
    if (it != mp.end()) {
        cout << "Value of key 3: " << it->second << std::endl;
    }

    // 刪除元素
    mp.erase(2); // 通過鍵刪除元素
    mp.erase(mp.find(4)); // 通過迭代器刪除元素

    // 清空map
    mp.clear();

    // 判斷map是否為空
    if (mp.empty()) {
        cout << "Map is empty!" << std::endl;
    }
}

void test02(){
	
	/*mp.find(key) 返回鍵為key的映射的迭代器 $O(logN) 
	注意：用find函數(shù)來定位數(shù)據(jù)出現(xiàn)位置，它返回一個迭代器。當數(shù)據(jù)存在時，返回數(shù)據(jù)所在位置的迭代器，數(shù)據(jù)不存在時，返回mp.end() 
	mp.erase(it) 刪除迭代器對應的鍵和值O(1)
	mp.erase(key) 根據(jù)映射的鍵刪除鍵和值 O(logN) 
	mp.erase(first,last) 刪除左閉右開區(qū)間迭代器對應的鍵和值 O(last-first) 
	mp.size() 返回映射的對數(shù)$ O(1)$ mp.clear() 清空map中的所有元素O(N) 
	mp.insert() 插入元素，插入時要構造鍵值對 
	mp.empty() 如果map為空，返回true，否則返回false 
	mp.begin() 返回指向map第一個元素的迭代器（地址） 
	mp.end() 返回指向map尾部的迭代器（最后一個元素的下一個地址） 
	mp.rbegin() 返回指向map最后一個元素的迭代器（地址） 
	mp.rend() 返回指向map第一個元素前面(上一個）的逆向迭代器（地址） 
	mp.count(key) 查看元素是否存在，因為map中鍵是唯一的，所以存在返回1，不存在返回0 
	mp.lower_bound() 返回一個迭代器，指向鍵值>= key的第一個元素 
	mp.upper_bound() 返回一個迭代器，指向鍵值> key的第一個元素
	*/
}


void test03(){
	map<int,int> mp;
	mp[1] = 2;
	mp[2] = 3;
	mp[3] = 4;
	map<int,int>::iterator it = mp.begin();
	while(it != mp.end()) {
		cout << it->first << " " << it->second << "\n";
		it ++;
	}
	cout<<"******"<<endl;
	map<int,int> mp1;
	mp1[1] = 2;
	mp1[2] = 3;
	mp1[3] = 4;
	map<int,int>::reverse_iterator it1 = mp1.rbegin();
	while(it1 != mp1.rend()) {
		cout << it1->first << " " << it1->second << "\n";
		it1 ++;
	}

}

void test04(){
	map<int, int> m;
    m.insert(make_pair(1, 2));
    m.insert(make_pair(2, 2));
    m.insert(make_pair(1, 2));
    m.insert(make_pair(8, 2));
    m.insert(make_pair(6, 2));
	map<int, int>::iterator it1 = m.lower_bound(2); 
	cout << it1->first << "\n";//it1->first=2 
	map<int, int>::iterator it2 = m.upper_bound(2); 
	cout << it2->first << "\n";//it2->first=6
	//?? 為什么不是8 
	cout<<"***"<<endl;
	
	map<int,int>::iterator it = m.begin();
	while(it != m.end()) {
		cout << it->first << " " << it->second << "\n";
		it ++;
	}

}

int main()
{
	cout<<"test01():"<<endl;
	test01();
	cout<<"************"<<endl;
	cout<<"test02():"<<endl;
	test02();
	cout<<"************"<<endl;
	cout<<"test03():"<<endl;
	test03();
	cout<<"************"<<endl;
	cout<<"test04():"<<endl;
	test04();
	
	return 0;
}

算法設計例題

例題一：（容器vector）快遞的分揀

樣例：
輸入：

10 
10124214 北京
12421565  上海
sdafasdg213 天津
fasdfga124 北京
145252  上海
235wtdfsg 濟南
3242356fgdfsg 成都
23423 武漢  
23423565f 沈陽
1245dfwfs 成都

輸出：

北京 2
10124214
fasdfga124
上海 2
12421565
145252
天津 1
sdafasdg213
濟南 1
235wtdfsg
成都 2
3242356fgdfsg 
1245dfwfs 
武漢 1
23423
沈陽 1
23423565f 

題解：

//1. 創(chuàng)建有個vector容器 用來保存地址
vector<string> city;
//2. 再創(chuàng)建一個 用來保存快遞單號
vector<string> dig[1000];
//3. 定義一個映射函數(shù)，因為城市可能會再次出現(xiàn)，我們需要知道之前有沒有。
//4. 讀入操作并按照順序進行存放

題解示例：

#include<iostream>
#include<vector>
using namespace std;

//創(chuàng)建有個vector容器 用來保存地址
vector<string> city;
//再創(chuàng)建一個 用來保存快遞單號
vector<string> dig[1000];

int Myfind(string s){
    //尋找到該城市的位置 下標
    for(int i=0;i<city.size();i++)
    {
        if(city[i]==s) return i;
    }
    return -1;
}

int main()
{

    int n;
    cin>>n;//輸入有幾個快遞

    for(int i=0;i<n;i++)
    {
        string d,c;
        
        cin>>d>>c;///輸入快遞單號 和 快遞地址
        int flag=Myfind(c);//輸出該地址的位置
        if(flag==-1){//如果沒找到這個地址
            city.push_back(c);//把這個城市添加到city這個容器中 
            dig[city.size()-1].push_back(d);//在對應位置的數(shù)值后添加 快遞單號
        }
        else  dig[flag].push_back(d);//在對應位置的數(shù)值后添加 快遞單號
    }
    for(int i=0;i<city.size();i++)
    {
        cout<<city[i]<<" "<<dig[i].size()<<endl;
        for(int j=0;j<dig[i].size();j++)
            cout<<dig[i][j]<<endl;
    }
}

例題二：（queue）銀行排隊問題

輸入樣例：

5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V

輸出樣例：

Adel
CLZ
laozhao

題解：

#include <iostream>
#include <queue>
using namespace std;

queue<string> V; // VIP隊列
queue<string> N; // 普通隊列

int main()
{
    int M;
    cin >> M; // 輸入操作的次數(shù)

    while (M--) // 每次進行一個操作
    {
        string op, name, type;
        cin >> op; // 讀入 進入還是出去
        if (op == "IN")
        {
            cin >> name >> type; // 讀取名字 和 類型

            if (type == "V")
                V.push(name); // 如果是VIP類型，加入VIP隊列
            else
                N.push(name); // 否則加入普通隊列
        }
        else
        {
            cin >> type; // 讀取類型

            if (type == "V")
                V.pop(); // 如果是VIP類型，從VIP隊列出隊
            else
                N.pop(); // 否則從普通隊列出隊
        }
    }

    // 打印結果
    while (V.size())
    {
        cout << V.front() << endl; // 輸出VIP隊列中的元素
        V.pop(); // 出隊
    }
    while (N.size())
    {
        cout << N.front() << endl; // 輸出普通隊列中的元素
        N.pop(); // 出隊
    }

    return 0;
}

例題三：(map)重復的單詞

輸入樣例：

5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds

輸出

sdfggfds

題解：

 #include <iostream>
 #include <map>
 using namespace std;

map<string,bool> mp;
int main ()
{

    int n;
    string ans="NO";
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string word;
        cin>>word;
        if(mp.count(word)){
            ans=word;
            break;
        }

        else mp[word]=1;
    }
    cout<<ans<<endl;

}

感謝閱讀?。。?br> 更多算法例題鏈接: 【數(shù)據(jù)結構與算法】遞推法和遞歸法解題（遞歸遞推算法典型例題）文章來源地址http://www.zghlxwxcb.cn/news/detail-850956.html

到了這里，關于【數(shù)據(jù)結構與算法】C++的STL模板（迭代器iterator、容器vector、隊列queue、集合set、映射map）以及算法例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！