c++ 容器STL

分手后的思念是犯贱 2022-03-16 09:40 398阅读 0赞

STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类
容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），现在来总结一下它们。
1，vector的应用

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. void print(vector<int>& v)
  5. {
  6.     for (auto m : v)
  7.         cout << m << "=";
  8.     cout << endl;
  9. }
  10. int main()
  11. {
  12.     int a[4];
  13.     //size() 为0
  14.     vector<int> v0;
  15.     //    初始化成n个默认值
  16.     vector<int> v1(-1);
  17. //    cout << v1.size() << endl;
  18.                      //n value
  19.     vector<string> v2(4, "hello");
  20.     //拷贝初始化
  21.     auto v3 = v2;
  22.     //列表初始化
  23.     vector<int> v4{2, 3, 4, 65};
  24.         //           |            |
  25.         //          begin()        end()
  26.     vector<int> v5 = {22, 31};
  27.     for (int i=0; i<v5.size(); i++)
  28.         cout << v5[i] << endl;
  30.     for (auto m : v4)
  31.         cout << m << " ";
  32.     cout << endl;
  33.     //使用迭代器访问动态数组的成员
  34.     //it相当于一个指针，指向数组的某个位置
  35.     for (vector<int> ::iterator it = v4.begin();
  36.             it != v4.end(); it++)
  37.         cout << *it << ", ";
  38.     cout << endl;
  40.     for (auto it = v3.begin(); it != v3.end(); it++)
  41.         cout << *it << "-";
  42.     cout << endl;
  43.     cout << "增加" << endl;
  44.     auto it = v5.begin();
  45.   //    it++;
  46.     //插入在it的位置, 需要获得返回值,返回值是新的迭代器位置
  47.     vector<int> ::iterator p;
  48.     //    (iterator pos, value)
  49.     p = it = v5.insert(it, 90);
  50.     it = v5.insert(it, 91);
  51.     it = v5.insert(it, 92);
  52.     cout << &v5[0] << endl;
  53.     p = v5.erase(p);
  54.     p = v5.erase(p);
  55.     cout << v5.size() << endl;
  56.     cout << &v5[0] << endl;
  57. // 如果it不更新，it指向的还是旧的空间所在的位置
  58.     v5.push_back(1);
  59.     v5.push_back(2);
  60.     print(v5);
  61.     cout << "删除" << endl;
  62.     v5.pop_back();
  63.     v5.pop_back();
  64.     print(v5);
  65. //    for (int i=0; i<20; i++)//    访问了非法空间
  66. //        cout << v5[i] << endl;
  67.     return 0;
  68. }

2,vector的实现

  1. #include <iostream>
  2. using namespace std;
  3. template <typename T>
  4. class Stack
  5. {
  6.     T* ptr;
  7.     int len;
  8.     int max;
  9. public:
  10.     Stack() : ptr(nullptr), len(0), max(4) {
  11.     }
  12.     //拷贝构造
  13.     ~Stack() {
  14.         delete[] ptr;
  15.     }
  16.     int size() {
  17.         return len;
  18.     }
  19.     bool empty() {
  20.         return len == 0;
  21.     }
  22.     void push(const T& t) {
  23.         if (ptr == nullptr) {
  24.             ptr = new T[max];
  25.         } else if (len >= max) {
  26.             max *= 2;
  27.             T* pnew = new T[max];
  28.             for (int i=0; i<len; i++) {
  29.                 pnew[i] = ptr[i];
  30.             }
  31.             delete [] ptr;
  32.             ptr = pnew;
  33.         }
  34.         ptr[len++] = t;
  35.     }
  36.     void pop() {
  37.         if (len > 0)
  38.             len--;
  39.     }
  40.     T& top() {
  41.         if (len == 0)
  42.             return ptr[0];
  43.         return ptr[len-1];
  44.     }
  45. };

3，list的应用

  1. #include <iostream>
  2. //双向链表
  3. #include <list>
  4. using namespace std;
  5. int main()
  6. {
  7.     //0个结点
  8.     list<int> l0;
  9.     cout << "size = " << l0.size() << endl;
  10.     cout << l0.front() << endl;
  11.     cout << l0.back() << endl;
  12.     l0.front() = 90;
  13.     cout << l0.front() << endl;
  14.     cout << l0.back() << endl;
  15. //    l0.resize(1);
  16. //    cout << l0.front() << endl;
  17. //    cout << l0.back() << endl;
  19.     //n个结点，每个都是默认值
  20.     list<int> l1(4);
  21.     //n个结点，都是value
  22.     list<int> l2(4, 10);
  23.     list<int> l3 = {2, 3, 4};
  24.     list<int> l4(l3);
  25.     l2.empty();
  26.     l2.size();
  27.     l2.pop_back();
  28.     l2.pop_front();
  29.     l2.push_front(12);
  30.     l2.push_back(34);
  31.     for (list<int>::iterator it = l2.begin();
  32.             it != l2.end(); it++)
  33.         cout << *it << ", ";
  34.     cout << endl;
  35.     //删除所有值为value的结点
  36.     l2.remove(10);
  37.     //list内的成员方法，从小到大排序
  38.     l2.sort();
  39.     //l2.insert(it, value); 
  40.     //l2.erase(it);
  41.     cout << "front = " << l2.front() << endl;
  42.     //头
  43.     l2.front() = 100;
  44.     //尾
  45.     l2.back() = 200;
  46.     for (auto m : l2)
  47.         cout << m << " ";
  48.     cout << endl;
  49.     return 0;
  50. }

4，list（双向链表）的实现

  1. #include <iostream>
  2. using namespace std;
  3. template <typename T>
  4. class List
  5. {
  6.     struct Node {
  7.         T value;
  8.         Node* prev;
  9.         Node* next;
  10.     };
  11.     Node* head;
  12.     Node* tail;
  13.     int len;
  14. public:
  15.     class Iterator {
  16.         Node* pi;
  17.     public:
  18.         Iterator() : pi(nullptr) { }
  19.         Iterator(Node* p) : pi(p) { }
  20.         Iterator& operator++() {
  21.             pi = pi->next;
  22.             return *this;
  23.         }
  24.         Iterator operator++(int) {
  25.             Iterator t(pi);
  26.             pi = pi->next;
  27.             return t;
  28.         }
  29.         Iterator& operator--() {
  30.             pi = pi->prev;
  31.             return *this;
  32.         }
  33.         Iterator operator--(int) {
  34.             Iterator t(pi);
  35.             pi = pi->prev;
  36.             return t;
  37.         }
  38.         bool operator==(const Iterator& it) {
  39.             return pi == it.pi;
  40.         }
  41.         bool operator!=(const Iterator& it) {
  42.             return pi != it.pi;
  43.         }
  44.         T& operator*() {
  45.             return pi->value;
  46.         }
  47.         T* operator->() {
  48.             return &pi->value;
  49.         }
  50.     };
  51.     List() : len(0) {
  52.         head = tail = new Node{};
  53.     }
  54.     List(int n) : head(nullptr), tail(nullptr), len(n){
  55.         Node* p = nullptr;
  56.         p = new Node{};
  57.         head = tail = p;
  58.         for (int i=0; i<n-1; i++) {
  59.             p = new Node{};    
  60.             tail->next = p;
  61.             p->prev = tail;
  62.             tail = p;
  63.         }
  64.     }
  65.     void show() {
  66.         Node* p = head;
  67.         while(p) {
  68.             cout << p->value << endl;
  69.             p = p->next;
  70.         }
  71.     }
  72.     List(int n, const T& v) : len(n) {
  73.         head = tail = new Node{v, nullptr, nullptr};
  74.         for (int i=0; i<n-1; i++) {
  75.             tail->next = new Node{v, tail, nullptr};
  76.             tail = tail->next;
  77.         }
  78.     }
  79.     List(const List& l) : len(l.len) {
  80.         Node* p = l.head;
  81.         head = tail = new Node{p->value, nullptr, nullptr};
  82.         p = p->next;
  83.         while(p) {
  84.             tail->next = new Node{p->value, tail, nullptr};
  85.             tail = tail->next;
  86.             p = p->next;
  87.         }
  88.     }
  89.     ~List() {
  90.         Node* p = head;
  91.         while(head) {
  92.             cout << "delete " << p->value << endl;
  93.             p = head->next;
  94.             delete head;
  95.             head = p;
  96.         }
  97.     }
  98.     T& front() {
  99.         return head->value;
  100.     }
  101.     T& back() {
  102.         return tail->value;
  103.     }
  104.     int size() {
  105.         return len;
  106.     }
  107.     bool empty() {
  108.         return len == 0;
  109.     }
  110.     void push_back(const T& t) {
  111.         if (len != 0) {
  112.             tail->next = new Node{t, tail, nullptr};
  113.             tail = tail->next;
  114.         } else { 
  115.             head->value = t;
  116.         }
  117.         len++;
  118.     }
  119.     void push_front(const T& t) {
  120.         if (len !=0 ) {
  121.             head->prev = new Node{t, nullptr, head};
  122.             head = head->prev;
  123.         } else {
  124.             head->value = t;
  125.         }
  126.         len++;
  127.     }
  128.     void pop_back() {
  129.         if (len > 1) {
  130.             tail->prev->next = nullptr;
  131.             Node* p = tail;
  132.             tail = tail->prev;
  133.             delete p;
  134.             len--;
  135.         } else if (len == 1) {
  136.             len = 0;
  137.         } 
  138.     }
  139.     void pop_front() {
  140.         if (len > 1) {
  141.             Node* p = head;
  142.             head = head->next;
  143.             head->prev = nullptr;
  144.             delete p;
  145.             len--;
  146.         } else if (len == 1) 
  147.             len = 0;
  148.     }
  150.     void remove(const T& t) {
  151.         Node* p = head;
  152.         if (len == 0)
  153.             return;
  154.         while(p) {
  155.             if (p->value == t) {
  156.                 if (len == 1)
  157.                     len = 0;
  158.                 else if (p == head) {
  159.                     pop_front();
  160.                     p = head;
  161.                 } else if (p == tail) {
  162.                     pop_back();
  163.                     //return;
  164.                     p = nullptr;
  165.                 } else {
  166.                     p->next->prev = p->prev;
  167.                     p->prev->next = p->next;
  168.                     Node* t = p->next;
  169.                     delete p;
  170.                     len--;
  171.                     p = t;
  172.                 }
  173.             } else
  174.                 p = p->next;
  175.         }
  176.     }
  177.     Iterator begin() {
  178.         return Iterator(head);    
  179.     }
  180.     Iterator end() {
  181.         return Iterator(tail->next);
  182.     }
  183. };

5，栈的应用

  1. #include <iostream>
  2. #include <stack
  3. using namespace std;
  4. int main()
  5. {
  6.     stack<int> s1;
  7.     cout << "top = " << s1.top() << endl;
  8.     cout << "size = " << s1.size() << endl;
  9.     s1.push(2);
  10.     s1.push(20);
  11.     s1.push(20);
  12.     cout << s1.top() << endl;
  13.     s1.top() = 30;
  14.     cout << "top = " << s1.top() << endl;
  15.     cout << "size = " << s1.size() << endl;
  16.     cout << s1.empty() << endl;
  17.     s1.pop();
  18.     cout << "size = " << s1.size() << endl;
  19.     if (s1.empty())
  20.         cout << "栈为空" << endl;
  21.     else
  22.         cout << "top = " << s1.top() << endl;
  23.     return 0;
  24. }

6，栈的实现

  1. #include <iostream>
  2. using namespace std;
  4. template <typename T>
  5. class Stack
  6. {
  7.     T* ptr;
  8.     int len;
  9.     int max;
  10. public:
  11.     Stack() : ptr(nullptr), len(0), max(4) {
  12.     }
  13.     //拷贝构造
  14.     ~Stack() {
  15.         delete[] ptr;
  16.     }
  17.     int size() {
  18.         return len;
  19.     }
  20.     bool empty() {
  21.         return len == 0;
  22.     }
  23.     void push(const T& t) {
  24.         if (ptr == nullptr) {
  25.             ptr = new T[max];
  26.         } else if (len >= max) {
  27.             max *= 2;
  28.             T* pnew = new T[max];
  29.             for (int i=0; i<len; i++) {
  30.                 pnew[i] = ptr[i];
  31.             }
  32.             delete [] ptr;
  33.             ptr = pnew;
  34.         }
  35.         ptr[len++] = t;
  36.     }
  37.     void pop() {
  38.         if (len > 0)
  39.             len--;
  40.     }
  41.     T& top() {
  42.         if (len == 0)
  43.             return ptr[0];
  44.         return ptr[len-1];
  45.     }
  46. };

关联容器
7 pair的实现和应用

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. template <typename T1, typename T2>
  6. struct Pair
  7. {
  8.     T1 first;
  9.     T2 second;
  10.     Pair() { }
  11.     Pair(const T1& t1, const T2& t2) : first(t1), second(t2) { }
  12.     bool operator==(const Pair& p) const {
  13.         return first==p.first && second==p.second;
  14.     }
  15.     bool operator<(const Pair& p) const {
  16.         if (first < p.first) 
  17.             return true;
  18.         else if (first==p.first && second < p.second)
  19.             return true;
  20.         return false;
  21.     }    
  22.     bool operator>(const Pair& p) const {
  23.         return !(p < *this || p == *this);
  24.     }
  25.     bool operator<=(const Pair& p) const {
  26.         return *this < p || *this == p;
  27.     }
  28.     //>= != 
  29. };
  30. int main()
  31. {
  32.     Pair<string, int> p1("hello", 123);
  33.     Pair<string, int> p2("hello", 123);
  34.     Pair<int, Pair<int, string> > p3(100, Pair<int, string>(200, "world"));
  35.     cout << p3.first << " " << p3.second.first << " "
  36.         << p3.second.second << endl;
  37.     Pair<int, string[4] > p4;
  38.     p4.first = 1;
  39.     /*
  40.     p4.second.push_back("hello");
  41.     p4.second.push_back("asd");
  42.     */
  43.     p4.second[0] = "fds";
  44.     p4.second[1] = "fdss";
  45.     cout << p4.first << " ";
  46.     for (auto m : p4.second) 
  47.         cout << m << ", ";
  48.     cout << endl;
  49.     cout << p1.first << " " << p1.second << endl;
  50.     cout << p2.first << " " << p2.second << endl;
  51.     if (p1 == p2) {
  52.         cout << "==" << endl;
  53.     } else if (p1 < p2) {
  54.         cout << "<" << endl;
  55.     } else if (p1 > p2) {
  56.         cout << ">" << endl;
  57.     }
  58. };

8,map的应用（实现后序补充）

  1. #include <iostream>
  2. #include <map>
  3. //映射
  4. using namespace std;
  6. int main()
  7. {
  8.     pair<int, string> p;
  9.     //key是唯一的，有序
  10.     //  key     value
  11.     map<int, string> m;
  12.     //make_pair()函数是制作一个pair
  13.     m.insert(make_pair(1003, "Cindy"));
  14.     m.insert({1002, "Mike"});
  15.     m.insert(pair<int, string>(1001, "Tom"));
  16.     //如果key 有相同的，后面的插入会失败
  17.     //pair<iterator, bool>
  18.     auto b = m.insert({1002, "David"});
  19.     cout << b.second << endl;
  21.     bool x = m.erase(1002);
  22.     cout << x << endl;
  24.     //m[key] 可以查找key对应的value
  25.     m[1001] = "Bob";
  26.     cout << m[1001] << endl;
  27.     //m[key]如果没有key, m会增加一个pair
  28.     cout << m[2000] << endl;
  29.     //增加一个pair
  30.     m[1003] = "An";
  31.     //m.find(key), 如果找到key，返回相应的位置，如果没有找到，返回 m.end() 位置
  32.     map<int, string> ::iterator i = m.find(1011);
  33.     if (i != m.end()) {
  34.         cout << "找到了 ";
  35.         cout << i->first << " " << i->second << endl;
  36.     } else {
  37.         cout << "没有找到" << endl; 
  38.     }
  39.     //upper_bound(key) 返回大于key的位置
  40.     auto it1 = m.upper_bound(1001);
  41.     //lower_bound(key) 返回不小于key的位置
  42.     auto it2 = m.lower_bound(1001);
  44.     cout << "it1 " << it1->first << " " << it1->second << endl; 
  45.     cout << "it2 " << it2->first << " " << it2->second << endl; 
  46.     //pair<map<>::iterator, map<>::iterator> 返回上面两个位置
  47.     auto it3 = m.equal_range(1001);
  48.     cout << "it3 l " << it3.first->first << " " <<
  49.         it3.first->second << endl;
  50.     cout << "it3 u " << it3.second->first << " " << 
  51.         it3.second->second << endl;
  53.     for (auto i : m) {
  54.         cout << i.first << " " << i.second << endl;
  55.     }
  56.     for (auto it = m.begin(); it != m.end(); it++) {
  57.         cout << it->first << "," << it->second << endl;
  58.     }
  59.     return 0;
  60. }

9,set的实现和使用（后序补充）

发表评论

表情：
评论列表 （有 0 条评论，398人围观）

还没有评论，来说两句吧...

相关阅读

    相关 C/C++编程：STL容器

    容器 有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_s

    小鱼儿小鱼儿/ 0 赞/ 361 阅读

    相关 c++ 容器STL

    STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的

    分手后的思念是犯贱分手后的思念是犯贱/ 0 赞/ 399 阅读