C++ STL multimap使用

C++ multimap使用

multimap

• C++ multimap使用
• • 概述
  • 建立multimap
  • • 構造函數
    • opertor=
  • 元素通路
  • • at
    • operator[ ]
  • 疊代器
  • • begin\cbegin
    • end\cend
    • rbegin\crbegin
    • rend\crend
  • 容量
  • • empty
    • size
    • max_size
  • 修改器
  • • clear
    • insert
    • emplace
    • emplace_hint
    • erase
    • swap
    • extract
    • merge
  • 查找
  • • count
    • find
    • contains
    • equal_range
    • lower_bound
    • upper_bound
  • 觀察器
  • • key_comp
    • value_comp
  • 非成員函數
  • • operator==
    • std::swap(std::multimap)
    • erase_if(std::multimap)

概述

• 定義于頭檔案<map>
• std::multimap 是有序鍵值對容器，它的元素的鍵是唯一的。用比較函數 Compare 排序鍵。搜尋、移除和插入操作擁有對數複雜度。 multimap 通常實作為紅黑樹。

類模闆：

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class multimap;
           

建立multimap

構造函數

定義：

// 1、預設構造函數
multimap();	

// 2、範圍構造函數。構造擁有範圍 [first, last) 内容的容器。若範圍中的多個元素擁有比較等價的關鍵，則插入哪個元素是未指定的								
template< class InputIt >
multimap( InputIt first, InputIt last,
     const Compare& comp = Compare(),
     const Allocator& alloc = Allocator() );

// 3、複制構造函數
multimap( const multimap& other );				

// 4、移動構造函數
multimap( multimap&& other );				 		

// 5、initializer_multimap init 構造函數
multimap( std::initializer_list<value_type> init,
     const Compare& comp = Compare(),
     const Allocator& alloc = Allocator() );
           

用法：

#include <iostream>
#include <string>
#include <iomanip>
#include <multimap>
 
template<typename Multimap>
void print_multimap(Multimap& m)
{
   std::cout << '{';
   for(auto& p: m)
        std::cout << p.first << ':' << p.second << ' ';
   std::cout << "}\n";
}
 
struct Point { double x, y; };
struct PointCmp {
    bool operator()(const Point& lhs, const Point& rhs) const { 
        return lhs.x < rhs.x; // NB 。有意忽略 y
    }
};
 
int main()
{
  // (1) 預設構造函數
  std::multimap<std::string, int> multimap1;
  multimap1["something"] = 69;
  multimap1["anything"] = 199;
  multimap1["that thing"] = 50;
  std::cout << "multimap1 = "; print_multimap(multimap1);
 
  // (2) 範圍構造函數
  std::multimap<std::string, int> iter(multimap1.find("anything"), multimap1.end());
  std::cout << "\niter = "; print_multimap(iter);
  std::cout << "multimap1 = "; print_multimap(multimap1);
 
  // (3) 複制構造函數
  std::multimap<std::string, int> copied(multimap1);
  std::cout << "\ncopied = "; print_multimap(copied);
  std::cout << "multimap1 = "; print_multimap(multimap1);
 
  // (4) 移動構造函數
  std::multimap<std::string, int> moved(std::move(multimap1));
  std::cout << "\nmoved = "; print_multimap(moved);
  std::cout << "multimap1 = "; print_multimap(multimap1);
 
  // (5) initializer_list 構造函數
  const std::multimap<std::string, int> init {
    {"this", 100},
    {"can", 100},
    {"be", 100},
    {"const", 100},
  };
  std::cout << "\ninit = "; print_multimap(init);
 
 
  // 定制關鍵類選項 1 ：
  // 使用比較 struct
  std::multimap<Point, double, PointCmp> mag = {
      { {5, -12}, 13 },
      { {3, 4},   5 },
      { {-8, -15}, 17 }
  };
 
  for(auto p : mag)
      std::cout << "The magnitude of (" << p.first.x
                << ", " << p.first.y << ") is "
                << p.second << '\n';
 
  // 定制關鍵類選項 2 ：
  // 使用比較 lambda
  // 此 lambda 按照其模比較點，注意其中模取自局部變量 mag
  auto cmpLambda = [&mag](const Point &lhs, const Point &rhs) { return mag[lhs] < mag[rhs]; };
  // 你亦可使用不依賴局部變量的 lambda ，像這樣：
  // auto cmpLambda = [](const Point &lhs, const Point &rhs) { return lhs.y < rhs.y; };
  std::multimap<Point, double, decltype(cmpLambda)> magy(cmpLambda);
 
  // 各種插入元素的方式：
  magy.insert(std::pair<Point, double>({5, -12}, 13));
  magy.insert({ {3, 4}, 5});
  magy.insert({Point{-8.0, -15.0}, 17});
 
  std::cout << '\n';
  for(auto p : magy)
      std::cout << "The magnitude of (" << p.first.x
                << ", " << p.first.y << ") is "
                << p.second << '\n';
}

// 輸出
// multimap1 = {anything:199 something:69 that thing:50 }
 
// iter = {anything:199 something:69 that thing:50 }
// multimap1 = {anything:199 something:69 that thing:50 }
 
// copied = {anything:199 something:69 that thing:50 }
// multimap1 = {anything:199 something:69 that thing:50 }
 
// moved = {anything:199 something:69 that thing:50 }
// multimap1 = {}
 
// init = {be:100 can:100 const:100 this:100 }
// The magnitude of (-8, -15) is 17
// The magnitude of (3, 4) is 5
// The magnitude of (5, -12) is 13
 
// The magnitude of (3, 4) is 5
// The magnitude of (5, -12) is 13
// The magnitude of (-8, -15) is 17
           

opertor=

• 指派給容器

  定義：

multimap& operator=( const multimap& other );	// 複制指派運算符。
multimap& operator=( multimap&& other );	// 移動指派運算符。
multimap& operator=( std::initializer_multimap<T> imultimap ); // 以 initializer_multimap imultimap 所辨別者替換内容。
           

用法：

std::multimap<int, int> nums1 {{3, 1}, {4, 1}, {5, 9}, 
                              {6, 1}, {7, 1}, {8, 9}};
    std::multimap<int, int> nums2; 
    std::multimap<int, int> nums3;

    // 從 nums1 複制指派資料到 nums2
    nums2 = nums1;
    // 從 nums1 移動指派資料到 nums3,
    nums3 = std::move(nums1);
    // initializer_multimap 的複制指派複制資料給 nums1
    nums1 = {{3, 1}, {4, 1}, {5, 9}};
           

元素通路

at

• 通路指定的元素，同時進行越界檢查

T& at( const Key& key );

const T& at( const Key& key ) const;
           

• 參數：key - 要找到的元素的鍵
• 傳回值：value，鍵對應的值

operator[ ]

• 通路或插入指定的元素

定義：

T& operator[]( const Key& key );

T& operator[]( Key&& key );
           

用法：

#include <iostream>
#include <string>
#include <vector>
#include <multimap>
 
int main()
{
    std::multimap<char, int> letter_counts {{'a', 27}, {'b', 3}, {'c', 1}};
 
    std::cout << "initially:\n";
    for (const auto &pair : letter_counts) {
        std::cout << pair.first << ": " << pair.second << '\n';
    }
 
    letter_counts['b'] = 42;  // 更新既存值
    letter_counts['x'] = 9;  // 插入新值
 
    std::cout << "after modifications:\n";
    for (const auto &pair : letter_counts) {
        std::cout << pair.first << ": " << pair.second << '\n';
    }
 
    // 統計每個詞的出現數
    // （首次調用 operator[] 以零初始化計數器）
    std::multimap<std::string, size_t>  word_multimap;
    for (const auto &w : { "this", "sentence", "is", "not", "a", "sentence",
                           "this", "sentence", "is", "a", "hoax"}) {
        ++word_multimap[w];
    }
 
    for (const auto &pair : word_multimap) {
        std::cout << pair.second << " occurrences of word '" << pair.first << "'\n";
    }
}

// 輸出
initially:
a: 27
b: 3
c: 1
after modifications:
a: 27
b: 42
c: 1
x: 9
2 occurrences of word 'a'
1 occurrences of word 'hoax'
2 occurrences of word 'is'
1 occurrences of word 'not'
3 occurrences of word 'sentence'
2 occurrences of word 'this'
           

疊代器

begin\cbegin

• 傳回指向 multimap 首元素的疊代器。
• cbegin中的c表示const，即傳回const_iterator，不允許通過疊代器修改元素。
• 若 multimap 為空，則傳回的疊代器将等于 end() 。

定義：

iterator begin();
const_iterator cbegin() const noexcept;
           

用法：

#include <iostream>
#include <multimap>
 
int main() {
  std::multimap<int, float> num_multimap;
  num_multimap[4] = 4.13;
  num_multimap[9] = 9.24;
  num_multimap[1] = 1.09;
  // 調用 a_multimap.begin() 與 a_multimap.end()
  for (auto it = num_multimap.begin(); it != num_multimap.end(); ++it) {
    std::cout << it->first << ", " << it->second << '\n';
  }
}

// 輸出
// 1, 1.09
// 4, 4.13
// 9, 9.24
           

end\cend

• 傳回指向 multimap 末元素後一進制素的疊代器。

定義：

iterator end();
const_iterator cend() const noexcept;
           

rbegin\crbegin

• 傳回指向逆向 multimap 首元素的逆向疊代器。
• 它對應非逆向 multimap 的末元素。若 multimap 為空，則傳回的疊代器等于 rend() 。

定義：

reverse_iterator rbegin();
const_reverse_iterator crbegin() const noexcept;
           

rend\crend

• 傳回指向逆向 multimap 末元素後一進制素的逆向疊代器。
• 它對應非逆向 multimap 首元素的前一進制素。此元素表現為占位符，試圖通路它導緻未定義行為。

定義：

reverse_iterator rend();
const_reverse_iterator crend() const noexcept;
           

容量

empty

• 檢查容器是否無元素，即是否 begin() == end() 。

定義：

用法：

multimap<int, int> v;
	bool flag = v.empty();	// 輸出 true
           

size

• 傳回容納的元素數。 即 std::distance(begin(), end()) 。

定義：

用法：

std::multimap<int,char> nums {{1, 'a'}, {3, 'b'}, {5, 'c'}, {7, 'd'}};
    std::cout << nums.size() << std::endl;	// 輸出 4
           

max_size

• 傳回根據系統或庫實作限制的容器可保有的元素最大數量，即對于最大容器的 std::distance(begin(), end()) 。

定義：

用法：

std::multimap<int, int> vi;
	std::cout << vi.max_size() << std::endl;	// 可能輸出 4611686018427387903
	std::multimap<char, cahr> vc;
	std::cout << vc.max_size() << std::endl;	// 可能輸出 18446744073709551615
           

修改器

clear

• 從容器擦除所有元素。此調用後 size() 傳回零。
• 非法化任何指代所含元素的引用、指針或疊代器。任何尾後疊代器亦被非法化。

定義：

用法：

std::multimap<int, char> container{{1, 'a'}, {3, 'b'}, {5, 'c'}};
	container.clear();
	std::cout << container.size() << std::endl;		// 輸出 0
           

insert

• 插入元素或結點

定義：

std::pair<iterator,bool> insert( const value_type& value );

std::pair<iterator,bool> insert( value_type&& value );

template< class InputIt >
void insert( InputIt first, InputIt last );

void insert( std::initializer_list<value_type> ilist );
           

用法：

std::multimap<int, char> a;
 	
 	a.insert({1, 'a'});

	std::multimap<int, char> b { {3, 'b'}, {5, 'c'}};
	a.insert(b.begin(), b.end());
	
 	a.insert({7, 'd'}, {9, 'e'});

           

emplace

  原位構造元素

定義：

template< class... Args >
std::pair<iterator,bool> emplace( Args&&... args );;
           

emplace_hint

• 使用提示原位構造元素

• 傳回值

    傳回指向新插入元素的疊代器。

    若因元素已存在而插入失敗，則傳回指向擁有等價關鍵的既存元素的疊代器。

定義：

template <class... Args>
iterator emplace_hint( const_iterator hint, Args&&... args );
           

erase

• 從容器擦除指定的元素。

定義：

// 1、移除位于 pos 的元素。
iterator erase( iterator pos );

// 2、移除範圍 [first; last) 中的元素。
iterator erase( iterator first, iterator last );

// 3、移除關鍵等于 key 的元素（若存在一個）。
size_type erase( const key_type& key )
           

用法：

std::multimap<int, char> c = {{3, 'b'}, {4, 'c'}, {2, 'b'}, {5, 'c'}};
    // 從 c 擦除所有奇數
    for(auto it = c.begin(); it != c.end(); )
        if(it->first % 2 == 1)
            it = c.erase(it);
        else
            ++it;
     // c : 2 4 6 8
           

swap

• 交換内容

定義：

用法：

std::multimap<int, char> a1{{3, 'b'}}, a2{{4, 'c'}, {2, 'b'}};
	a1.swap(a2);
           

extract

• 從另一容器釋出結點 C++17

定義：

// 解鍊含 position 所指向元素的結點并傳回占有它的結點柄。
node_type extract( const_iterator position );

// 若容器擁有元素而其關鍵等于 x ，則從容器解鍊該元素并傳回占有它的結點柄。否則，傳回空結點柄。
node_type extract( const key_type& x );
           

merge

• 從另一容器接合結點 C++17

定義：

template<class C2>
void merge( std::multimap<Key, C2, Allocator>& source );

template<class C2>
void merge( std::multimap<Key, C2, Allocator>&& source );
           

用法：

std::multimap<int, std::string> ma {{1, "apple"}, {5, "pear"}, {10, "banana"}};
  	std::multimap<int, std::string> mb {{2, "zorro"}, {4, "batman"}, {5, "X"}, {8, "alpaca"}};
  	std::multimap<int, std::string> u;
 	 u.merge(ma);
  	std::cout << "ma.size(): " << ma.size() << '\n';
  	u.merge(mb);
  	std::cout << "mb.size(): " << mb.size() << '\n';
  	std::cout << "mb.at(5): " << mb.at(5) << '\n';
  	for(auto const &kv: u)
    	std::cout << kv.first << ", " << kv.second << '\n';

// 輸出
ma.size(): 0
mb.size(): 1
mb.at(5): X
1, apple
2, zorro
4, batman
5, pear
8, alpaca
10, banana
           

查找

count

• 傳回比對特定鍵的元素數量
• 傳回擁有關鍵比較等價于指定參數的元素數，因為此容器不允許重複故為 1 或 0。

定義：

find

• 尋找帶有特定鍵的元素

• 傳回值

    指向鍵等于 key 的元素的疊代器。若找不到這種元素，則傳回尾後（見 end() ）疊代器。

定義：

iterator find( const Key& key );
const_iterator find( const Key& key ) const;
           

用法：

std::multimap<int,char> example = {{1,'a'},{2,'b'}};
 
    auto search = example.find(2);
    if (search != example.end()) {
        std::cout << "Found " << (*search) << '\n';
    } else {
        std::cout << "Not found\n";
    }
           

contains

• 檢查容器中是否有鍵等價于 key 的元素
• 若有這種元素則傳回 true ，否則傳回 false

定義：

bool contains( const Key& key ) const;

template< class K > bool contains( const K& x ) const;
           

用法：

std::multimap<int,char> example = {{1,'a'},{2,'b'}};
 
    for(int x: {2, 5}) {
        if(example.contains(x)) {
            std::cout << x << ": Found\n";
        } else {
            std::cout << x << ": Not found\n";
        }
    }
           

equal_range

• 傳回比對特定鍵的元素範圍
• 範圍以二個疊代器定義，一個指向首個不小于 key 的元素，另一個指向首個大于 key 的元素。首個疊代器可以換用 lower_bound() 獲得，而第二疊代器可換用 upper_bound() 獲得。
• 傳回值： 含一對定義所需範圍的疊代器的 std::pair ：第一個指向首個不小于 key 的元素，第二個指向首個大于 key 的元素。

若無元素不小于 key ，則将尾後（見 end() ）疊代器作為第一進制素傳回。類似地，若無元素大于 key ，則将尾後疊代器作為第二進制素傳回。

定義：

lower_bound

• 傳回指向首個不小于給定鍵的元素的疊代器
• 指向首個不小于 key 的元素的疊代器。若找不到這種元素，則傳回尾後疊代器。

定義：

用法見upper_bound。

upper_bound

• 傳回指向首個大于給定鍵的元素的疊代器
• 指向首個大于 key 的元素的疊代器。若找不到這種元素，則傳回尾後（見 end() ）疊代器。

定義：

用法：

std::multimap<int, char> a {{1,'a'},{2,'b'}, {3,'c'}, {4,'d'}};
	std::cout << a.lower_bound(3)->second << std::endl;	// 3
	std::cout << a.upper_bound(3) << std::endl;	// 4
           

觀察器

key_comp

• 傳回用于比較鍵的函數
• 它是此容器構造函數參數 comp 的副本，它與 value_comp 相同。

value_comp

• 傳回比較 std::multimap::value_type （關鍵-值 pair ）對象的函數對象，它用 key_comp 比較 pair 的第一組分。

• 傳回值

    比較值的函數對象。

非成員函數

operator==

• 按照字典順序比較 multimap 中的值

定義：

template< class Key, class Compare, class Alloc >
bool operator==( const std::multimap<Key,Compare,Alloc>& lhs,
                 const std::multimap<Key,Compare,Alloc>& rhs );
           

用法：

std::multimap<int, char> alice{{1, 'a'}, {2, 'b'}, {3, 'c'}};
    std::multimap<int, char> bob{{7, 'Z'}, {8, 'Y'}, {9, 'X'}, {10, 'W'}};
    std::multimap<int, char> eve{{1, 'a'}, {2, 'b'}, {3, 'c'}};
 
	// 比較不相等的容器
	std::cout << "alice == bob returns " << (alice == bob) << std::endl;	//輸出 false
	// 比較相等的容器
	std::cout << "alice == eve returns " << (alice == eve) << std::endl;	//輸出 true
           

std::swap(std::multimap)

• 為 std::multimap 特化 std::swap 算法。交換 lhs 與 rhs 的内容。調用 lhs.swap(rhs) 。

定義：

template< class Key, class Compare, class Alloc >
void swap( std::multimap<Key,Compare,Alloc>& lhs,
           std::multimap<Key,Compare,Alloc>& rhs );
           

用法：

std::multimap<int, char> alice{{1, 'a'}, {2, 'b'}, {3, 'c'}};
    std::multimap<int, char> bob{{7, 'Z'}, {8, 'Y'}, {9, 'X'}, {10, 'W'}};
	//交換容器
	std::swap(alice,bob);
           

erase_if(std::multimap)

• 擦除所有滿足特定判别标準的元素(C++ 20)

定義：

template< class Key, class Compare, class Alloc, class Pred >
typename std::multimap<Key,Compare,Alloc>::size_type
    erase_if(std::multimap<Key,Compare,Alloc>& c, Pred pred);
           

用法：

std::multimap<int, char> data {{1, 'a'},{2, 'b'},{3, 'c'},{4, 'd'},
                              {5, 'e'},{4, 'f'},{5, 'g'},{5, 'g'}};
    std::cout << "Original:\n" << data << '\n';
 
    const auto count = std::erase_if(data, [](const auto& item) {
        auto const& [key, value] = item;
        return (key & 1) == 1;
    });
    // {{2, b}{4, d}}