Cpp-03-STL

作者： 分类：笔记 字数：6109

容器

  • 顺序容器：存储顺序由插入操作决定，支持随机或顺序访问。

    • vector：动态数组，高效的尾部插入删除，随机访问，内存连续分配。
    • deque：双端队列，高效前后向插入删除，随机访问，内存分段存储。
    • list：双向链表，高效前后向插入删除，不提供随机访问，节点包含前后向指针。
    • forward_list：单向链表，只支持前向遍历（从前往后遍历），高效前向插入删除，内存开销小。
    • array：固定数组，随机访问，内存连续。

  • 关联容器：根据键值对或单一键进行排序，允许快速查找、插入和删除。

    • set：单一键，不允许重复，默认升序排序。
    • multiset：存储单一键，允许重复键，默认升序，（内部使用平衡二叉搜索树-红黑树实现）查找、插入和删除都是O(log n)。适用于需要频繁统计或多值集合并保持有序，如频率统计或优先队列变种。
    • map：键值对，不允许重复，默认按键的升序排列。
    • multimap：键值对，允许重复键，（内部使用平衡二叉搜索树实现）查找、插入和删除都是O(log n)。适用于将一个键映射多个值，可以模拟关系数据库多对一或多对多的关系，或者构建索引。
    • unordered_set：单一键，不允许重复，内部无序，基于哈希表实现，查找、插入和删除都是O（1）。
    • unordered_multiset：存储单一键，允许重复键，基于哈希表实现，查找、插入和删除都是O（1）。使用与频率统计但是不要求有序。
    • unordered_map：基于哈希表的map。
    • unordered_multimap：键值对，允许重复键，基于哈希表实现，查找、插入和删除都是O（1）。

  • 容器适配器：基于其他容器构建的特殊容器。

    • stack：栈，后进先出（LIFO），仅支持top、push、pop、empty操作底层基于deque，也可以指定vector或list，适用于表达式求值、回溯算法等。
    • queue：队列，先进先出（FIFO），支持front、back、push、pop、empty操作，默认使用deque，也可以指定list，适用于任务调度，广度优先搜索。
    • priority_queue：优先级队列，最大堆或最小堆，默认最大堆，支持top、push、pop、empty操作，默认使用vector，也可以指定deque，适用于优先级管理，如事件调度、Dijkstra算法等。
//map
void mapBase(){
    map<string, size_t> word_count;
    string word;
    while(cin >> word){
        //下标访问会直接添加元素
        //不添加可以使用find方法
        word_count[word]++;
    }
    for(const auto &val : word_count){
        cout << "word is " << val.first << "count are " << val.second << endl;
    }
    //等价于
    for_each(word_count.begin(), word_count.end(), [](pair<string, size_t> a){
        cout << a.first << "  " << a.second << endl;
    })
    //使用pair插入
    //添加单一元素的insert和emplace返回一个pair<key,bool>
    auto res = word_count.insert(make_pair("ady", 20));
    //res.second判断是否成功
    //使用{}
    word_count.insert({"io", 2020});
}
//不在set中出现的次数
void setBase(){
    map<string, size_t> word_count;
    set<string> excludes = {"zack", "joyce", "mongo"};
    string word;
    while(cin >> word){
        if(excludes.find(word) == excludes.end()){
            word_count[word]++;
        }
    }
    for(const auto &val : word_count){
        cout << "word is " << val.first << "count are " << val.second << endl;
    }
}
//multiset与multimap
void multiBase(){
    //multiset
    vector<int> nums;
    for(int i = 0; i < 10; i++){
        nums.push_back(i);
        //重复插入，为了测试multi容器
        nums.push_back(i);
    }
    set<int> numSet(nums.begin(), nums.end());
    multiset<int> numsMulti(nums.begin(), nums.end());
    for_each(numSet.begin(), numSet.end(), [](const int &i){
        cout << i << "    ";
    });
    cout << endl;
    for_each(numMulti.begin(), numMulti.end(), [](const int &i){
        cout << i << "  ";
    });
    cout << endl;
    //multimap
    multimap<string, string> authors;
    authors.insert(make_pair("zack", "i see i know"));
    authors.insert(make_pair("zack", "who am i"));
    for(auto low = authors.low_bound("zack"); low != authors.upper_bound("zack"); low++){
        cout << low->first << "  " << low->second << endl;
    }
    //等价于
    auto equal_range = authors.equal_range("zack");
    for(; equal_range.first != equal_range.second; equal_range.first++){
        cout << equal_range.first->first << "  " << equal_range.first->second << endl;
    }
}
//key为自定义的复合类型，需要为该类重载比较运算符或者定义比较函数
class BookData {
public:
    BookData() = default;
    BookData(string nm, string au, string is) : name(nm), author(au), isbn(is) {}
    string name;
    string author;
    string isbn;
};
// 定义比较函数对象
struct CompareIsbn {
    bool operator()(const BookData &b1, const BookData &b2) const {
        return b1.isbn < b2.isbn;
    }
};
void funCompare(){
    //使用函数对象作为比较器
    multiset<BookData, CompareIsbn> bookmap;
    //示例数据
    bookmap.insert(BookData("C++ Primer", "Stanley B. Lippman", "0321714113"));
    bookmap.insert(BookData("Effective Modern C++", "Scott Meyers", "1491903996"));
    // 打印所有书籍
    for (const auto &book : bookmap) {
        cout << "Name: " << book.name << ", Author: " << book.author << ", ISBN: " << book.isbn << endl;
    }
    //等价于================使用lambda=================
    auto compareLambda = [](const BookData &b1, const BookData &b2){
        return b1.isBn < b2.isBn;
    }
    multiset<BookData, decltype(compareLambda)> booklambda(compareLambda);
    for (const auto &book : booklambda) {
        cout << "Name: " << book.name << ", Author: " << book.author << ", ISBN: " << book.isbn << endl;
    }
}
//pair,定义在头文件utility中，存储两个数据，主要用于map插入
void pariBase(){
    //可以定义多种pair
    pair<string, string> str_pair;
    pair<string, vector<int>> vec_pair;
    //初始化
    str_pair = {"ady", "io2020"};
    //或者make_pair
    auto mkpair = make_pair("ady", 1);
    //或者pair 模板
    auto pairint = pair<string, size_t>("io", 2020);
    //map
    auto mappair = map<string, size_t>::value_type("ady", 2020);
}

容器操作

  • 容器赋值:
//容器直接赋值
list<int> nums = {1,2,3};
list<int> nums1(nums);
//迭代器copy
list<int> nums2(nums.begin(), nums.end());
//assign,将nums2的指定位置元素替换为nums的元素
nums2.assign(nums.begin(), nums.end());
nums.assign(3,6);
//swap交换两个容器的内容
vector<int> vnum1(10);
vector<int> vnum2(20);
swap(vnum1, vnum2);

  • 其他操作:

    • push： array和forward_list不支持push_back, 其余顺序容器都支持; 仅deque,list和forward_list才支持push_front。这里添加的都是对象的拷贝，而不是对象本身。
    • insert：forward_list提供了特殊版本的insert成员，部分不支持push_back或者push_front的容器可以使用insert。
    • emplace：可以接受一个类的构造函数，减少对类的构造开销。
    • pop：list，deque支持pop_back和pop_front，forward_list不支持pop_back和push_back, vector和string不支持pop_front和push_front。
    • erase：迭代器删除。
    • clear：清空。
    • size：resize改变容器size，注意forward_list不支持size（）函数，reverse改变容器容量。

  • 顺序容器适配器：Cpp中队列和栈都基于deque实现，优先级队列基于向量实现。

    • stack：需要支持back操作，可以用除array和forward_list以外的容器进行构建。
    • queue：需要支持front和back操作，可以使用list或者deque构建，但是不能使用vector（头部插入删除需要移动所有元素）。
    • priority_queue：（堆操作，需要频繁调整元素位置）除了front和back还要求随机访问能力，所以可以使用vector和deque，但是不能使用list（不支持随机访问）。
#Cpp
最后修改于：2025年01月22日 09:19

添加新评论

Copyright © 2025 io2020
Powered by Typecho | Theme by Waxy