天天看點
傳回

程式設計與算法（三） 第八周 标準模闆庫STL（一）

String 類

string類是一個模闆類：

typedef basic_string< char > string

使用string類要包含頭檔案< string>

string 對象的初始化：

  • string s1(“hello”);
  • string month=”match”;
  • string s2(8,’x’);
  • 等。。。。 
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s1("hello");
    cout<<s1<<endl;
    string s2(, 'x');
    cout<<s2<<endl;
    string match = "matrch";
    cout<<match<<endl;
    string s;
    s = 'n';
    cout<<s<<endl;
    return ;
}
           
hello
xxxxxxxx
matrch
n

string支援getline函數

  • string s;
  • getline(cin,s)

string的指派和連接配接

  • 用=指派
  • string s1(“cat”), s2
  • s2=s1
  • 用assign成員函數指派
  • string s1(“cat”), s2
  • s2.assign(s1);
  • 用assign成員函數部分複制
  • string s1(“catpig”), s3;
  • s3.assign(s1,1,3); //下标為1到3這3個元素指派給s3
  • 單個字元指派
  • 單個字元複制：s2[5]=s1[3]=’a’;
  • 逐個通路string中的字元string s1(“hello”) s1.at(i)
  • 用+運算符連接配接字元串
  • string s1(“good”), s2(“morning!”);
  • s1+=s2
  • 用成員函數append連接配接字元串
  • string s1(“good”), s2(“morning”)
  • s1.append(s2)
  • s1.append(s1, 3, s1.size()) //下标為3的位置開始，指派s1.size()個字元，如果沒用那麼多字元，就指派到最後一個字元
  • 用<,>,==比較字典序
  • 用成員函數compare比較string的大小
  • s1.compare(1,2,s3,0,3)是說，用s1的下标為1到2（包括2）的字元和s3的0到3的字元比較

子串

string s1(“hello world”), s2;

s2 = s1.substr(4,5); //從下标為4的位置，向後數5個字元進行指派

交換兩個string: s1.swap(s2)

尋找string中的字元

  • 成員函數 find()和rfind()
    • string s1(“hello world”)
    • s1.find(“lo”)
    • 在s1中從前向後查找，”lo”第一次出現的地方，如果找到，傳回”lo”開始的下标（“l”的下标） 如果找不到，傳回string::npos(string中定義的靜态常量)
    • s1.find(“lo”,1)//從下标為1的地方開始找
  • find_first_of() 和find_last_of()（這個是最後一次出現的地方）
    • string s1(“hello world”);
    • s1.find_first_of(“abcd”);
    • 在s1中從前向後找”abcd”中任何一個字元第一次出現的地方，如果找到，傳回找到字母的位置，找不到則傳回string::npos。
  • 成員函數find_first_not_of() 和find_last_not_of()
    • string s1(“hello world”)
    • s1.find_first_not_of(“abcd”);
    • 在s1中從前向後查找不在，“abcd”中的字母第一次出現的地方，如果找到，傳回找到字母的位置，如果找不到，傳回string::npos。
  • 删除string中的字元
    • 成員函數erase()
    • string s1(“hello world”)
    • s1.erase(5) //删除5以及之後的字元
  • 替換string中的字串
    • 成員函數replace()
    • string s1(“hello world”)
    • s1.replace(2,3,”haha”) // 将s1中下标2開始的3個字元換成”haha”
    • s1.replace(2,3,”haha”,1,2) // 将s1中下标2開始的3個字元換成“haha”中下标1開始的2個字元
  • 在string中插入字元
    • 成員函數insert()
    • string s1(“hello world”)
    • string s2(“show insert”)
    • s1.insert(5, s2)
    • s1.insert(2, s2, 5, 3)
  • 轉換成C語言式char *字元串
    • 成員函數c_str()
    • string s1(“hello world”)
    • printf(“%s\n”,s1.c_str()) // s1.c_str() 傳回傳統的const char*類型字元串，該字元串以 ‘\0’ 結尾
  • 轉換成c語言式char*字元串
    • 成員函數data()
    • string s1(“hello world”)
    • const char *p1=s1.data()
    • for(int i=0;i

字元串流處理

除了标準流和檔案流輸入輸出之外，還可以從string進行輸入輸出

類似istream和ostream進行标準流輸入輸出，我們用istringstream和ostringstream進行字元串上的輸入輸出，也稱為記憶體輸入輸出:include< sstream> 

#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main(){
    string s1("hello world");
    string ss1, ss2;
    istringstream inputstring(s1);
    inputstring>>ss1>>ss2;
    cout<<ss1<<" "<<ss2;
    return ;
}
           
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main(){
    string s1("hello world");
    string ss1, ss2;
    istringstream inputstring(s1);
    inputstring>>ss1>>ss2;
    ostringstream out;
    out<<"the "<<<<" ok"<<endl;
    cout<<out.str();
    cout<<"there";
    return ;
}
           
the  ok
there

标準模闆庫（STL）概述

泛型程式設計

c++語言的核心優勢之一就是便于軟體的重用

c++中有兩個方面展現重用，

  • 面向對象的思想：繼承和多态，标準類庫
  • 泛型程式設計的思想：模闆機制以及标準模闆庫STL

STL中的基本的概念

  • 容器：可容納各種資料類型的通用資料結構，是類模闆
  • 疊代器：可用于一次存取容器中元素，類似于指針
  • 算法：用來操作容器中哦的元素的函數模闆
  • sort() 來對一個vector中的資料進行排序
  • find()來搜尋一個list中的對象
  • 算法本身與他們操作的資料的類型無關，是以他們可以在從簡單數組到高度複雜容器的任何資料結構上使用

容器概述：可以用于存放各種類型的資料（基本資料類型的變量，對象等）的資料結構，都是類模闆，分為三種：

  • 順序容器：vector, deque, list
  • 關聯容器：set, multiset, map, multimap
  • 容器擴充卡：stack, queue, priority_queue

順序容器簡介

vector：動态數組，元素在記憶體連續存放。

deque:頭檔案< deuqe>雙向隊列。元素在記憶體連續存放。随機存取任何元素都能在常數時間内完成（但次于vector）。在兩端增删元素具有較佳的性能（大部分情況下是常數時間）。

list:頭檔案< list>雙向連結清單。元素在記憶體不連續存放。在任何位置增删元素都能在常數時間内完成。不支援随機存取。

關聯容器簡介

  • 元素是排序的
  • 插入任何元素，都按相應的排序規則來确定其位置
  • 在查找時具有
  • 通常以平衡二叉樹方式實作，插入和檢索時間都是O(log(N))
  • set/multiset 頭檔案< set> set即集合。set中不允許相同元素，multiset中允許存在相同元素。
  • map/multimap 頭檔案< map>
  • map和set的不同在于map中存放的元素有且僅有兩個成員變量，一個名為first，另一個名為second，map根據first值對元素進行從小到大排序，并可快速地根據first來檢索元素。map同multimap的不同在于是否允許相同first值的元素。

容器擴充卡簡介

  • stack:頭檔案：< stack> 棧。是項的有限序列，并滿足序列中被删除、檢索和修改的項隻能是最近插入序列的項(棧頂的項)。後進先出
  • queue：頭檔案< queue>隊列。插入隻可以在尾部進行，删除、檢索和修改隻允許從頭部進行。先進先出。
  • priority_queue:頭檔案< queue> 優先級隊列。最高優先級元素總是第一個出列

順序容器和關聯容器中都有哪些成員函數

  • begin: 傳回指向容器中第一個元素的疊代器
  • end: 傳回指向容器中最後一個元素後面位置的疊代器
  • rbegin:傳回指向容器中最後一個元素的疊代器
  • rend: 傳回指向容器中第一個元素前面的位置的疊代器
  • erase: 從容器中删除一個或幾個元素
  • clear: 從容器中删除所有元素

順序容器的常用的成員函數

  • front: 傳回容器中第一個元素的引用
  • back: 傳回容器中最後一個元素的引用
  • push_back: 在容器末尾增加新元素
  • pop_back: 删除容器末尾的元素
  • erase:删除疊代器指向的元素（可能會使該疊代器失效），或删除一個區間，傳回被删除元素後面的那個元素的疊代器

标準模闆庫STL概述（二）

疊代器

  • 用于指向順序容器和關聯容器中的元素
  • 疊代器用法和指針類似
  • 有const和非const兩種
  • 通過疊代器可以讀取它指向的元素
  • 通過非const疊代器還能修改其指向的元素

定義疊代器的方法

  • 容器類名：：iterator 變量名;
  • 容器類名：：const_iterator 變量名;
  • 通路一個疊代器指向的元素：*疊代器變量名

疊代器上可以執行++操作，以使其指向容器中的下一個元素。如果到達了最後一個元素後面，就會出錯。 

#include <vector>
#include <iostream>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back();
    v.push_back();
    v.push_back();
    v.push_back();
    vector<int>::const_iterator i;
    for (i = v.begin(); i != v.end(); ++i) {
        cout<<*i<<",";
    }
    cout<<endl;
    vector<int>::reverse_iterator r;//反向疊代器，這裡r++會指向容器中的前一個元素
    for (r = v.rbegin(); r!=v.rend(); ++r) {
        cout<<*r<<",";
    }
    vector<int>::iterator j;  //非常量疊代器
    for (j = v.begin(); j != v.end() ; ++j) {
        *j=;
    }
    cout<<endl;
    for(auto x:v){
        cout<<x<<",";
    }
}
           
1,2,3,4,
4,3,2,1,
100,100,100,100,

雙向疊代器

  • ++p, p++， –p, p–
  • *p //傳回那個值（的引用）
  • p=p1
  • p==p1, p!=p1

随機通路疊代器

  • 雙向疊代器的所有操作
  • p+=i
  • p-=i
  • p+i, p-i, p[i],
  • p

容器和容器上疊代器的種類

  • vector 随機通路
  • deque 随機通路
  • list 雙向
  • set/multiset 雙向
  • map/multimap 雙向
  • stack 不支援疊代器
  • queue 不支援疊代器
  • priority_queue 不支援疊代器

有的容器，例如sort和binary_search需要通過随機通路疊代器來通路容器中的元素，那麼list以及關聯容器就不支援改算法

vector 的疊代器是随機疊代器

list是雙向疊代器，用法如下： 

list<int> vv;
    vv.push_back();
    vv.push_back();
    vv.push_back();
    list<int> ::const_iterator ii;
    //這裡不能用ii<vv.end()，不能用vv[i]
    for (ii=vv.begin();ii!=vv.end();++ii){
        cout<<*ii<<",";
    }

算法簡介

  • 算法就是一個個函數模闆，大多是在< algorithm>中定義
  • STL中提供能在各種容器中通用的算法，比如查找、排序等
  • 算法通過疊代器來操縱容器中的元素，許多算法可以對容器中的一個局部區間進行操作，是以需要兩個參數，一個是起始元素的疊代器，一個是終止元素的後面一個元素的疊代器
  • 有的算法傳回一個疊代器。比如find()算法，在容器中查找一個元素，并傳回一個指向該元素的疊代器
  • 算法可以處理容器，也可以處理普通數組

算法示例 find()

  • template

STL中“大”，“小”的概念

  • 關聯容器内部的元素是從小到大排序的
  • 有些算法要求其操作的區間是從小到大排序的，稱為“有序區間算法”。例如：binary_search
  • 有些算法會對區間進行從小到大排序，成為排序算法。例如：sort
  • 還有一些其他算法會用到“大”，“小”的概念
  • 使用STL時，在預設的情況下，以下三個說法等價：x比y小，x 
#include <iostream>
#include <algorithm>
using namespace std;
class A{
    int v;
public:
    A(int n):v(n){}
    bool operator < (const A &a2)const{
        cout<<v<<"<"<<a2.v<<"?"<<endl;
        return false;
    }
    bool operator == (const A &a2) const{
        cout<<v<<"=="<<a2.v<<"?"<<endl;
        return v==a2.v;
    }
};
int main()
{
    A a[]={A(), A(), A(), A(), A()};
    cout<<binary_search(a, a+, A());//折半查找中，隻是判斷了是否小于。。傳回1是找到了
    return ;
}
           
3<9?
2<9?
1<9?
9<1?
1

vector 和deque

vector 

#include <iostream>
#include <vector>
using namespace std;
template <class T>
void PrintVector(T s, T e){
    for(;s!=e;++s)
        cout<<*s<<" ";
    cout<<endl;
}
int main(){
    int a[]={,,,,};
    vector<int> v(a, a+);
    cout<<"1)"<<v.end()-v.begin()<<endl;
    cout<<"2)";
    PrintVector(v.begin(), v.end());
    v.insert(v.begin()+, );//插入。。第一個參數是位置，第二個位置是元素
    cout<<"3)";
    PrintVector(v.begin(), v.end());
    v.erase(v.begin()+);//删除
    cout<<"4)";
    PrintVector(v.begin(), v.end());
    vector<int> v2(, );//4個元素，每個元素都是100
    v2.insert(v2.begin(),v.begin()+, v.begin()+);//在v2裡面插入某個區間
    cout<<"5) v2:";
    PrintVector(v2.begin(), v2.end());
    v.erase(v.begin()+, v.begin()+);
    cout<<"6) ";
    PrintVector(v.begin(), v.end());
    return ;
}
           
1)5
2)1 2 3 4 5 
3)1 2 13 3 4 5 
4)1 2 3 4 5 
5) v2:2 3 100 100 100 100 
6) 1 4 5

vector 二維數組 

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector< vector<int> > v();
    for (int i = ; i < v.size(); ++i) {
        for (int j = ; j < ; ++j) {
            v[i].push_back(j);
        }
    }
    for (int i = ; i < v.size(); ++i) {
        for (int j = ; j < ; ++j) {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
    return ;
}
           
0 1 2 3 
0 1 2 3 
0 1 2 3

deque:适合vector的操作都适用于deque。

deque還要push_front(将元素插入到前面）和pop_front(删除最前面的元素）操作，複雜度是O(1)

雙向連結清單：list

  • 在任何位置插入删除都是常數時間，不支援随機存取
  • 除了具有所有容器都有的成員函數以外，還支援8個成員函數：
  • push_front: 在前面插入
  • pop_front: 删除前面的元素
  • sort：排序（list不支援STL的算法sort)
  • remove: 删除和指定值相同的所有元素
  • unique: 删除所有和前一個元素相同的元素（要做到元素不重複，則unique之前還需要sort）
  • merge：合并兩個連結清單，并清空被合并的那個
  • reverse：颠倒連結清單
  • splice: 在指定位置前面插入另一個連結清單中的一個或多個元素，并在另一連結清單中删除被插入的元素 
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
class A{
private:
    int n;
public:
    A(int _n):n(_n){}
    friend bool operator<(const A &a1, const A &a2);
    friend bool operator==(const A &a1, const A &a2);
    friend ostream &operator<<(ostream &o, const A &a);
};
bool operator<(const A &a1, const A &a2) {
    return a1.n<a2.n;
}
bool operator==(const A &a1, const A &a2) {
    return a1.n==a2.n;
}
ostream& operator<<(ostream &o, const A &a) {
    o<<a.n;
    return o;
}
template <class T>
void PrintList(const list<T> & lst){
    //不推薦的寫法，用兩個疊代器更好
    typename list<T>::const_iterator i; //typename用來說明list<T>::const_iterator是個類型
    i = lst.begin();
    for (i = lst.begin(); i!=lst.end(); ++i) {
        cout<<*i<<",";
    }
}
int main()
{
    list<A> lst1, lst2;
    lst1.push_back();lst1.push_back();
    lst1.push_back();lst1.push_back();
    lst1.push_back();
    lst2.push_back();
    lst2.push_front();
    lst2.push_back();
    lst2.push_front();
    lst2.push_back();
    lst2.push_front();
    lst2.push_back();
    cout<<"1)";
    PrintList(lst1);cout<<endl;
    cout<<"2)";
    PrintList(lst2);cout<<endl;
    lst2.sort();
    cout<<"3)";
    PrintList(lst2);
    cout<<endl;
    lst2.pop_front();//删掉頭部元素
    cout<<"4)";
    PrintList(lst2);
    cout<<endl;
    lst1.remove(); //删除和A(2)相等的元素
    cout<<"5)";
    PrintList(lst1);
    cout<<endl;
    lst2.unique();
    cout<<"6)";
    PrintList(lst2);
    cout<<endl;
    lst1.merge(lst2); //合并lst2到lst1并清空lst2
    cout<<"7)";
    PrintList(lst1);
    cout<<endl;
    cout<<"8)";
    PrintList(lst2);
    cout<<endl;
    lst1.reverse();
    cout<<"9)";
    PrintList(lst1);
    cout<<endl;
    lst2.push_back();
    lst2.push_back();
    lst2.push_back();
    lst2.push_back();
    list<A>::iterator p1, p2, p3;
    p1 = find(lst1.begin(), lst1.end(), );
    p2 = find(lst2.begin(), lst2.end(), );
    p3 = find(lst2.begin(), lst2.end(), );
    lst1.splice(p1, lst2, p2, p3);//将lst2[p2,p3)插入到p1之前， 并從lst2中删除[p2, p3)
    cout<<"10)";
    PrintList(lst1);
    cout<<endl;
    cout<<"11)";
    PrintList(lst2);
    cout<<endl;
    return ;
}
           
1)1,3,2,4,2,
2)40,30,20,10,30,30,40,
3)10,20,30,30,30,40,40,
4)20,30,30,30,40,40,
5)1,3,4,
6)20,30,40,
7)1,3,4,20,30,40,
8)
9)40,30,20,4,3,1,
10)40,30,20,4,200,300,3,1,
11)100,400,

函數對象：若一個類重載了運算符“（）”，則該類的對象就成為函數對象 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

int SumSquares(int total, int value)
{return total+value*value;}

template <class T>
void PrintInterval(T first, T last)
{
    for(;first!=last;++first)
    {
        cout<<*first<<" ";
    }
    cout<<endl;
}
template <class T>
class SumPowers
{
private:
    int power;
public:
    SumPowers(int p):power(p){}
    const T operator()(const T&total, const T&value){
        T v=value;
        for(int i=;i<power-;i++) v=v*value;
        return total+v;
    }
};

int main()
{
    const int SIZE = ;
    int a1[]={,,,,,,,,,};
    vector<int> v(a1, a1+SIZE);
    cout<<"1)";
    PrintInterval(v.begin(), v.end());
    int result = accumulate(v.begin(), v.end(), , SumSquares);//SumSquares是個函數
    /*
     這裡執行個體化了：
     int accumulate(vector<int>::iterator first, vector<int>::iterator last, int init, int(*op)(int, int))
     {
        for(;first!=last;++first)
            init=op(init, *first);
        return init;
     }
     */
    cout<<"2)平方和"<<result<<endl;
    //SumPowers是個類模闆，SumPowers<int>模闆類，SumPowers<int>(3)是個對象，這個對象重載了“()”
    result = accumulate(v.begin(), v.end(), , SumPowers<int>());
    /*
     int accumulate(vector<int>::iterator first, vector<int>::iterator last, int init, SumPowers<int> op)
     {
        for(;first!=last;++first)
            init=op(init, *first);
        return init;
     }
     */
    cout<<"3)立方和"<<result<<endl;
    result=accumulate(v.begin(), v.end(), , SumPowers<int>());
    cout<<"4)4次方和"<<result<<endl;
    return ;
}
           
1)1 2 3 4 5 6 7 8 9 10 
2)平方和385
3)立方和3025
4)4次方和25333
           
//在c++源碼中如下：

  template<typename _InputIterator, typename _Tp>
    inline _Tp
    accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_requires_valid_range(__first, __last);

      for (; __first != __last; ++__first)
    __init = __init + *__first;
      return __init;
    }

  template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
    inline _Tp
    accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
           _BinaryOperation __binary_op)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_requires_valid_range(__first, __last);

      for (; __first != __last; ++__first)
    __init = __binary_op(__init, *__first);
      return __init;
    }

STL中的函數對象類模闆:頭檔案：< functional>

greater 函數對象類模闆 

//在c++中源碼如下：

  template<typename _Tp>
    struct greater : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x > __y; }
    };

greater的應用

list有兩個sort成員函數

  • void sort(); 将list中的元素按”<”規定的比較方法升序排列
  • template< class Compare>
  • void sort(Compare op); 将list中的元素按op規定的比較方法升序排列。即要比較x, y大小時，看op(x, y)的傳回值，為true則認為x小于y 
#include <list>
#include <iostream>
using namespace std;
class MyLess{
public:
    bool operator()(const int &c1, const int &c2)
    {
        //比較各位數
        return (c1%)<(c2%);
    }
};
template <class T>
void Print(T first, T last){
    for(;first!=last;++first) cout<<*first<<",";
}
int main()
{
    const int SIZE=;
    int a[SIZE]={,,,,};
    list<int> lst(a, a+SIZE);
    lst.sort(MyLess());
    Print(lst.begin(), lst.end());
    cout<<endl;
    lst.sort(greater<int>());//greater<int>()是個對象
    Print(lst.begin(), lst.end());
    cout<<endl;
    return ;
}
           
21,2,3,14,5,
21,14,5,3,2,

在STL中使用自定義的“大”，“小”關系

關聯容器和STL中許多算法，都是可以用函數或函數對象自定義比較器的。在自定義了比較器op的情況下，以下三個說法是等價的：1.x小于y；2.op(x,y) 傳回true；3.y大于x 

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

class MyLess{
public:
    bool operator()(int a1, int a2){
        if((a1%)<(a2%)) return true;
        else return false;
    }
};

bool MyCompare(int a1, int a2){
    if((a1%)<(a2%)) return false;
    else return true;
}

template <class T, class pred>
T MyMax(T first, T last, pred op){
    T temp = first;
    for(;first!=last;++first){
        if(op(*temp, *first)) 如果*temp小于*first
            temp = first;
    }
    return temp;
};

int main()
{
    int a[]={, ,, , };
    cout<<*MyMax(a, a+, MyLess())<<endl;
    cout<<*MyMax(a, a+, MyCompare)<<endl;
    return ;
}
           
19
12
c++和java基礎 mooc
上一篇: HTML 5.1和主要元素
下一篇: 中國大學MOOC程式設計與算法（三）：C++ 面向對象程式設計 第四周 運算符重載 筆記 之

繼續閱讀