关于程序员:关于合理选择数据结构解题的一些总结

5次阅读

共计 2488 个字符，预计需要花费 7 分钟才能阅读完成。

在解题时，正当地抉择数据结构可真是太重要了，抉择正当不仅使操作简略，更不易把本人搞晕。上面进行适当总结：
1. 应用 STL 容器尽管看上去很高级，有时也能简化一些操作、节俭内存等，但不要什么都想用 STL 容器来解决，因为动态数组更容易操作，且有时比 STL 容器省空间省工夫（拜访快，除非非凡状况，比 map 省空间）
2. 数据结构不要套太多娃，也即开的构造体不要太简单，一层套一层，最初把本人搞晕，最多套一层（比方嵌入另一个构造体，或开一个数组，放一个 STL 啥的）。若有须要，单开构造体或数组啥的，建设一个映射即可，操作会清晰简略很多，也没有占多大内存。

1.insert()：向指定地位处插入元素
erase()：删除单个元素或者一个区间内的所有元素
以上两个操作参数均为迭代器。

2.begin()、rbegin()、end()：别离为第一个元素、最初一个元素、以及尾元素的下一个地址。

3. 能够间接判等，间接比拟。

4. 整体赋值：

vector<int> temp(inDegree, inDegree+N); // 这种用法注意一下，行将 inDegree 数组的从 0 到 N - 1 的全副元素整体赋值给 temp

5. 拓展利用：

vector<int> v;
// 栈
v.erase(--v.end());
v.erase(v.rbegin());
v.pop_back();
// 队列
v.erase(v.begin());
// 双端队列
v.insert(v.begin(), 1);

主动去重并按升序排序。

1.insert():
insert(pos, string) insert(it, it1, it2)

2.erase():
erase(it) erase(first, last) erase(pos, len)

3.substr():
substr(pos, len)

4.find():（留神联合 string::npos 应用）
find(str) find(str, pos)

5.replace():
replace(pos, len, str) replace(it1, it2, str)

6.sscanf() sprintf():
尽管不是 string 所特有的函数，然而联合应用成果很棒（留神应用时联合 c_str()函数能力用）

优先队列设置构造体优先级时队首元素与个别 cmp 示意的意义相同。
优先队列默认队首元素最大，若批改为最小，即：
priority_queue<int, vector<int>, greater<int> > q

上面是构造体优先级设置的一些办法，个别能够联合 priority_queue 和 set 应用。

struct node{
    int x, y;
    friend bool operator < (node a, node b){return a.x < b.x;}
};

struct node{
    int x, y;
    friend bool operator < (const node &a, const node &b){return a.x < b.x;}
};

struct node{
    int x, y;
    friend bool operator < (const node &b) const{return x < b.x;}
};

1.lower_bound,upper_bound：
用于有序数组或容器中。
int* pos = lower_bound(first, last, val)
int* pos = upper_bound(first, last, val)
形参为指针或迭代器。别离用来寻找第一个值大于等于 val 和大于 val 的元素的地位，返回一个指针或迭代器。

2.heap：
make_heap: 依据指定的迭代器区间以及一个可选的比拟函数，来创立一个 heap。O(N)
push_heap: 把指定区间的最初一个元素插入到 heap 中。O(logN)
pop_heap: 弹出 heap 顶元素, 将其搁置于区间开端。O(logN)
sort_heap：堆排序算法，通常通过重复调用 pop_heap 来实现。N*O(logN)
is_heap: 判断给定区间是否是一个 heap。O(N)
is_heap_until: 找出区间中第一个不满足 heap 条件的地位。O(N)

vector<int> v{6, 1, 2, 5, 3, 4};
    // 进行堆的相干操作之前记得先建堆，且留神前面堆的所有操作都默认是大根堆，若想应用小根堆必须增加比拟函数
    // 默认建设大根堆
    make_heap(v.begin(), v.end());
    // 建设小根堆，仅给出这一示范，上面应用小根堆时相似
    make_heap(v.begin(), v.end(), greater<int>());
    // 插入堆
    v.push_back(200);
    push_heap(v.begin(), v.end());
    // 堆顶元素出堆，置于堆开端
    pop_heap(v.begin(), v.end());
    v.pop_back();
    // 堆排序
    sort_heap(v.begin(), v.end());
    // 判断是否是堆
    is_heap(v.begin(), v.end());
    // 返回第一个不是堆元素的迭代器
    auto it = is_heap_until(v.begin(), v.end());

留神：
只有在 vector 和 string 中，能力对迭代器间接加整数来解决
只有 vector 和 string 能够通过下标拜访，其余只能通过迭代器拜访

顺序存储 or 散列存储：个别当须要拜访特定 id 对应的数值只有一个，或只关注是否存在时，应用顺序存储，并独自开拓一个简略的散列数组（或者 map）来建设这种繁多映射关系。但若特定 id 对应多个数值甚至是简单的数据结构时，则思考应用散列存储，间接将全副信息存储在下标为其 id 处，从而便于拜访与批改信息。

对于数组 or map：个别更举荐应用数组，除非那种字符串不好应用数组，或二维甚至三维信息建设映射应用数组会占用大量应用不到的内存时，才去应用 map。并且留神，map 是很占内存的，故尽量少应用。并且次要用来建设映射关系，不要把它当做散列存储工具，散列存储还是更多用数组。

正文完