C++ STL容器基本使用

一. 顺序容器：

• 按顺序存储数据；
• 插入速度快，查找相对较慢。
• vector 在最后插入数据;
  1. STLvector类与数组类似，允许随机询问元素，即可使用下标运算符[]指定元素在 vector 中的位置(索引)，从而直接访问或操作元素.
  2. 将所有元素存储在连续的存储单元中
• deque 允许在开头插入或删除元素;
• list 可在任何位置添加或删除对象;
  1. 普通链表的 STL 实现
  2. 不能像 STLvector 中的元素那样随机访问，因为list使用不连续的内存块组织元素
• forward_list 是单向链表，只能沿一个方向遍历。

二. 关联容器

• 指定的顺序存储数据
• 就像词典一样。这将降低插入数据的速度，但在查询方面有很大的优势。
• set：存储各不相同的值，在插入时进行排序;容器的复杂度为对数;
• map: 存储键·值对，并根据唯一的键排序;容器的复杂度为对数;
• multiset：与 set 类似，但允许存储多个值相同的项，即值不需要是唯一的

STL 容器是泛型模板类，因此是通用的，可用于存储字符串、整型、结构或类对象。

三. STL:string

1. 为什么需要string类

字符数组可这样定义

char staticName[20];

• 声明了一个名为staticName的字符数组(也叫字符串)，其长度是固定的(静态的)，包含20 个元素。

• 这个缓冲区可存储一个长度有限的字符串，如果试图存储的字符数超出限制将溢出。不能调整静态数组的长度.

避开这种限制， C++支持动态分配内存，因此可以如下定义更动态的字符数组:

char* dynamicName = new char [ArrayLength];

• 其长度由变量ArrayLength的值指定。

• 而这种值是在运行阶段确定的，因此该数组的长度是可变的。然而，如果要在运行阶段改变数组的长度，必须首先辈辈放以前分配给它的内存，再重新分配内存来存储数据。

2. 实例化和复制 STL string

• 类提供了很多重载的构造函数，因此可以多种方式进行实例化和初始化
• 实例化并初始化 string 对象时，无需关心字符串长度和内存分配细节。

const char* constCStyleString = "Hello String!";

string strFromConst(constCStyleString);

string strFromConst = constCStyleString;

string str2("Hello Stringl");

• string 的构造函数只接受输入字符串的前 n 个字符:

string strPartialCopy(constCStyleString, 5);

• 使其包含指定数量的特定字符:

string strRepeatChars(10, 'a');

3. 访问string内字符内容

• 使用类似于数组的写法：

string strSTLString('Hello String ' );

for(size_t num = 0;num<strSTLString.length();++num){
    cout<<strSTLString[num]<<endl;
}

• 使用迭代器

string::const_iterator iCharacterLocator;
for (iCharacterLocator = strSTLString.begin(); iCharacterLocator != strSTLString.end (); 
++ iCharacterLocator)
    cout<<*iCharacterLocator<<endl;

4.拼接字符串

• 要拼接字符扇，可使用运算符+=，也可使用成员函数 append:

string strSample1('Hello');
string strSample2("String!");
strSample1 += strSample2;
strSample1.append(strSample2);

5.在 string 中查找字符或子字符串

• string 类提供了成员函数 find，该函数有多个重载版本

• std::string::npos 表明没有找到要搜索的元素。如果 find 函数没有返回,npos它将返回一个偏移量，指出子字符串或字符在 string 中的位置。

string strSample("happy birthday!")
size_t charPos = strSample.find("day", 0); //从位置0开始
if (charPos != string::npos)
    cout <<"First instance of \"day\" was found at position " << charPos；
else
    cout <<"Substring not found." << endl;

6. 擦除string

• 在给定偏移位置和字符数时删除指定数目的字符;

string strSample("Hello Stringl Wake up to a beautiful dayl");
strSample.erase (13, 28); //Hello String!

• 在给定指向字符的选代器时删除该字符:

strSample.erase(iCharS); 

• 在给定由两个迭代器指定的范围时删除该范围内的字符:

strSample.erase(strSample.begin(), strSample.end()); 

7. 使用 auto 简化冗长的选代器声明

string::iterator iCharS = find(strSample.begin(), strSample.end(), 'S');

auto iCharS = find(strSample.begin(), strSample.end(), 'S');

8. 字符串反转

string strSample("Hello Stringl We will reverse you!");
reverse(strSample.begin(), strSample.end());

9. 字符串大小写转换

string strInput;
getline(cin, strInput);
transform(strInput.begin(), strInput.end(), strlnput.begin(), toupper); //大写
transform(strlnput.begin(), strlnput.end(), strlnput.begin(), tolower); //小写

四. STL动态数组vector类

• 是一个模板类，提供了动态数组的通用功能
• 在数组末尾添加元素所需的时间是固定的，即在末尾插入元素的所需时间不随数组大小而异在末尾删除元素也如此;
• 在数组中间添加或删除元素所需的时间与该元素后面的元素个数成正比;
• 存储的元素数是动态的，而 vector类自行负责管理内存。

1. 实例化vector

using namespace std;
vector<int> vecDynamiclntegerArray; // vector containing integers
vector<float> vecDynamicFloatArray; // vector containing floats
vector<Tuna> vecDynamicTunaArray; //包含对象

vector也有很多构造函数，初始化方式也多变

• 实例化一个存储整型数据的 vector,使用了默认构造函数

vector<int> vecone;

• vector 至少应包含10个元素。注意，这并没有限制容器最终的大小，而只是设置了初始大小。

vector<int> vectwo(10);

• 10个90值

vector<int> vecthree(10, 90);

• 使用一个 vector 实例化另一个vector 的内容，即复制vector对象或其一部分

vector<int> vecfour(vecthree);

• 使用选代器

vector<int> vecfive(vecthree.cbegin (), vecthree.cbegin () + 5 );

2. push_back()在末尾插入元素

vector <int> veclntegers;
veclntegers.push_back(50);
veclntegers.push_back(1);
vecIntegers.push_back(987);
veclntegers.push_back(1001);
cout << veclntegers.size()<<endl; //4 //请注意函数size()的用法，它返回vector 中存储的元素数。

• c++11支持像数组那样初始化列表

vector<int> veclntegers = {50, 1, 987, 1001};
vector<int> vecMorelntegers {50, 1, 987, 1001};

3. 使用 insert()在指定位置插入元素

• 在开头插入一个元素25

vecone.insert (vecone.begin(), 25);

• 指定插入位置、要插入的元素数以及这些元素的值(都相同):

veclntegers.insert (veclntegers.end(), 2 , 45);

• 还可将另一个 vector 的内容插入到指定位置:

vector<int> vecAnother(2, 30);

• 在vecone位置1处插入vecanother从begin到end的值

vecone.insert(vecone.begin() + 1,vecAnother.begin(), vecAnother.end());

插入位置的迭代器一般最好为：

1. begin()或 end()返回的
2. STL 算法(如find函数)的返回位,find可用于查找元素，然后在这个位置插入另一个元素(这将导致查找的元素向后移).

注意：

• 虽然函数insert功能众多，但给 vector添加元素时，应首选 push_back()。
• 因为insert是低效的，它会导致所有元素后移
• 频繁在容器中间插入元素 应使用list

4. 数组语法访问vector元素

vector<int> vecone(5,10);
for(size_t num; num<vecone.size();++num)
    cout<<vecone[num]<endl;
    cout<<vecone.at(num)<<endl;

注意：

• 使用[]访问 vector 的元素时,面临越界的危险
• 更安全的方法是使用成员函数 at()
• at()函数在运行阶段检查容荡的大小，如果索引超出边界(无论如何都不能这样做).将引发异常

5. 使用指针(迭代器)访问vector元素

vector<int> vecone(5,10);
auto iLocator = vecone.begin();
while(iLocator != vecone.end()
{
    size_t index = distance(vecone.begin(),iLocator);//distance函数计算元素偏移量
    cout<<index<<':'<<*iLocator<<endl;
    ++iLocator;
}

6. pop_back删除vector末尾的元素

vector<int> vecone(10,90);
vecone.pop_back();

7. vector的大小和容量

vector的大小指的是实际存储的元素数，而vector的容量指的是在重新分配内存以存储更多元素
前vector能够存储的元素数。因此，vector的大小小于或等于容量。

• 查询 vector 当前存储的元素数

vector.size();

• 查询vector的容量

vector.capacity();

五. STL 动态数组deque

• deque 是一个STL动态数组类，与vector非常类似
• 支持使用方法push_back()和pop_back()在末尾插入和删除元素
• 与Vector一样， deque也使用运算符[]以数组语法访问其元素

deque<int> deqone;

1.使用 push_front 和 pop_front 在开头插入和删除元素

deque<int> deqone;
deqone.push_back(3);
deqone.push_back(4);
deqone.push_back(5);
deqone.push_front(2);
deqone.push_front(1);
deqone.push_front(0); // 0,1,2,3,4,5
deque.pop_back(); // 0,1,2,3,4
deque.pop_front(); //1,2,3,4

动态数组vector和deque总结

1. 在不知道需要存储多少个元素时，务必使用动态数组vector或deque.
2. 请牢记， vector只能在末端扩容，为此可使用方法push_back().
3. 请牢记，deque可在两端扩容，为此可使用方法push_back()和push_front().
4. pop_back()删除集合最后一个元素
5. pop_front()删除deque开头元素

六.STL::list

• 以模板类 std::list 的方式向程序员提供了一个双向链表
• 双向链表的主要优点是，插入和删除元素的速度快，且时间是固定的

1. 实例化list

list<int> lione(10);
list<int> litwo(10,90);
list<int> lithree(litwo);
vector<int> vecone(10,20);
list<int> lifour(vecone.begin(),vecone.end());

• 声明一个指向 list 中元素的选代器

list<int>::const_iterator isite;
list<int>::iterator isite

2.list开头或末尾插入元素

• 与 deque 类似，要在 list 开头插入元素，可使用其成员方法 push front。
• 要在末尾插入，可使用成员方法 push_back。
• 这两个方法都接受一个参数，即要插入的值:

list<int> lione(10);
lione.push_back(-1);
lione.push_front(2001);

3.在list中间插入元素，借助insert函数

• list 的特点之一是，在其中间插入元素所需的时间是固定的

• 有多个重载版本

• 版本一：第 1 个参数是插入位置，第 2 个参数是要插入的值

iterator insert(iterator pos, const T& x)；

• 版本二：第 1 个参数是插入位置，最后一个参数是要插入的值，而第2个参数是要插入的元素个数。

void insert(iterator pos, size_type n, const T& x)；

• 版本三： 除一个位置参数外，它还接受两个输入迭代器，指定要将集合中相应范围内的元素插入到 list 中

temp1ate <c1ass Inputlterator>
void insert(iterator pos, Inputlterator f, Inputlterator 1)

4. 删除list中元素，借助erase函数

• erase函数有两个重载版本
• 一个接受一个迭代器参数并删除迭代器指向的元素

listlntegers.erase(isite)

• 另一个接受两个选代器参数并删除指定范围内的所有元素

listlntegers.erase(listlntegers.begin() , listlntegers.end());

5. 对list元素进行反转

• list 的一个独特之处是，指向元素的选代器在 list 的元素重新排列或插入元素后仍有效
• 使用reverse()反转元素顺序
• reverseO只是反转list 中元素的排列顺序。
• 它是一个没有参数的简单函数，确保指向元素的选代器在反转后仍有效一如果程序员保存了该迭代器。

lione.reverse();

6. 对list元素进行排序

• list 的成员函数 sort()有两个版本，其中一个没有参数:

listlntegers.sort(); //递增顺序

• 另一个接受一个二元谓词函数作为参数，让您能够指定排序标准:

bool SortPredicate_Descending(const int & lsh, const int& rsh)
{
    return(lsh > rsh); //优先找最大的，递减
}
listlntegers.sort(SortPredicate_Descending);

注意：

• 该谓词解释：这个谓词仅在第一个值比第二个值大时返回true也就是说，
• 使用该谓词时，仅当第一个无素(lsh)的数字值比第二个元素(rsh)大时，sort才认为第一个元素比第二个元素小。
• 基于这种解释，sort交换元素的位置，以满足谓词指定的标准。

7. 总结

• 如果需要频繁地插入或删除元素(尤其是在中间插入或删除时)，应使用list ，而不是vetor.
• 因为在这种情况下，vector需要调整其内部缓冲区的大小，以支持数组语法，
• 还需执行开销高昂的复制操作，而 list 只需建立或断开链接。

七.STL集合set

• 快速地查找和搜索
• set和multiset 之间的区别在于，后者可存储重复的值，而前者只能存储唯一的值。
• 为实现快速搜索， STL set 和 multiset 的内部结构像二叉树
• 这意味着将元素插入到 set 或 multiset时将对其进行排序，以提高查找速度
• 如果您没有指定排序标准，它们将使用默认谓词 std::less，确保包含的元素按升序排列。

1. 实例化set对象

set<int> seone;
multiset<int> musone;

• 要声明一个指向 set 或 mu1tiset 中元素的选代器

set<int>::const_iterator isiter;
set<int>::iterator isiter;

• 也可以指定排序谓词

template <typename T>
struct SortDescending
{
    bool operator() (const T& lhs , const T& rhs) const
    {
        return (lhs > rhs);
    }
};
set <int, SortDescending<int> setIntegerS;

2. set插入元素

setlntegers.insert(1);
msetlntegers.insert (setlntegers.begin(), setlntegers.end());

3. set中查找元素

• set、multiset、map和multimap等关联容器都提供了成员函数 find()

set<int> setone;
setone.insert(10);
setone.insert(13);
setone.insert(9); //9,10,13
auto isiter = setone.find(9);
if (ister != setlntegers.end())
    cout << "found" <<endl;
else
    cout << "not found"<<endl;

4. 删除set中的元素

• 接受键值

setObject.erase(key);

• 接受一个选代器作为参数，删除该迭代器指向的元素:

setObject.erase(iElement);

• 使用迭代器指定的边界，可将指定范围内的所有元素都从 set 或 mu1tiset 中删除:

setObject.erase(iLowerBound, iUpperBound);

八. STL映射类map

key（键）-- value（值）

1. 实例化map对象

map<key, value> mapone;

map<int, string> maptwo;
map<int, string> mapthree(maptwo);
map<int, string> mapfour(mapthree.begin(), mapthree.end())

2. map插入元素

map<int, string> mapone;

• 使用makepair函数

mapone.insert(make_pair(1, "one"));

• 使用std::pair

mapone.insert(pair<int, string>(2, "two"))

• 使用数组语法

mapone[3] = "three";

3.map查找元素

• map关联容器都提供了成员函数find().它让您能够根据给定的键查找值。find()总是返回一个选代器:

map<int, string> mapone;
map<int, string>::const_iterator isiter = mapone.find(1); //find(key)
if(isiter != mapone.end())
{
    cout<<"key: "<<isiter->first<<endl;
    cout<<"value: "<<isiter->second<<endl;
}
else
    cout<<"not found"<<endl;

4. map删除元素

• 将键作为参数，这将删除包含指定键的所有键-值对:

mapObject.erase(key);

• 接受迭代器作为参数，并删除选代器指向的元素:

mapObject.erase(iElement);

• 使用选代器指定边界，从而将指定范围内的所有元素都从 map 或 multirnap 中删除:

mapObject.erase(iLowerBound, iUpperBound);