C++11 新特性学习（3） ---- 顺序性容器

2022-11-05 本文已影响0人特立独行的佩奇

通用容器的分类

STL 对定义的容器分为三类：顺序性容器，关联性容器和容器适配器

顺序性容器
是一种各个元素之间有顺序关系的线性表，是一种线性结构的可续群集，顺序容器的每个元素都有固定的位置，除非用删除或者插入的方法改变这个位置，这个位置和元素本身没有关系，顺序容器不会根据元素的特点进行排序而是直接保存了元素操作的逻辑顺序
关联性容器
关联性容器是非线性的树结构，更准确的说的是二叉树结构，各个元素没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入时的逻辑顺序，但是关联容器提供了另一种根据元素特点排序的功能，这个迭代器可以根据元素的特点顺序的获取元素
关联容器的另一个特点就是以键值的方法保存数据，就是它可以将关键字和值关联起来保存，顺序容器只能保存一种（键值或者数据）
容器适配器
容器适配器比较抽象，是一种让已经存在的容器类型采用另一种不同的抽象类型的工作方式实现的一种机制，可以理解为容器的容器，或者说容器的数据结构，是容器的一种模板

标准容器类	特点
顺序容器类	NA
vector	可变大小数组，支持快速随机访问，在尾部之外的位置插入或者删除元素可能会很慢
deque	双端队列，支持快速随机访问，在头尾位置插入删除元素速度很快
list	双向链表，只支持头尾的顺序访问，在链表的任何位置插入删除操作速度都很快
forward_list	单向链表，支持单向顺序访问，在链表的任何位置插入/删除速度都很快
array	指定大小的数据，支持快速随机访问，不能动态添加或者删除元素
string	和vector 类似的容器，专门用于保存字符，随机访问快，在尾部插入删除速度快
关联性容器
set ，unordered_set	快速查找，内部有序，unordered_set内部无序，不允许重复值
multi_set，unordered_multiset	快速查找，内部有序，unordered_set内部无序，允许有重复值
map，unordered_map	一对多映射，基于关键字查找，unordered_map 内部无序，不允许重复值
mulit_map，unordered_multimap	一对多映射，基于关键字查找，unordered_multimap 内部无序，允许重复值
容器适配器
stack	后进先出的栈的数据结构，只能访问头尾元素
queue	先进先出的队列数据结构，只能访问头尾元素
priority_queue	最高优先级的总是可以第一个出队列

string和vector将元素保存在连续的内存空间中，由于元素是连续存储的，由元素的下标来计算其他地址是非常快速的。但是，在这两种容器的中间位置添加或者删除元素就会非常耗时，在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储，而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间

vector 容器

元素	说明
构造方法	数组构造，拷贝构造，复制构造
访问方法	at，operator[ ]，front()，back()
修改方法	push_back()，pop_back()，emplace_back()，emplace()，erase()，insert()，clear()
属性	size()，capacity()，max_size()

vectorDemo::vectorDemo() {
    auto dumpVector = [](const auto& p)->void {
        cout << "vector size: " << p.size() << " capacity: " << p.capacity() << " maxsize: " << p.max_size() << endl;
        for (auto temp : p) {
            cout <<" " << temp;
        }
        cout << endl;
    };

    // construct vector
    {
        vector<uint32_t> va(10);
        vector<uint32_t> vb(10, 1);
        vector<uint32_t> vc(vb);
        vector<uint32_t> vd(vc.cbegin(), vc.cbegin() + 3);

        uint32_t temp[] = { 1,2,3,4,5,6 };
        vector<uint32_t> ve(temp, temp + 3);

        vector<uint32_t> vf = {100,200,300,400};
        vector<uint32_t> vh({ 100,200,300,400});
        vector<uint32_t> vi;
        vi.assign(10,100);
    }

    //get element 
    {
        vector<uint32_t> va({ 100,200,300,400 });
        // get element
        cout << " first element: " << va.front() << " at 0:" << va.at(0) << endl;
        cout << " last element: " << va.back() << endl;
        cout << " first element: " << va[2] << endl;
    }


    //modify element  push_back pop_back erase insert clear emplace emplace_back
    {
        vector<uint32_t> va({ 100,200,300,400 });
        va.push_back(1234);
        va.push_back(5678);
        va.emplace(va.cbegin() + 3, 521);
        va.emplace_back(1234);
        //dumpVector(va);
        
        va.clear();
        va.insert(va.begin(), 1000); //在 begin 位置插入一个 1000 的元素
        va.insert(va.begin() + 1, 5, 1000); //在 begin 位置插入5 个 值为1000 的元素

        uint32_t atemp[] = {12, 34, 56, 78};
        va.insert(va.begin() + 1, atemp + 1, atemp + 3); //在 begin + 1 位置 插入 index + 3 到 index + 6 的元素  temp 是数组名称
        va.emplace_back(999);
        va.pop_back(); // remove end element
        va.erase(va.cbegin());
        //dumpVector(va);
    }
}

deque 容器

元素	说明
构造方法	数组构造，拷贝构造，复制构造
访问方法	at，operator[ ]，front()，back()
修改方法	push_back()，pop_back()，push_front()，pop_front()，emplace()，emplace_back()，emplace_front()，insert()，erase()，clear()
属性	size()，empty()，max_size()

stddequeDemo::stddequeDemo() {

    auto dumpdeq = [](deque<string>& p) {
        cout << "deque size: " << p.size() << " empty: " << p.empty() << " max_size: " << p.max_size() << endl;
        for (auto temp : p) {
            cout << " " << temp;
        }
        cout << endl;
    };

    //cosntructer deque
    {
        deque<string> dqa = { "stringA", "stringB", "stringC", "stringD" };
        deque<string> dqb(dqa);
        deque<string> dqc = dqb;
        deque<string> dqd(5, "dequestring");
        deque<string> dqe({"stringA", "stringB", "stringC", "stringD" });
        //dumpdeq(dqa);
    }

    //modifier push_front push_back
    {
        deque<string> dqa = { "stringA", "stringB", "stringC", "stringD" };
        dqa.push_front("frontA");
        dqa.push_front("frontB");
        dqa.push_front("frontC");
        dqa.push_front("frontD");
        dqa.push_back("backA");
        dqa.push_back("backB");
        dqa.push_back("backC");
        dqa.push_back("backD");

        dqa.pop_front();
        dqa.pop_back();
        dqa.clear();
    }

    {
        deque<string> dqa = { "stringA", "stringB", "stringC", "stringD" };
        dqa.emplace(dqa.cbegin() + 1,"emplace");
        dqa.emplace_back("emplace_back");
        dumpdeq(dqa);
    }

    //get
    {
        deque<string> dqa = { "dqstringA", "dqstringB", "dqstringC", "dqstringD" };
        cout << "dqa_front: " << dqa.front();
        cout << " dqa_back: " << dqa.back();
        cout << " dqa_at 3: " << dqa.at(3);
        cout << " dqa_[0]: " << dqa[0];
    }

}

array 容器

元素	说明
构造方法	数组构造，拷贝构造，复制构造
访问方法	at，operator[ ]，front()，back()，data()
修改方法	fill
属性	size()，empty()，max_size()

stdArrayDemo::stdArrayDemo() {

    auto dumpArray = [](array<uint32_t, 10>& a) {
        cout << "array size: " << a.size() << " empty: " << a.empty() << " max_size: " << a.max_size() << endl;
        auto iter = a.begin();
        while (iter != a.end()) {
            cout << " " << *iter;
            iter++;
        }
    };

    //array construct
    {
        array<uint32_t, 10> ara;
        array<uint32_t, 10> arb = {1,2,3,4,5};
        array<uint32_t, 10> arc(arb);
    }

    //modifier
    {
        array<uint32_t, 10> ara;
        ara.fill(100);

        cout << "dump all array element: " << endl;
        for (uint8_t i = 0; i < ara.size(); i++) {
            cout << " " << ara[i];
        }
        cout << endl;
        //dumpArray(ara);
    }

    {
        array<uint32_t, 10> ara = {11, 22, 33, 44, 55, 66, 77};
        dumpArray(ara);
        cout << " array at 1: " << ara.at(1) << " front: " << ara.front() << " back: " << ara.back() << endl;
    }

}

list 容器

元素	说明
构造方法	数组构造，拷贝构造，复制构造
访问方法	front()，back()
修改方法	insert，erase，push_back()，pop_back()，push_front()，pop_front()，emplace()，emplace_back()，emplace_front()
属性	size()，empty()，max_size()

stdListDemo::stdListDemo() {

    auto dumplist = [](auto& p) {
        cout << "dump all element " << endl;
        for (auto temp : p) {
            cout << " " << temp;
        }
        cout << endl;
    };


    //construct
    {
        list<string> la;
        list<string> lb({"A", "B", "C", "D"});

        list<string> lc(lb);
        list<string> ld = {"A", "B", "C", "D"};
        list<string> le(6); // size as 6
    }

    //modifier insert push_front push_back pop_front pop_back emplace_back erase
    {
        list<string> la({ "A", "B", "C", "D" });
        
        la.push_front("push_front_A");
        la.push_front("push_front_B");
        la.push_back("push_back_A");
        la.push_back("push_back_B");
        la.emplace_back("emplace_element");
        dumplist(la);

        la.pop_front();
        la.pop_back();
        dumplist(la);


        //auto iter = next(la.begin(), 3);  //using next method
        list<string>::iterator iter = next(la.begin(), 3);
        la.insert(iter,"insertvalue");

        la.erase(next(la.begin(), 1));
        dumplist(la);
    }

}