set

set 容器介紹

set屬於關聯容器(Associative Container)，其按照某種排序方式排序且儲存的元素是唯一的

預設情況下set按照key進行升序排序，可以藉由仿函式來變更其排序的方式

set 的底層實現是二叉搜尋樹，因此 set 不提供更改資料的接口，避免更新破壞二叉搜尋樹的特性

// Example
int main()
{
set<int> s; // 空set
set<int> s2 = {6, 4, 2, 8, 3, 1}; // 以一至多個資料進行初始化
for (auto &e : s2)
{
 cout << e << " ";
}
cout << endl;
return 0;
}

set 接口介紹

插入

插入的接口有：insert()和 emplace()

• insert : 插入已經構造好的物件 (可以簡單理解為不會在插入的時候原地構造物件)

  (對隱式類型來說，是先構造出一份物件的臨時拷貝再插入)

• emplace : 直接在容器內部原地構造物件 => emplace 是函數模版，直接推演

int main()
{
  set<pair<char, int>> ms;
  ms.emplace('a', 24); // emplace 直接調用 pair 的構造函式然後插入 set

  // ms.insert('b', 25); // 報錯，因為 insert 只能接收一個參數

  ms.insert(make_pair('b', 25)); // 先構造出物件，再插入 set

  for (auto it = ms.begin(); it != ms.end(); ++it)
    cout << " " << (*it).first << " "
    << (*it).second << endl;
    // Output : a 24 b 25
  return 0;
}

訪問

set 的訪問可以由迭代器來實現

int main()
{
set<int> s1 = {3, 5, 4, 2, 7};
auto it = s1.begin();
while (it != s1.end())
{
 cout << *it << " ";
 it++;
}

return 0;
}

查找

int main() {
set<int> s = {1, 4, 2, 3, 5};

auto it = s.find(3); // 查找 3
/*
如果找到，則返回指向該元素的迭代器。如果未找到，則返回std::set::end()
*/
    auto it2 = s.count(4); // count 和 find 的差別在於， count 返回的是要查找的數據數據的個數
if (it != s.end()) cout << *it;
else cout << "Element not Found!";
return 0;
}

刪除

int main() {
 set<int> s = {1, 4, 2, 3, 5};

 s.erase(5);
 s.erase(s.begin()); // 用迭代器刪除
    /*
    返回從 set 容器中刪除的元素數量。對於 set ，該值始終為 1 或 0
    */
 for (auto x: s) cout << x << " ";
 return 0;
}

其他接口

1. lower_bound() : 找到 set 中等於或大於給定值的第一個元素
2. upper_bound() : 找到 set 中第一個大於給定值的元素

int main()
{
    set<int> s = {5, 4, 3, 8, 6, 0, 7, 1};
    auto lower = s.lower_bound(3);
    auto upper = s.upper_bound(7);

    s.erase(lower, upper); // s.erase(3,8); 左閉右開 所以是刪除 3~7
    for (auto &e : s)
    {
        cout << e << " "; // 0 1 8
    }
    cout << endl;

    return 0;
}

時間複雜度

map

map 容器介紹

map也屬於關聯容器，其與set的區別在於map是以 <key,value>的形式存儲

預設排序是根據key進行升序且key的值不允許重複

map 的底層是使用紅黑樹實現，所以有修改的接口

map 接口介紹

插入

map 的插入方式有三種

1. insert : 只插入一次，如果後面重複插入相同的 key 不同的 value 也不會改變 value 的數據

2. operator []

   插入又分為 key 是否以存在於 map 中，若存在則改變 value ( 假如值與原本的不一樣 )；

   反之則插入 <key,value> 到 map 中

3. emplace：主要還是和 insert 形成對比，直接調用構造函式構造物件，而不是先構造才能插入

// insert
int main()
{
  map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};
  m.insert({"f", 6});
  for (auto &e : m)
  {
    cout << e.first << " " << e.second << endl;
  }
  cout << endl;
  m.insert({"a", 10}); // 插入重複的數據
  for (auto &e : m)
  {
    cout << e.first << " " << e.second << endl;
  }
  cout << endl;

  return 0;
}
/*
output:
a 1
b 2
c 3
d 4
e 5
f 6

a 1
b 2
c 3
d 4
e 5
f 6
*/

// operator []
int main()
{
    map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};

    m["f"] = 6;

    for (auto &e : m)
    {
        cout << e.first << " " << e.second << endl;
    }
    cout << endl;

    m["a"] = 10;
    for (auto &e : m)
    {
        cout << e.first << " " << e.second << endl;
    }
    cout << endl;

    return 0;
}
/*
a 1
b 2
c 3
d 4
e 5
f 6

a 10
b 2
c 3
d 4
e 5
f 6
*/

訪問

// 訪問可以利用迭代器、[]、或at
int main() {
 map<int, string> m = {{1, "Geeks"},
          {2, "For"}, {3, "Geeks"}};
 cout << m[1] << endl;
 cout << m.at(2);
 return 0;
}
/*
output:
Geeks
For
*/

修改

// 修改可以使用[] 或 at
int main() {
 map<int, string> m = {{1, "Geeks"},
          {2, "For"}, {3, "Geeks"}};

 // 修改數據
 m[0] = "Tweaks";
 m.at(1) = "By";

 cout << m[0] << endl;
 cout << m.at(1);
 return 0;
}
/*
output:
Tweaks
By
*/

查找

int main() {
 map<int, string> m = {{1, "Geeks"},
          {2, "For"}, {3, "Geeks"}};

 // 查找key為2的數據
 auto it = m.find(2);
 /*
 find : 如果有找到返回這個數據的迭代器；反之返回 end()
 */
 if (it != m.end())
     cout << it->first << " " << it->second;
 else cout << "Key not Found!";
 return 0;
}

刪除

int main() {
 map<int, string> m = {{1, "Geeks"},
          {2, "For"}, {3, "Geeks"}};

 // 刪除
 m.erase(2);
 m.erase(m.begin());
 // 返回從 map 容器中刪除的元素數量。對於 map ，該值始終為 1 或 0
 for(auto i : m)
   // 第一個->是迭代器運算符重載，返回pair*，第二個箭頭是結構指標解引用取pair數據
     cout << i.first << " " << i.second // 3 Geeks
     << endl;
 return 0;
}

時間複雜度