【转】三种容器vector, list, deque的对比

原博客地址

向量 vector

是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数组。
在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：

【转】序列合并(洛谷P1631)

序列合并

题目描述

有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2 个和， 求这N^2 个和中最小的N个。

TopK问题(最大/小的k个数)

首先简单的陈述一下问题，对于一个整数数组，找出其中最小的k个数，例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

leetcode链接，这篇博客参考了leetcode的官方解答。

求最大或者最小k个数方法都是一样的，下面的解法都是针对最小的k个数。

【转】stringstream(sstream)常用用法介绍

转载自这篇博客

本文主要介绍 C++ 中 stringstream 类的常见用法。

1 概述

<sstream> 定义了三个类：istringstream、ostringstream 和 stringstream，分别用来进行流的输入、输出和输入输出操作。本文以 stringstream 为主，介绍流的输入和输出操作。

<sstream> 主要用来进行数据类型转换，由于<sstream> 使用 string 对象来代替字符数组（snprintf方式），就避免缓冲区溢出的危险；而且，因为传入参数和目标对象的类型会被自动推导出来，所以不存在错误的格式化符的问题。简单说，相比c库的数据类型转换而言，<sstream> 更加安全、自动和直接。

C/C++中各种类型的最大最小值

需要导入#include<limits.h>和#include<float.h>两个库，下面是个各个常量的说明。

ccf-csp 202006-3 markdown渲染器(c/c++)

题目就不过多描述了，就是针对markdown的两种格式段落和列表进行行数的计数。这个问题可能处理起来比较麻烦，接下来简要介绍一下我的做法吧。

C/C++输入输出加速(算法考试重要!)

加上这么一句：

1

ios::sync_with_stdio(false);

C++ STL 中 unique() 函数详解

1.简要说明

unique()函数用于删除序列中重复的相邻元素，注意一定是相邻元素（所以使用unique()函数前一般都需要进行排序），而且这里的删除也不是直接删除（会返回一个迭代器，之后再使用erase()函数进行删除）

【转】C++给vector去重的两种方法

转自这篇博客

第一种方法是简单的利用set的特性，这部分代码比较简单，直接上code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <vector>
#include <set>

using namespace std;


int main()
{
    int myints[] = {1,2,3,1,1};
    int len = sizeof(myints)/sizeof(int);
    vector<int> vec(myints, myints + len);
    set<int>s(vec.begin(), vec.end());
    vec.assign(s.begin(), s.end());
    for(int x : vec)
        cout << x << ",";
    return 0;
}

第二种方法是结合sort和unique函数

unique()函数将相邻且重复的元素放到vector的尾部 然后返回指向第一个重复元素的迭代器再用erase函数擦除从这个元素到最后元素的所有的元素。

所以可以先进行排序，这样重复元素就会堆一起了，调用unique()函数，再调用erase函数删除重复。代码见下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
    int myints[] = {1,2,3,1,1};
    int len = sizeof(myints)/sizeof(int);
    vector<int> vec(myints, myints + len);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int x : vec)
        cout << x << ",";
    return 0;
}

上述代码中
for (auto x : nums)
作用就是迭代容器中所有的元素，每一个元素的临时名字就是x，等同于下边代码
for (vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter++)

图像处理:分水岭算法（图像分割）

分水岭算法

分水岭算法是一种图像区域分割法，分割的过程中将图片转化为灰度图，然后我会将灰度值看作是海拔，然后向较低点注水，这种基于地形学的解释，我们着重考虑三种点：