vector底層為動態數組

1. 類構成

   • class vector : protected _Vector_base
   • _Vector_base:
     • _M_start：容器元素開始的位置
     • _M_finish：容器元素結束的位置
     • _M_end_of_storage：動態內存最后一個元素的下一個位置

2. 構造函數

   • 無參構造

     根據性能優先規則，沒有申請動態內存

   • 初始化元素個數的構造

     申請了動態內存，避免多次申請影響性能

3. 插入元素

   先檢查空間，不夠則申請內存翻倍

   • 插入到最后
   • 插入到非最后：待插入位置之后的元素往后移一位，然后插入

4. 刪除元素

   刪除元素不會釋放已申請的內存

   • 刪除最后：_M_finish往前移動一位
   • 刪除非最后：待刪除位置之后的元素往前移一位，然后執行“刪除最后”操作

5. 讀取元素

   返回的是具體元素的引用

   • 操作符[]
   • at()：比[]多一步越界檢查操作

6. 修改元素

   • 不支持直接修改某個位置的元素
   • 通過讀取元素，獲取引用，然后修改
   • 先刪除后插入

7. 釋放空間

   • swap一個空容器
   • C++ 11：shrink_to_fit 將容器的空間收縮到容器大小。先clear()將容器清空（不會釋放空間），然后收縮空間大小

參考：【C++面試題】vector底層實現原理_嗶哩嗶哩_bilibili

---

fill和assign

1. std::fill（算法庫函數）

   • 功能：將指定范圍內的元素逐個賦值為給定值。

   • 語法：

     #include <algorithm>
     std::fill(iterator begin, iterator end, value);
     

   • 行為

     • 遍歷 [begin, end) 范圍內的元素，將每個元素賦值為 value。
     • 不改變容器大小，僅修改已有元素的值。

   • 適用容器：所有支持迭代器的容器（如 vector, array, deque, 原生數組等）。

   • 優點：

     • 高效：直接覆蓋現有元素，無需重新分配內存。
     • 靈活性：可局部修改（例如只修改某一部分元素）。

   • 缺點：需要確保目標范圍有效（例如不越界）。

示例：

std::vector<int> vec = {1, 2, 3, 4};
std::fill(vec.begin(), vec.end(), 0); // vec → {0, 0, 0, 0}
std::fill(vec.begin() + 1, vec.end() - 1, 5); // vec → {0, 5, 5, 0}

2. assign（容器成員函數）

   • 功能：替換容器的內容，可以指定新元素的數量和值，或從其他容器/迭代器復制數據。

   • 語法：

     // 用 n 個 value 替換容器內容
     container.assign(n, value);// 用迭代器范圍 [begin, end) 替換容器內容
     container.assign(begin, end);
     

   • 行為：

     • 銷毀原有元素，重新分配內存（可能觸發內存重新申請）。
     • 新內容可以是重復值或來自其他容器。

   • 適用容器：支持動態修改的序列容器（如 vector, deque, list, string）。

   • 優點：

     • 簡潔性：一行代碼即可替換整個容器的內容。
     • 靈活性：支持從不同數據源（如另一個容器或初始化列表）賦值。

   • 缺點：

     • 潛在性能開銷：若新內容大小與原有內容不同，可能觸發內存重分配。
     • 數據丟失：原有內容被完全覆蓋。

示例：

std::vector<int> vec = {1, 2, 3, 4};
vec.assign(3, 10);       // vec → {10, 10, 10}（大小變為 3）
vec.assign({5, 6, 7});   // vec → {5, 6, 7}（用初始化列表替換）

3. 關鍵區別

特性	std::fill	assign
作用范圍	修改指定范圍內的已有元素	替換整個容器的內容
內存操作	不改變容器大小，無內存分配	可能觸發內存重新分配
性能	高效（直接覆蓋）	可能低效（若大小變化）
適用場景	局部修改或保持容器大小不變時	需要完全替換內容或調整大小時
代碼簡潔性	需要顯式指定范圍	一行代碼替換全部內容

4. 如何選擇

• 使用 std::fill 當：
  • 需要保留容器原有結構（如大小不變）。
  • 僅需修改部分或全部元素的值（例如重置為默認值）。
  • 避免內存重分配（對性能敏感的場景）。
• 使用 assign 當：
  • 需要完全替換容器內容（例如用新數據覆蓋舊數據）。
  • 需要調整容器大小（例如從 n 個元素變為 m 個元素）。
  • 從其他容器或初始化列表快速賦值。