---
# System prepended metadata

title: 演算法題目踩到的雷

---

# 演算法題目踩到的雷

`multiset` 不能用 `rbegin` 當作 `erase` 的 `position`
:::info
`erase` 不能用 `reverse iterator` 當作 `position`，像是 `rbegin()` 或是 `rend()` 都不行。
:::

Reference & vs. Pointer *
`Reference` 是參考的意思，比較像變數的 `alias`，也就是別名，在宣告的時候就要賦值完成，且對象不能被更改
`Pointer` 則是指向變數的指標，不需要在宣告時就賦值，可以在宣告後再賦值，而且賦值的內容可以被更改

對一個 `list` 進行 `min` 或 `max` 的比較時，要導入函式庫 `algorithm`

用 `sort(arr.rbegin() , arr.rend())` 可以對陣列進行降序排序

在 `sort` 的 `compare` 放上 `greater<>()` 可以對陣列進行降序排序
在 `sort` 的 `compare` 放上 `less<>()` 可以對陣列進行升序排序

用 `accumulate(arr.begin() , arr.end() , 0LL)` 可以取得陣列的所有元素和，需要導入函式庫 `numeric`
`0LL` 是 `0` 的 `long long` 型別

在 `C++20` 中，命名空間 `std` 中有一個成員是 `count`，所以如果使用了 `using namespace std` 又宣告了 `count`，就有可能得到 `error: reference to 'count' is ambiguous` 的錯誤
:::info
**解決辦法：在 `count` 前加上 `::`**
```cpp=
#include <iostream>

using namespace std;

int count=0 ;

int main()
{
    count++ ; // error: reference to 'count' is ambiguous
    ::count++ ; // success
    ++::count ; // success
}
```
因為寫程式的文件內也可以被視為命名空間，所以可以使用[**範圍解析運算子`::`**](https://learn.microsoft.com/zh-tw/cpp/cpp/scope-resolution-operator?view=msvc-170) 來調用位於全域的 `count`。
:::

```cpp=
vector<int> arr ;
for (int i=0 ; i<3 ; ++i)
{
    cin >> m ;
    arr.emplace_back(m) ;
}
for (auto i : arr) arr.emplace_back(-i) ;
```
遍歷 `vector` 本身又向 `vector` 加入元素，是[**未定義的行為**](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules-for-c-containers)，可能導致[**出錯**](https://stackoverflow.com/questions/75804757/get-a-random-number-when-emplace-an-element-with-range-based-for-loop)
因為過程中如果 `vector` 的空間不夠，就會變更 `.capacity()` 與 `.size()`，並導致所有的迭代器與參考(包含 `.end()`)失效
但如果 `.size()` 沒有超過 `.capacity()`，那就只有 `.end()` 迭代器會失效而已。
> _"...If the new size() is greater than capacity() then all iterators and references (including the end() iterator) are invalidated. Otherwise only the end() iterator is invalidated...."_

所以應該直接對索引(`index`)進行操作，或者是改用這個[**寫法**](https://stackoverflow.com/questions/14373934/iterator-loop-vs-index-loop)：
```cpp=
arr.reserve(2 * arr.size()); // reserve space for twice as many elements
auto first = arr.begin();
auto last = arr.end();
for ( ; first != last; ++first)
    arr.emplace_back(-*first);
```

`dfs` 用到的參數，除了固定不變的數字外，其他都盡量在 `function` 內宣告，避免變數的值被覆蓋

`map` 適合在需要排列時使用，因為使用了紅黑樹的資料結構
`unorder_map` 適合在有大量查詢時使用，因為使用了 `hash_table`，所以時間複雜度為 `O(N)`