基于的算法（模板函数）集合结构来存储线性数据

作为 C++ 的标准类库，C++ STL 包含了最可重用的数据结构（容器）和算法（模板函数）。

考虑到数据结构和算法类型的通用性，STL利用模板的语法机制来实现类型泛化，即泛型。

STL 考虑到算法对数据结构的普遍适用性，并增加了一个中间层——迭代器。迭代器也是一个模板类，通常定义为容器类的内部类，封装了一个指向容器类的指针，并重载了一些与指针相关的操作符。每个容器的迭代器都提供了统一命名的接口，方便使用。算法（模板函数）通常将一对迭代器（指向容器的第一个元素和容器的最后一个元素的后面）作为参数来遍历容器元素。

为了让算法（模板函数）的代码更通用，STL通常使用一个函数对象（）作为参数，这样就可以应用于不同的应用特定需求，比如less等。

1 个向量

元素顺序存储（以数组为底层数据结构），元素类型可以嵌套，元素个数可以动态增加，支持随机访问。是 C++ 的推荐类型（而不是 C 数组）。

支持 Inert()，但 () 相对高效。

#include 
#include 
#include 
using namespace std;
bool cmp(int &x, int& y)
{
    return x>y;
}
void vectorUse()
{
    int a[10] = {2,5,8,6,3,7,1,9,4,10};
    vectorvec(a,a+10);
    printf("size:%dn",vec.size());
    printf("正向输出 vec:");
    vector::iterator it,it2;
    for(it=vec.begin();it!=vec.end();it++)
    {
        printf("%d ",*it);
    }
    printf("n");
    int x = 6;
    it2 = find(vec.begin(),vec.end(),x);
    if(it2!=vec.end())
        printf("查找到元素%dn",*it2);
    else
        printf("没有找到元素%dn",x);
    printf("递减排序n");
    sort(vec.begin(),vec.end(),cmp);
    vector::reverse_iterator rit;
    printf("反向输出 vec:");
    for(rit=vec.rbegin();rit!=vec.rend();rit++)
        printf("%d ",*rit);
    printf("n");
}
int main()
{
    vectorUse();
    getchar();
    return 0;
}
/*
size:10
正向输出 vec:2 5 8 6 3 7 1 9 4 10
查找到元素6
递减排序
反向输出 vec:1 2 3 4 5 6 7 8 9 10
*/

2 deque 双端队列

功能类似，但可以在前端和后端相对高效地向其添加数据（使用map管理多个大小的连续内存块）。一个中央控制器（一组连续存储的指向不同元素的指针）和多个缓冲区。

支持开头和结尾（不在中间）的快速增删，也支持随机存取。

#include 
#include 
using namespace std;
void print(deque &dq)
{
    deque::iterator iter;
    for(iter=dq.begin();iter!=dq.end();iter++)
        printf("%d ",*iter);
    printf("n");
}
void userDeque()
{
    deque dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.push_front(3);
    dq.push_back(4);
    print(dq);
    dq.pop_front();
    dq.pop_back();
    print(dq);
}
int main()
{
    userDeque();
    getchar();
    return 0;
}
/*
3 1 2 4
1 2
*/

3 list 链表

由节点组成的双向链表（每个节点有两个指向前任和后继的指针），可以在任意位置进行快速插入和删除操作。

#include 
#include 
using namespace std;
bool cmp(const int &n)
{
    return n<3;
}
void print(list &lst)
{
    list::iterator it;
    for(it=lst.begin();it!=lst.end();it++)
        printf("%d ",*it);
    printf("n");
}
void useList()
{
    int a[] = {1,2,3,3,3,4,5,4,4,5};
    int n = sizeof a / sizeof *a;
    list lst(a,a+n);
    lst.remove_if(cmp);
    cout<<"remove_if: ";
    print(lst);
    lst.unique();
    cout<<"unique: ";
    print(lst);
}
void useList2()
{
    int a[] = {3,5,1,4,6,2};
    listlst(a,a+6);
    list::iterator iter;
    lst.sort();
    for(iter=lst.begin();iter!=lst.end();iter++)
        printf("%d ",*iter);
    printf("n");
    lst.sort(greater());
    for(iter=lst.begin();iter!=lst.end();iter++)
        printf("%d ",*iter);
    printf("n");
}
class Ctest
{
    int n;
public:
    Ctest(int m):n(m){}
    ~Ctest(){}
    const int getn() const
    {
        return n;
    }
    const bool operators.getn();
    }
};
void print(list &lst)
{
    list::iterator it;
    for(it=lst.begin();it!=lst.end();it++)
        printf("%d ",*it);
    printf("n");
}
void useList3()
{
    Ctest obj1(3),obj2(5),obj3(2);
    Ctest obj4(7),obj5(4),obj6(1),obj7(6);
    list lst1,lst2;
    lst1.push_back(obj1);
    lst1.push_back(obj2);
    lst1.push_back(obj3);
    lst2.push_back(obj4);
    lst2.push_back(obj5);
    lst2.push_back(obj6);
    lst2.push_back(obj7);
    printf("排序前：n");
    printf(" lst1: ");
    print(lst1);
    printf(" lst2: ");
    print(lst2);
    printf("排序n");
    lst1.sort();
    lst2.sort();
    printf("排序后：n");
    printf(" lst1: ");
    print(lst1);
    printf(" lst2: ");
    print(lst2);
    printf("lst1合并到lst2n");
    lst2.merge(lst1);
    print(lst2);
}
int main()
{
    //useList()
    useList2();
    useList3();
    getchar();
    return 0;
}
/* useList(); vc6运行有误，在线可运行
remove_if: 3 3 3 4 5 4 4 5 
unique: 3 4 5 4 5 
1 2 3 4 5 6
6 5 4 3 2 1
*/

4套收藏

线性数据存储在树结构中二进制树型搜索算法，以确保数据元素（节点、键）的预定顺序。它的底层数据结构是红黑树（一种二叉平衡树，在增删数据时考虑了数据的顺序，需要考虑调整元素的存储位置）。元素必须是唯一的。

为什么 STL 集合的底层使用红黑树而不是哈希表？Set 支持集合操作。数据有序时，并集、交集、差集等集合运算的时间复杂度会大大降低，而红黑树是有序结构。

#include 
#include 
#include 
using namespace std;
void print(set &st)
{
    set::iterator it;
    for(it=st.begin();it!=st.end();it++)
        printf("%d ",*it);
    printf("n");
}
void useSet()
{
    setst1,st2,st3;
    int a[]={4,1,2,6};
    int n=sizeof a / sizeof *a;
    st1.insert(a,a+n);
    int b[]={1,5,3,2,4};
    int m=sizeof b / sizeof *b;
    st2.insert(b,b+m);
    //set::iterator it3;
    printf("set1: ");
    print(st1);
    printf("set2: ");
    print(st2);
    insert_iterator< set > insert_it(st3,st3.begin());
    set_union(st1.begin(),st1.end(),st2.begin(),st2.end(),insert_it);
    printf("并集：");
    print(st3);
    st3.clear();
    set_intersection(st1.begin(),st1.end(),st2.begin(),st2.end(),insert_it);
    printf("交集：");
    print(st3);
    st3.clear();
    set_difference(st1.begin(),st1.end(),st2.begin(),st2.end(),insert_it);
    printf("差集：");
    print(st3);
    st3.clear();
    
}
int main()
{
    useSet();
    getchar();
    return 0;
}
/*
set1: 1 2 4 6
set2: 1 2 3 4 5
并集：1 2 3 4 5 6
交集：1 2 4
差集：6
*/

5地图地图

线性数据存储在树结构中，以确保数据元素（节点，由关键字和值组成）的预定顺序。它的底层数据结构是红黑树（一种二叉平衡树，在增删数据时考虑了数据的顺序，需要考虑调整元素的存储位置）。元素必须是唯一的。

元素关键字与值一一对应，可根据关键字进行快速搜索。

我们知道C数组支持下标运算，通过数字索引映射元素的存储位置，本质上是指针算术运算的语法糖。map还支持下标操作二进制树型搜索算法，通过关键字映射元素的存储位置，本质上是一种树型的二分查找。

#include 
#include 

6栈栈

在某些情况下，我们希望限制访问元素的顺序。如后进先出（最后一个元素存入，保证先访问）。最常见的适用场景是函数的嵌套调用和返回、括号匹配、基数转换、优先级遍历等。这种具体的数据结构，我们可以简单的通过数组或者列表来模拟。与支持随机访问的数组或支持顺序访问的列表不同，当我们使用数组或列表进行模拟时，它被限制为只能在一端进行操作（添加、删除、读取）。STL栈的底层数据结构一般使用list或者deque。

#include        // std::cout
#include           // std::stack
int main ()
{
    std::stack mystack;
    
    for (int i=0; i<5; ++i) 
        mystack.push(i);
    
    std::cout << "Popping out ";
    std::cout << mystack.size();
    std::cout << " elements...";
    while (!mystack.empty())
    {
        std::cout << ' ' << mystack.top();
        mystack.pop();
    }
    std::cout << 'n';
    getchar();
    return 0;
}
// Popping out 5 elements... 4 3 2 1 0

7 队列队列

在某些情况下，我们希望限制访问元素的顺序。比如后进后出（最后一个元素存入，保证最后一次访问）。最常见的应用场景是广度优先遍历等。这种具体的数据结构，我们可以简单的通过数组或者列表来模拟。与支持随机访问的数组或支持顺序访问的列表不同，当我们使用数组或列表进行模拟时，我们限制它们只能在前后端操作（增加、删除、读取）。Queue需要提供and的能力，所以可以使用list或deque作为底层数据结构，但不能作为底层数据结构。

// constructing queues
#include        // std::cout
#include           // std::deque
#include            // std::list
#include           // std::queue
int main ()
{
  std::deque mydeck (3,100);        // deque with 3 elements
  std::list mylist (2,200);         // list with 2 elements
  std::queue first;                 // empty queue
  std::queue second (mydeck);       // queue initialized to copy of deque
  std::queue<int,std::list > third; // empty queue with list as underlying container
  std::queue<int,std::list > fourth (mylist);
  std::cout << "size of first: " << first.size() << 'n';
  std::cout << "size of second: " << second.size() << 'n';
  std::cout << "size of third: " << third.size() << 'n';
  std::cout << "size of fourth: " << fourth.size() << 'n';
  int sum (0);
  for (int i=1;i<=10;i++) 
      first.push(i);
  while (!first.empty())
  {
     sum += first.front();
     first.pop();
  }
  std::cout << "total: " << sum << 'n';
  std::cout << first.front() << " " << first.back();
  return 0;
}
/*
size of first: 0
size of second: 3
size of third: 0
size of fourth: 2
total: 55
0 10
*/

8 优先队列

在某些情况下，我们希望优先级最高的元素（例如最大值或最小值）确保它被首先访问。这样的数据结构称为优先级队列。当然，该数据结构的数据元素的添加或删除需要考虑元素存储的优先顺序进行调整。需要提供随机访问的能力，所以可以使用 or deque 作为底层数据结构，但不能 list 作为底层数据结构。

优先级队列通常用堆来实现，堆一般可以用二叉树来实现。

#include 
#include 
using namespace std;
void print(priority_queue &pq)
{
    while(!pq.empty())
    {
        printf("%d ",pq.top());
        pq.pop();
    }
    printf("n");
}
void print(priority_queue<int,vector,greater > &pq)
{
    while(!pq.empty())
    {
        printf("%d ",pq.top());
        pq.pop();
    }
    printf("n");
}
void useQue()
{
    int a[] = {3,6,1,5,4,2};
    int n = sizeof a / sizeof *a;
    priority_queuepq1(a,a+n); // 默认以vector作为底层容器
    print(pq1);
    // 显式声明底层容器vector，谓词函数greater
    priority_queue<int,vector,greater > pq2(a,a+n);
    print(pq2);
}
#include 
struct Stud
{
    int no;
    string name;
    Stud(int n,string na):no(n),name(na){}
    bool operator<(const Stud &s)const{
        return no(const Stud &s)const{
        return no>s.no;
    }
};
struct StudCmp{ // 结构体定义函数对象
    bool operator()(const Stud &s1,const Stud &s2)const{
        return s1.name > s2.name;
    }
};
void print(priority_queue &pq)
{
    while(!pq.empty())
    {
        printf("[%d %s] ",pq.top().no,pq.top().name.c_str());
        pq.pop();
    }
    printf("n");
}
void print(priority_queue<Stud,vector,StudCmp > &pq)
{
    while(!pq.empty())
    {
        printf("[%d %s] ",pq.top().no,pq.top().name.c_str());
        pq.pop();
    }
    printf("n");
}
void useQue2()
{
    Stud a[] = {Stud(1,"Mary"),Stud(3,"John"),Stud(2,"Henry")};
    int n = sizeof a / sizeof *a;
    priority_queue pq1(a,a+n);
    print(pq1);
    priority_queue<Stud,vector,StudCmp >pq2(a,a+n);
    print(pq2);
}
int main()
{
    useQue();
    useQue2();
    getchar();
    return 0;
}
/*
6 5 4 3 2 1
1 2 3 4 5 6
[3 John] [2 Henry] [1 Mary]
[2 Henry] [3 John] [1 Mary]
*/

9 无序哈希表

数据需要存储和获取，必须考虑效率。哈希表是这种思路的最佳实践。

我们知道数组可以通过数字下标随机访问，但只能顺序访问。

当哈希存储在数据元素中时，使用哈希函数（以数据元素的关键字为参数）计算数据元素的特定下标作为存储位置（当然也考虑到冲突处理） . 这样，在访问数据元素时，可以以关键字作为下标索引进行访问，最好的情况下可以达到O(1).

10// unordered_map::operator[]
#include 
#include 
#include 
int main ()
{
  std::unordered_map mymap;
  mymap["Bakery"]="Barbara";  // new element inserted
  mymap["Seafood"]="Lisa";    // new element inserted
  mymap["Produce"]="John";    // new element inserted
  std::string name = mymap["Bakery"];   // existing element accessed (read)
  mymap["Seafood"] = name;              // existing element accessed (written)
  mymap["Bakery"] = mymap["Produce"];   // existing elements accessed (read/written)
  name = mymap["Deli"];      // non-existing element: new element "Deli" inserted!
  mymap["Produce"] = mymap["Gifts"];    // new element "Gifts" inserted, "Produce" written
  for (auto& x: mymap) {
    std::cout << x.first << ": " << x.second << std::endl;
  }
  return 0;
}
/*
Gifts: 
Deli: 
Produce: 
Seafood: Barbara
Bakery: John
*/

10 总结

STL 中的容器（数据结构）和模板类函数（算法）是提供给程序员的“轮子”。凝聚了库设计者和实现者的最佳编程思想。

每个容器都有自己的底层数据结构，每个容器都有自己特定的优势和应用场景。

-结尾-

文章来源:http://www.toutiao.com/a7042460793232687620/

------本页内容已结束，喜欢请分享------

感谢您的来访，获取更多精彩文章请收藏本站。