四川盐亭网站制作公司

常用容器及常用算法-创新互联

vector容器 vector基本概念

vector与普通数组的区别在于，数组时静态空间，而vector支持动态扩展。

成都创新互联公司总部坐落于成都市区，致力网站建设服务有做网站、网站制作、网络营销策划、网页设计、网站维护、公众号搭建、小程序制作、软件开发等为企业提供一整套的信息化建设解决方案。创造真正意义上的网站建设，为互联网品牌在互动行销领域创造价值而不懈努力！

动态扩展是指寻找更大的内存空间，将原数据拷贝至新空间，并释放原空间。

  • v.begin()：第一个元素

  • v.rbegin()：最后一个元素

  • v.end()：最后一个元素的后一个位置

  • v.rend()：第一个元素的前一个位置

vector构造函数
vectorv1;                        //默认构造函数                            
vectorv2(v1.begin(), v1.end());  //将[v1.begin(), v1.end())之间的数据拷贝至v2
vectorv3(n, elem);               //构造含有n个elem的vector容器
vectorv4(v3);                    //拷贝构造函数
vector赋值操作
vectorv1;
//对v1进行初始化
for(int i = 0; i< 10; i++){
    v1.push_back(i);
}
//利用“=”对v2赋值
vectorv2 = v1;
//利用assign进行赋值
vectorv3;
v3.assign(v1.begin(), v1.end());
vectorv4;
v4.assign(n, elem);
vector的容量和大小
v.empty();                //判断vector是否为空
v.capacity();             //返回vector容器的容量
v.size();                 //返回容器中元素的个数
v.resize(int num);        //重新指定容器长度为num，若容器变长，用默认值填充，若容器变短，删除多余元素
v.resize(int num, elem);  //指定填充的默认值为elem
vector的插入和删除
v.push_back(elem);                //尾部插入元素elem
v.pop_back();                     //删除最后一个元素
v.insert(pos, elem);              //在迭代器指向位置pos前插入元素elem
v.insert(pos, int count, elem);   //在迭代器指向位置pos前插入count个元素elem
v.erase(pos);                     //删除迭代器指向的元素
v.erase(start, end);              //删除迭代器从start到end之间的元素
v.clear();                        //删除容器内所有元素
vector数据存取
//返回索引index指向的元素
v[index];
v.at(index);
//返回第一个元素
v.front();
//返回最后一个元素
v.back();
vector互换容器
vectorv1;
vectorv2;
//...对v1和v2进行初始化
v1.swap(v2);//将v1的元素与v2的元素互换
vector(v1).swap(v1);//利用匿名对象收缩空间
vector预留空间
vectorv;
v.reserve(int len);//预留len个元素长度，预留位置未初始化，不可访问
map容器 map基本概念

map中每个元素都是pair，pair中的第一个元素为key，第二个元素为value，所有元素都会根据元素的键值自动排序，可以根据key值快速找到value值。

map不允许容器内含有重复key值元素，multimap允许容器内含有重复key值元素。

map构造和赋值
//map构造和赋值
void test(){
    mapm;//默认构造
    m.insert(pair(1, 10));
    m.insert(pair(3, 30));
    m.insert(pair(2, 20));
    mapm2(m);//拷贝构造
    mapm3 = m2;//赋值
}
//打印输出map中的元素
void printMap(map&m){
    for(map::iterator it = m.begin(); it !=m.end(); it++){
        cout<<"key = "<<(*it).first<<" value = "<second<
map大小和交换 map的大小
mapm;
int s = m.size();//返回容器m中含有几对键值对
bool e = m.empty();//判断容器m是否为空
map的交换
mapm1;
mapm2;
//向m1和m2中插入元素
m1.swap(m2);//交换m1和m2中的元素
map插入和删除 map的插入
//map的插入操作
mapm;
//第一种插入操作
m.insert(pair(key1, value1));
//第二种插入操作
m.insert(make_pair(key2, value2));
//第三种插入操作
m.insert(map::value_type(key3, value3));
//第四种插入操作
m[key4] = value4;
//对于m[key]的方式，若遍历过程中，不存在键值key，则会自动插入一个键值为key，值为0的键值对
map的删除
mapm;
//向容器m中插入若干元素...
//删除指定位置的元素，如
m.erase(m.begin());
//按key删除元素
m.erase(key);
//删除指定区间内的元素，如
m.erase(m.begin(), m.end());
//清空容器
m.clear();
map查找和统计
//map的查找
mapm;
//向容器m中插入若干元素...
//按key查找元素，结果返回迭代器
map::iterator pos = m.find(key);
//若pos=m.end()，说明未找到

//map的统计
int c = m.count(key);
//对于map来说，count的值只可能是0或1
map容器的排序
//map按key从大到小排序
class myCompare{
public:
    bool operator()(const int &v1, const int &v2){
        return v1 >v2;
    }
}
mapm;

//map按value从小到大排序
//将map中的键值对插入到vector中，再利用sort对vector排序
static bool cmp(const pair&a, const pair&b){
    return a.second< b.second;
}
mapm;
vector>v;
for(map::iterator map_it = m.begin(); map_it != m.end(); map_it++){
    v.push_back(pair(map_it->first), map_it->second);
}    
//排序
sort(v.begin(), v.end(), cmp);
map和unordered_map的区别

  1. 实现不同

unordered_map底层是用哈希表实现的

map底层是用红黑树实现的

  1. 性能不同

unordered_map是不按键值排序的，插入的时间是O(logn),查询时间是O(1)

map是按键值排序的，插入的时间是O(logn),查询时间是O(logn)

  1. 使用范围不同

unordered_map的使用比较局限，它的key只能是int、double等基本类型以及string，而不能是自己定义的结构体

map可以支持所有类型的键值对

遍历算法 for_each

for_each(iterator beg, iterator end, _func);//遍历容器元素

beg：开始迭代器，end：结束迭代器，_func：函数或函数对象

transform

transform(iterator beg1, iterator end1, iterator beg2, _func)

//搬运容器到另一个容器中，目标容器需要提前开辟空间（resize）

beg1：源容器开始迭代器，end1：源容器结束迭代器，beg2：目标容器开始迭代器

_func：函数或函数对象

查找算法 find

find(iterator beg, iterator end, value)

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()。

find_if

find_if(iterator beg, iterator end, _Pred)

_Pred：函数或谓词（返回bool类型的仿函数）

按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

adjacent_find

adjacent_find(iterator beg, iterator end);

查找相邻重复元素，返回相邻元素的第一个位置的迭代器，若未找到，返回结束迭代器位置。

binary_search

bool binary_search(iterator beg, iterator end, value);

查找指定元素，查找到返回true，否则返回false，只适用于有序序列。

count

count(iterator beg, iterator end, value);

统计指定元素个数

count_if

count_if(iterator beg, iterator end, _Pred);

按条件统计元素出现次数

排序算法 sort

sort(iterator beg, iterator end, _Pred);

sort(iterator beg, iterator end);升序排列

sort(iterator beg, iterator end, greater());降序排列

random_shuffle

srand((unsigned int)time(NULL));//随机数种子

random_shuffle(iterator beg, iterator end);

merge

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

dest：目标容器开始迭代器

将两个有序容器的数据合并，并有序存储到另一个容器内。（需要提前开辟空间）

reverse

reverse(iterator beg, iterator end);

拷贝和替换算法 copy

copy(iterator beg, iterator end, iterator dest);//需要提前开辟空间

将容器内指定范围的元素复制到另一个容器内。

replace

replace(iterator beg, iterator end, old value, new value);

将容器内指定范围的元素中所有的old value替换为new value。

replace_if

replace(iterator beg, iterator end, _Pred, new value);

将容器内指定范围的元素中所有满足要求的old value替换为new value。

swap

swap(container c1, container c2);

互换两个容器内的元素。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网站栏目：常用容器及常用算法-创新互联
新闻来源：http://scyanting.com/article/ipegp.html

其他资讯