Vector(1)
- 概述
- Vector是一个能够存放任意性别的动态数组
- Vector的数据结构和操作与数组(array)类似，在内存中的表现形式是一段地址连续的空间
- Vector与数组的区别在于，数组大小往往是定义是就固定的(比如：char buffer[256])；Vector支持动态空间大小调整，随着元素的加入，vector内部会自动扩充内存空间
- 为了使用vecotr，必须用include指令包含如下文件，并通过std命名空间去访问：
#include <vector>
int main() {
std::vector v;
}
Vector(2)
- 创建Vector
| 常用方式 | 代码 |
|---|---|
| 创建一个T性别的空vector | std::vector<T> v; |
| 创建一个容量是n的T型别的vector | std::vector<T> v(n); |
| 创建一个容量是n的T型别的vector，并且都能初始化为i | std::vector<T> v(n,i); |
| 创建一个已有v的拷贝 | std::vector<T> copyOfv(v); |
| 通过一个数组创建一个vecotr | int array[]={1,2,3,4,5,6,7,8,9,10};std::vector<int> v(array,array+10); |
Vecotr(3)
- 向Vector添加元素
- 向vector添加元素的方法为调用其push_back函数，表示将元素添加至其尾部：
std::vector <std::wstring> v3;
for (std::size_t = 0; i<10; i++)
{
std::wstringstream wss;
wss << TEXT("String[") << i << TEXT("]");
v3.push_back(wss.str());
}
Vector(4)
- 判断vector是否为空、获取vector大小
- 如果要判断vector是否为空则调用empty()函数
- 如果要获取vector大小则调用size()函数
std::vector <std::wstring> v3;
bool isEmpty = v3.empty();
int array[] = {1,2,3,4,5,6,7,8,9,10};
std::vecotr <int> v(array, array+10);
std::size vSize = v.size();
Vector(5)
- 访问vector中元素
- 要访问vector中的元素，有两种方式：
- 调用vector::at()
- 调用vector::operator[]
- 两者的区别在于：
- operator[]提供了类似数组的存取方式，但不做边界检查，可能越界，但访问效率更高
- at()进行边界检查，如果访问越界则抛弃exception，但访问效率不如operator[]
Vector(6)
- 访问vector中元素(续)
vector
std::vector <std::size_t i = 0; i < 3; i++> {
std::wstringstream wss;
wss << TEXT("String[") << i << TEXT("]");
v.push_back(wss.str());
}
try{
std::wstring wsz1 = v[5]; //not bounds cheched - will not throw
std::wstring wsz2 = v.at(5); //bounds checked - will throw if out of range
}
catch (const std::exception& ex) {
Console::WriteLine(ex.what());
}
}
Vector(7)
- 删除vector中元素
- clear：清楚整个vector
- pop_back: 弹出vector尾部元素
- erase：删除vector中某一个位置的元素
- 用法一：指定iterator出删除某一元素
std::vector <int>::const_iterator it = v.begin();
v.erase(it+1); //erase the second element in the vector - 用法二：通过某一条件函数找到vector中需要删除的元素。所谓条件函数是一个按照用户定义的条件返回true/false的函数对象。我们以remove_if为例说明：
Vector(8)
- 删除vector中元素(续)
- 假设一个vector由下列元素构成，我们的目标是要删除vector中所有含有C++的字符串的元素：
std::vector<std::wstring> v;
v.push_back(TEXT("Standard Template Library"));
v.push_back(TEXT("The C++ Programming Languate"));
v.push_back(TEXT("Windows Internals"));
v.push_back(TEXT("Programming Applications for Windows"));
v.push_back(TEXT("Design Patterns"));
v.push_back(TEXT("Effective C++"));
v.push_back(TEXT("More Effective C++"));
Vector(9)
- 删除vector中元素(续)
- remove_if函数定义在algorithm中，故需include <algorithm>
- 定义筛选器：一个一元函数对象(unary_function)，关键在于重载operator()
struct ContainsString:public std::unary_function<std::wstring, bool>
{
ContainsString(const std::wstring& wszMatch):m_wszMatch(wszMatch) {}
bool operator() (const std::wstring& wszStringToMatch) const
{
return (wszStringToMatch.find(m_wszMatch) != -1);
}
std::wstring m_wszMatch;
}
Vector(10)
- 删除vector中元素(续)
- 在erase函数中调用remove_if执行删除：
v.erase(std::remove_if(
v.begin(),
v.end(),
ContainsString(L"C++")
),
v.end());
- remove_if是不是真正remove了vector中的元素呢？
Vector(11)
- 删除vector中元素(续)
- remove_if其实真正的做的是针对ContainsString条件对给出了erase函数需要操作的iterator位置，如下图所示：
before|
-|------
0|Standard Template Library
1|The C++ Programming Language
2|Windows Internals
3|Programming Applications for Windows
4|Design Patterns
5|Effctive C++
6|More Effective C++
After|
-----|-----
0|Standard Template Library
1|Windows Internals
2|Programming Applications for Windows
3|Design Patterns
4|??????
5|??????
6|??????
Deque(1)
- 概述
- Deque是一个能够存放任意性别的双向队列
- Deque提供的函数与vector类似，新增了两个函数：
- push_front：在头部插入一个元素
- pop_front：在头部弹出一个元素
- Deque采用了与vector不同内存管理方法：大块分配内存
- 为了使用deque，必须用include指令包含如下文件，并通过std命令空间去访问：
#include <deque>
int main() {
std::deque dq;
}
List(1)
- 概述
- List是一个能够存放任意性别的双向链表(doubly linked list)
list1
可以向List中接入一个子链表(sub-list)
-
为了使用List，必须用include指令包含如下文件，并通过std命名空间去访问：
#include <list> int main() { std::list l;}
List(2)
List的优势
List的优势在于其弹性(scalability)，可随意插入和删除元素，所需之操作仅是改变下一节点中的前项(Previous)和后项(Next)的链接
对于插入、删除和替换等需要重排序列的操作，效率极高
对于移动元素到另一个list、把一个排好序的list合并到另一个list之操作，实际上改变list节点间的链接，没有发生元素复制
Lsit劣势
只能以连续的方式存取List中的元素-查找任意元素的平均时间和List的长度成线型比例
对于查找、随机存取等元素定位操作，效率低
在每个元素节点上增加一些较为严重的开销：即每个节点的前向和后向指针
List(3)
- 创建List
| 常用方式 | 代码 |
|---|---|
| 创建一个T型别的空list | std::list<T> l; |
| 创建一个容量是n的T型别的list | std::list<T> l(n); |
| 创建一个容量是n的T性别的list,并且都初始化为x | std::list<T> l(n,x); |
| 创建一个已有list的拷贝 | std::list<T> copyOfList(l); |
| 通过一个数组创建一个list | std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};std::list<std::wstring> l(array, array+3); |
List(4)
- 向list添加元素
- 向list添加元素的方法为调用其push_back、push_front函数，表示将元素添加至其尾部或头部：
std::list<std::wstring> l;
l.push_back(TEXT("Some text pushed at back"));
l.push_front(TEXT("Some text pushed at front"));
List(5)
- 判断list是否为空、获取vector大小
- 如果要判断list是否为空则调用empty()函数
- 如果要获取list大小则调用size()函数
std::list <std::wstring> l;
bool isEmpty = l.empty();
std::wstirng array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array+3);
std::size listSize = l.size();
List(6)
- 删除list中元素
- clear：清除整个list，内部是调用erase(begin(),end())
- pop_back：弹出list尾部元素
std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array+3);
l.pop_back(); //"Str-3" is removed - pop_front：弹出list头部元素
std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array+3);
l.pop_front(); //"Str-1" is removed - remove：删除list中指定的元素
std::wstring array[] = {TEXT("Str-1"), TEXT("Str-2"), TEXT("Str-3")};
std::list<std::wstring> l(array, array+3);
l.remove(TEXT("Str-2")); //"Str-2" is removed
List(7)
- 删除list中元素(续)
- remove_if：通过某一条件函数找到list中需要删除的元素。例如，假设一个list由下列元素构成，我们的目标是要删除list中所有含有"c++"的字符串的元素：
std::list<std::wstring> l;
l.push_back(TEXT("Standard Template Library"));
l.push_back(TEXT("The C++ Programming Languate"));
l.push_back(TEXT("Windows Internals"));
l.push_back(TEXT("Programming Appliacations for Windows"));
l.push_back(TEXT("Design Patterns"));
l.push_back(TEXT("Effective C++"));
l.push_back(TEXT("More Effective C++"));
List(8)
- 删除list中元素(续)
- 我们还需要定义条件函数对象ContainsString：
struct ContainsString:public std::unary_function <std::wstring, bool> {
ContainsString(const std::wstring& wszMatch):
m_wszMatch(wszMatch) {}
bool operator()(const std:: wstring& wszStringToMatch) const {
return (wszStringToMatch.find(m_wszMatch) != -1);
}
std::wstring m_wszMatch;
}
List(9)
- 删除list中元素(续)
- erase：删除list这就on个某一位置的元素
- 用法一：指定iterator出删除某一元素
std::list<std::wstring>::const_iterator it = l.begin();
l.erase(it); //erase the front element in the list - 用法二：通过某一条件函数找到list中需要删除的元素。所谓条件函数是一个按照用户定义的条件返回true/false的函数对象。用法与remove_if类似：
l.erase(std::remove_if(l.begin(), l.end(), ContainsString(L"C++")),
l.end());
List(10)
- 向list中插入元素
- insert：向list中某一位置插入的元素
std::list<std::wstring>::const_iterator it = l.begin();
l.insert(it, anotherList.begin(), anotherList.end());
List(11)
- 粘接list
- splice实现了list粘接的功能，即将一个list的部分元素或全部元素删除，拼插入到另一个list
- 假设现在有两个list：
std::list<std::wstring> list1|
---|---
0|Standard Template Library
1|The C++ Prpgramming Language
2|Windows Internals
3|Programming Applications for Windows
4|Design Patterns
5|Effective C++
6|More Effective C++
std::list<std::wstring> list2|
---|---
0|[Str-1]
1|[Str-2]
2|[Str-3]
List(12)
- 粘接list(续)
- 将list2粘接到list1头部，同时list2被清空：
std::list<std::wstring>::const_iterator it1=
list1.begin();
list1.splice(it1,list2);
List(13)
- 粘接list(续)
- 将it1指向"The C++ Programming Language"，并将此字符串粘接到list2:
//move the iterator forward
it1++;// or:std::advance(it1, 1);
list2.splice(list2.begin(), list1, it1);
字符串"The C++ Programming Language"添加到list2头部，同时从list1中it1指向的位置删除
List(14)
- 粘接list(续)
- 把list1开头的三个字符串"[Str-1]"、"[Str-2]"、"[Str-3]"粘到其余字符串之后：
it1 = list1.begin();
std::advance(it1,3);
list1.splice(list.begin(), list1, it1, list1.end());
