STL（一）vector、set/multiset、list

Vector

動(dòng)態(tài)數(shù)據(jù)，可以隨機(jī)訪問。末尾添加和刪除的效率高。元素的順序和推入的順序一致。

基本函數(shù)

  • push_back 數(shù)組最后添加一個(gè)元素。如果是對(duì)象會(huì)執(zhí)行對(duì)象的拷貝構(gòu)造函數(shù)

  • pop_back 去掉數(shù)組最后一個(gè)元素

  • at 根據(jù)下標(biāo)得到數(shù)據(jù)的引用，可以當(dāng)左值。越界會(huì)拋異常

  • [] 可以使用[]操作符，得到結(jié)果可以當(dāng)左值。越界不會(huì)拋異常

  • begin 得到數(shù)組頭的指針iterator

  • end 得到數(shù)組的最后一個(gè)單元+1的指針 iterator

  • front 數(shù)組首元素的引用

  • back 數(shù)組尾元素的引用

  • size 數(shù)組大小

  • earse 刪除參數(shù)為iterator

  • insert 指定位置插入元素

  • empty 判斷空

    ?

遍歷

迭代器方式

void printV(vector<int>& v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << "  ";
    }
    cout << endl;
}

刪除

vector<int>::iterator it = v.begin();
v.erase(v.begin(), v.end() - 1);

案例

void test() {
    vector<Student> v;
    Student stu1(1, "first");
    Student stu2(2, "second");
    Student stu3(3, "third");
    v.push_back(stu1);
    cout << "------------" << endl;
    v.push_back(stu2);
    cout << "------------" << endl;
    vector<Student>::iterator it = v.begin();
    v.insert(it, stu3);
    cout << "------------" << endl;
    printStud(v);
}

運(yùn)行結(jié)果：


insert.png

Set

vector封裝數(shù)組，list封裝了鏈表，map和set封裝了二叉樹等。set關(guān)聯(lián)式容器。set作為一個(gè)容器也是用來存儲(chǔ)同一數(shù)據(jù)類型的數(shù)據(jù)類型，并且能從一個(gè)數(shù)據(jù)集合中取出數(shù)據(jù)，在set中每個(gè)元素的值都唯一，而且系統(tǒng)能根據(jù)元素的值自動(dòng)進(jìn)行排序。應(yīng)該注意的是set中數(shù)元素的值不能直接被改變。C++ STL中標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-Black Tree)。RB樹的統(tǒng)計(jì)性能要好于一般平衡二叉樹，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。set插入是按照一定規(guī)則排序，默認(rèn)是由小到大。

  • 為何map和set的插入刪除效率比用其他序列容器高？

    對(duì)于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng)。說對(duì)了，確實(shí)如此。set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來存儲(chǔ)，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)。

  • 為何每次insert之后，以前保存的iterator不會(huì)失效？

    iterator這里就相當(dāng)于指向元素的指針，元素的內(nèi)存沒有變，指向內(nèi)存的指針當(dāng)然也不會(huì)失效，當(dāng)然這里排除元素被刪除的情況。相對(duì)于vector,每一次刪除和插入，指針都可能失效。所以一定要記住，不要使用過期的iterator

      set<int> s;
  s.insert(3);
  set<int>::iterator it1 = s.begin();
  cout << *it1 << endl;
  s.insert(1);
  //雖然插入1后，1在3的前面。但是it1指向的元素的內(nèi)存。而set內(nèi)所有的元素以節(jié)點(diǎn)
  //方式存儲(chǔ)，節(jié)點(diǎn)結(jié)構(gòu)合鏈表差不多，插入和刪除元素不需要做內(nèi)存的移動(dòng)，只需節(jié)點(diǎn)做
  //變換即可
  //牢記這個(gè)原則：不要使用過期的iterator。
  cout << *it1 << endl;
  s.insert(2);

    這里檔次打印的it1結(jié)果都是3.

  • 當(dāng)數(shù)據(jù)元素增多時(shí)，set的插入和搜索速度變化如何？

    set中查找是使用二分查找，也就是說，如果有16個(gè)元素，最多需要比較4次就能找到結(jié)果，有32個(gè)元素，最多比較5次。

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

  • equal_range()

    返回>=制定元素的第一個(gè)元素指針和>制定元素的第一個(gè)元素的指針。返回的是pair類型，如果哪個(gè)返回失敗，就會(huì)等于end()的值。

    pair<set<int>::iterator, set<int>::iterator> p1=s.equal_range(4);
if (p1.first != s.end()) {
  cout <<">=4 is "<< *p1.first << endl;
}
if (p1.second != s.end()) {
  cout << ">4 is " << *p1.second << endl;
}

  • insert

    • insert(key_value) 將key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>bool標(biāo)志著插入是否成功，而iterator代表插入的元素的定位器。

      pair<set<int>::iterator, bool> p2=s.insert(7);
if (p2.second) {
  cout <<"insert success"<< *p2.first << endl;
}

    • inset(first,second)

      將定位器first到second之間的元素插入到set中，返回值是void

  • lower_bound(key_value)

    是>=值的第一個(gè)元素指針

  • upper_bound(key_value)

    upper_bound是>值的第一個(gè)元素指針

    cout << *s.lower_bound(5) << " " << *s.upper_bound(5) << endl;

測(cè)試案例一

#include "iostream"
using namespace std;
#include "set"
#include "vector"
//迭代器遍歷
void print(set<int>& s) {
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
        cout << *it <<" ";
    }
    cout << endl;
}
int main()
{
    cout << "---------插入----------" << endl;
    set<int> s;
    s.insert(3);
    set<int>::iterator it1 = s.begin();
    cout << *it1 << endl;
    s.insert(1);
    //雖然插入1后，1在3的前面。但是it1指向的元素的內(nèi)存。而set內(nèi)所有的元素以節(jié)點(diǎn)
    //方式存儲(chǔ)，節(jié)點(diǎn)結(jié)構(gòu)合鏈表差不多，插入和刪除元素不需要做內(nèi)存的移動(dòng)，只需節(jié)點(diǎn)做
    //變換即可
    //牢記這個(gè)原則：不要使用過期的iterator。
    cout << *it1 << endl;
    s.insert(2);
    s.insert(5);
    s.insert(6);
    print(s);
    cout << "---------equal_range----------" << endl;
    pair<set<int>::iterator, set<int>::iterator> p1=s.equal_range(4);
    if (p1.first != s.end()) {
        cout <<">=4 is "<< *p1.first << endl;
    }
    if (p1.second != s.end()) {
        cout << ">4 is " << *p1.second << endl;
    }
    set<int>::iterator it = s.begin();
    //不可以隨機(jī)訪問，關(guān)聯(lián)型數(shù)據(jù)結(jié)構(gòu)。紅黑二叉樹
    //it=it+4;
    cout << "---------erase----------" << endl;
    s.erase(it);
    print(s);
    cout << "---------insert及其返回值----------" << endl;
    pair<set<int>::iterator, bool> p2=s.insert(7);
    if (p2.second) {
        cout <<"insert success"<< *p2.first << endl;
    }
    print(s);
    cout << "---------lower_bound、upper_bound----------" << endl;
    //lower_bound是>=值的最小指針  upper_bound是>值的最小指針
    cout << *s.lower_bound(5) << " " << *s.upper_bound(5) << endl;
    return 0;
}

結(jié)果：


set_test1.png

測(cè)試案例二

#include "string"
#include "iostream"
#include "set"
using namespace std;
class Student {
private:
    string name;
    int number;
public:
    Student(int number, string name) {
        cout << "構(gòu)造" << number << endl;
        this->number = number;
        this->name = name;
    }
    Student(const Student& student) {
        this->number = student.getNumber();
        this->name = student.getName();
    }

    void print()const {
        cout << this->number << " "<<this->name << endl;
    }

    string getName()const {
        return this->name;
    }

    int getNumber()const  {
        return this->number;
    }
};
//函數(shù)對(duì)象
struct StuCmp{
    bool operator()(const Student &first,const Student& second) {
        return first.getNumber() > second.getNumber();
    }
};

//遍歷
void print(set<Student, StuCmp>& s) {
    for (set<Student, StuCmp>::iterator it = s.begin(); it != s.end(); it++) {
        it->print();
    }
}
int main()
{
    set<Student, StuCmp> set;
    Student stu1(3, "third");
    Student stu2(1, "first");
    Student stu3(2, "second");
    set.insert(stu1);
    set.insert(stu2);
    set.insert(stu3);
    print(set);
    return 0;
}

結(jié)果：


set_test2.png

multiset

set集合中一個(gè)值只能出現(xiàn)一次，而multiset集合中一個(gè)值可以出現(xiàn)多次。

  • set::insert(key)的返回值是一個(gè)pair<iterator, bool>，其中pair中的bool成員表明了key被插入之前，set中是否已存在相同的key。根據(jù)我在VS2010上的實(shí)驗(yàn)結(jié)果，如果set中已經(jīng)存在相同key的元素，那么插入操作是會(huì)失敗的，新的元素不會(huì)被插進(jìn)去。而multiset::insert的返回值只是一個(gè)iterator，插入操作總是會(huì)成功的。
  • multiset::count(key)的返回值可能大于1。
  • multiset::size()的返回值是多重集合的勢(shì)（cardinality），即multiset中元素的個(gè)數(shù)，而不是值的個(gè)數(shù)。比如，{1, 1, 2}的size是3，而不是2。
  • multiset::erase(key)會(huì)將對(duì)應(yīng)的key全部刪掉，所以對(duì){1, 1, 2}調(diào)用erase(1)之后，它就變成了{(lán)2}。
  • 只要key存在于集合中，set::equal_range(key)的返回值pair<iterator1, iterator2>總是會(huì)有++iterator1 == iterator2。但是對(duì)multiset來說就不一定了。
  • 如果使用自定義類型，則需要在構(gòu)造時(shí)候傳入函數(shù)對(duì)象或者在自定義類型中重載<操作符。注意：函數(shù)要加const限定符。

什么時(shí)候需要用multiset？當(dāng)然是需要用set，但是又允許重復(fù)key存在的時(shí)候了。什么時(shí)候用set？我的答案是：需要隨時(shí)往容器中插入元素，隨時(shí)對(duì)元素進(jìn)行快速查找，又需要按某種順序?qū)υ剡M(jìn)行遍歷的時(shí)候

示例

int main() {
    multiset<Student, StuCmp> s;
    Student stu1(3, "third");
    Student stu2(1, "first");
    Student stu3(2, "second");
    Student stu4(2, "second_2");
    s.insert(stu1);
    s.insert(stu2);
    multiset<Student,StuCmp>::iterator res= s.insert(stu3);
    cout << "--------插入結(jié)果---------" << endl;
    res->print();
    res= s.insert(stu4);
    cout << "--------插入結(jié)果---------" << endl;
    res->print();
    cout << "--------遍歷---------" << endl;
    print(s);
    Student stu5(2, "second_3");
    cout << "--------count方法---------" << endl;
    cout << "count(5)=" << s.count(stu5) << endl;;
    return 0;
}

這里的Student和StuCmp沿用Set中的定義。編譯后發(fā)現(xiàn)出錯(cuò):


multi_set_error.png

發(fā)現(xiàn)是StuCmp的問題，函數(shù)的const修飾符漏了。修改后

struct StuCmp{
    bool operator()(const Student &first,const Student& second) const{
        return first.getNumber() > second.getNumber();
    }
};

運(yùn)行結(jié)果：


multi_set_test3.png

list

list是一個(gè)線性雙向鏈表結(jié)構(gòu)，它的數(shù)據(jù)由若干個(gè)節(jié)點(diǎn)構(gòu)成，每一個(gè)節(jié)點(diǎn)都包括一個(gè)信息塊（即實(shí)際存儲(chǔ)的數(shù)據(jù)）、一個(gè)前驅(qū)指針和一個(gè)后驅(qū)指針。它無需分配指定的內(nèi)存大小且可以任意伸縮，這是因?yàn)樗鎯?chǔ)在非連續(xù)的內(nèi)存空間中，并且由指針將有序的元素鏈接起來。由于其結(jié)構(gòu)的原因，list 隨機(jī)檢索的性能非常的不好，因?yàn)樗幌駐ector 那樣直接找到元素的地址，而是要從頭一個(gè)一個(gè)的順序查找，這樣目標(biāo)元素越靠后，它的檢索時(shí)間就越長(zhǎng)。檢索時(shí)間與目標(biāo)元素的位置成正比。雖然隨機(jī)檢索的速度不夠快，但是它可以迅速地在任何節(jié)點(diǎn)進(jìn)行插入和刪除操作。因?yàn)閘ist 的每個(gè)節(jié)點(diǎn)保存著它在鏈表中的位置，插入或刪除一個(gè)元素僅對(duì)最多三個(gè)元素有所影響，不像vector 會(huì)對(duì)操作點(diǎn)之后的所有元素的存儲(chǔ)地址都有所影響，這一點(diǎn)是vector 不可比擬的。

  • 不使用連續(xù)的內(nèi)存空間這樣可以隨意地進(jìn)行動(dòng)態(tài)操作
  • 可以在內(nèi)部任何位置快速地插入或刪除，當(dāng)然也可以在兩端進(jìn)行push 和pop
  • 不能進(jìn)行內(nèi)部的隨機(jī)訪問，即不支持[ ] 操作符和vector.at()
  • 相對(duì)于verctor 占用更多的內(nèi)存

示例

void print(list<Student> l) {
    for (list<Student>::iterator it = l.begin(); it != l.end(); it++) {
        it->print();
    }
}
struct PrintStu{
    bool operator()(const Student& stu)const  {
        stu.print();
        return true;
    }
};
int main()
{
    list<Student> l;
    Student stu1(1, "first");
    Student stu2(2, "second");
    Student stu3(3, "third");
    Student stu4(4, "fourth");
    l.push_back(stu1);
    l.push_front(stu2);
    l.push_back(stu3);
    l.push_front(stu4);
    print(l);
    cout << "---pop_back、pop_front-------" << endl;
    Student s=l.back();
    s.print();
    l.pop_back();
    s = l.front();
    s.print();
    l.pop_front();
    cout << "----for_each------" << endl;
    for_each(l.begin(), l.end(), PrintStu());
    return 0;
}

結(jié)果：

list.png

這里使用了for_each函數(shù)算法。需要引入#include<algorithm>頭文件

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容