C++ 关联性容器
|
333
|
0
|
Linux C / C++

2393 字
|
23 分钟

std::set

std::set 的构造

std::set 是 C++ 标准库中的一个关联式容器，它根据元素值自动排序，并确保容器中每个元素的唯一性。

  1. 默认构造： 创建一个空的 std:: set。 
    std::set<Key, Compare, Allocator> set1;
  2. 复制构造： 使用另一个 std:: set 的内容、比较函数和分配器来构造新的 std:: set。 
    std::set<Key, Compare, Allocator> set1;
std::set<Key, Compare, Allocator> set2(set1);
  3. 移动构造： 使用另一个 std:: set 的内容来构造新的 std:: set，原 std:: set 将变为空。 
    std::set<Key, Compare, Allocator> set1;
std::set<Key, Compare, Allocator> set3(std::move(set1));
  4. 初始化列表构造： 使用初始化列表来构造 std:: set。 
    std::set<Key, Compare, Allocator> set = {key1, key2, key3};
  5. 范围构造（C++23）： 使用给定范围的元素来构造 std:: set。 
    std::initializer_list<Key> init_list = {key1, key2, key3};
std::set<Key, Compare, Allocator> set(init_list);
  6. 按范围构造（C++23）： 使用给定迭代器范围的元素来构造 std:: set。 
    Key arr[] = {key1, key2, key3};
std::set<Key, Compare, Allocator> set(std::begin(arr), std::end(arr));

参数说明

  • Key：存储在 std:: set 中的元素类型。
  • Compare（可选）：用于比较元素的函数对象，它接受两个参数并返回一个布尔值，指示第一个参数是否被认为小于第二个参数。默认情况下，使用 std:: less 。
  • Allocator（可选）：用于管理内存分配和释放的分配器类型。默认情况下，使用 std:: allocator 。

std::set 的特征：

  1. 元素唯一性：std::set 中的每个元素值必须是唯一的，不允许重复。
  2. 自动排序：std::set 默认会根据元素的值进行升序排序。

遍历 std::set：

std::set 内部实现为二叉搜索树，可以通过以下方式遍历：

  1. 迭代器遍历：使用迭代器遍历 std::set 中的每个元素。
  2. 范围 for 循环：使用 C++11 的范围 for 循环遍历 std::set。
for (auto &ele : set) {
  cout << ele << " ";
}

auto it = set.begin();
for(; it != set.end(); ++it) {
  cout << *it << " ";
}

std::set 的查找操作

count 操作

count 函数用来检查某个值是否存在于 std::set 中。如果值存在，则返回 1；如果不存在，则返回 0。

示例代码：

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers = {1, 3, 5, 7, 9};

  if (numbers.count(5) > 0) {
    std::cout << "Number 5 is in the set." << std::endl;
  } else {
    std::cout << "Number 5 is not in the set." << std::endl;
  }

  if (numbers.count(6) > 0) {
    std::cout << "Number 6 is in the set." << std::endl;
  } else {
    std::cout << "Number 6 is not in the set." << std::endl;
  }

  return 0;
}

find 操作

find 函数用来在 std::set 中查找一个值。如果找到了，函数返回一个指向该元素的迭代器；如果没找到，则返回一个等于 end() 的迭代器。

示例代码：

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers = {1, 3, 5, 7, 9};

  auto it = numbers.find(5);
  if (it != numbers.end()) {
    std::cout << "Number 5 found in the set." << std::endl;
  } else {
    std::cout << "Number 5 not found in the set." << std::endl;
  }

  it = numbers.find(6);
  if (it != numbers.end()) {
    std::cout << "Number 6 found in the set." << std::endl;
  } else {
    std::cout << "Number 6 not found in the set." << std::endl;
  }

  return 0;
}

std::set 的插入操作

std::set 是一个关联容器，它存储的元素是唯一的，并且是自动排序的。以下是 std::set 的几种插入操作：

插入单个元素

插入单个元素时，可以使用 insert 函数。该函数的返回类型是一个 pair，包含一个迭代器和一个 bool 值。

  • 迭代器：指向插入元素的迭代器，如果插入失败（元素已存在），则迭代器指向已存在的元素。
  • bool 值：true 表示插入成功，false 表示插入失败（元素已存在）。

示例代码：

#include <iostream>
#include <set>

int main() {
  std::set<int> number;
  std::pair<std::set<int>::iterator, bool> ret = number.insert(8);

  if (ret.second) {
    std::cout << "该元素插入成功:" << *(ret.first) << std::endl;
  } else {
    std::cout << "该元素插入失败，表明该元素已存在" << std::endl;
  }

  return 0;
}

插入多个元素

  1. 使用迭代器范围插入：传入一对迭代器，指定要插入元素的范围。

  2. 使用初始化列表插入：使用花括号 {} 指定要插入的元素列表。

示例代码：

#include <iostream>
#include <set>

int main() {
  std::set<int> number;
  int arr[5] = {18, 41, 35, 2, 99};

  // 插入数组中的元素
  number.insert(arr, arr + 5); // 注意：arr + 5 是正确的，因为它指向数组末尾的下一个位置

  for (const auto &value : number) {
    std::cout << value << " ";
  }
  std::cout << std::endl;

  return 0;
}

注意事项

  1. std::set 不支持下标访问：因为 std::set 没有 operator[] 重载函数，所以不能使用下标访问元素。

  2. 不能通过迭代器直接修改键值：std::set 的底层实现是红黑树，结构稳定，元素的键值不能通过迭代器直接修改。

std::map 的构造和遍历

std::map 是 C++ 标准库中的一个关联容器，它存储的元素是键值对（pair 类型），并且按键值自动排序。

std::map 的构造函数

  1. 默认构造： 创建一个空的 std::map。 
    std::map<Key, T, Compare, Allocator> map;
  2. 复制构造： 使用另一个 std::map 的内容、比较函数和分配器来构造新的 std::map。 
    std::map<Key, T, Compare, Allocator> map1;
map1["key1"] = "value1";
std::map<Key, T, Compare, Allocator> map2(map1);
  3. 移动构造： 使用另一个 std::map 的内容来构造新的 std::map，原 std::map 将变为空。 
    std::map<Key, T, Compare, Allocator> map1;
map1["key1"] = "value1";
std::map<Key, T, Compare, Allocator> map2(std::move(map1));
  4. 初始化列表构造： 使用初始化列表来构造 std::map。 
    std::map<Key, T, Compare, Allocator> map = {{"key1", "value1"}, {"key2", "value2"}};
  5. 范围构造（C++11 及之后）： 使用给定迭代器范围的元素来构造 std::map。 
    std::pair<const Key, T> arr[] = {{"key1", "value1"}, {"key2", "value2"}};
std::map<Key, T, Compare, Allocator> map(std::begin(arr), std::end(arr));
  6. 按范围构造（C++23）： 使用给定迭代器范围的元素来构造 std::map。 
    std::pair<const Key, T> arr[] = {{"key1", "value1"}, {"key2", "value2"}};
std::map<Key, T, Compare, Allocator> map(std::begin(arr), std::end(arr));

参数说明：

  • Key：存储在 std::map 中的键的类型。
  • T：存储在 std::map 中的值的类型。
  • Compare（可选）：用于比较键的函数对象，它接受两个参数并返回一个布尔值，指示第一个参数是否被认为小于第二个参数。默认情况下，使用 std::less<Key>。
  • Allocator（可选）：用于管理内存分配和释放的分配器类型。默认情况下，使用 std::allocator<std::pair<const Key, T>>。

std::map 的特征：

  1. 元素唯一性：std::map 中的每个键值必须是唯一的。如果插入了具有相同键值的元素，那么新元素的值不会替换现有元素的值，但新元素可能会覆盖老元素（取决于具体的插入操作和元素的比较函数）。
  2. 按键值排序：std::map 默认按键值进行升序排序。

注意事项：

  • std::map 不支持下标访问，因为它没有 operator[] 重载函数。
  • 可以通过 first 和 second 成员访问 std::pair 的内容。
  • 可以使用 insert 成员函数插入单个键值对，或者使用 emplace 函数就地构造键值对。

std::map 的查找操作

使用 count 函数

count 函数用于检查是否存在与给定键相等的元素。它的返回值是一个 size_type 类型，如果找到元素则返回 1，如果没有找到则返回 0。

语法:

size_type count(const Key& key) const;

示例:

#include <map>
#include <iostream>

int main() {
  std::map<int, std::string> myMap;
  myMap[1] = "apple";
  myMap[2] = "banana";

  if (myMap.count(1) > 0) {
    std::cout << "Key 1 exists.\n";
  } else {
    std::cout << "Key 1 does not exist.\n";
  }

  if (myMap.count(3) > 0) {
    std::cout << "Key 3 exists.\n";
  } else {
    std::cout << "Key 3 does not exist.\n";
  }

  return 0;
}

使用 find 函数

find 函数用于查找具有特定键的元素。如果找到，它返回一个指向该元素的迭代器；如果没有找到，则返回一个指向 end() 的迭代器。

语法:

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

示例:

#include <map>
#include <iostream>

int main() {
  std::map<int, std::string> myMap;
  myMap[1] = "apple";
  myMap[2] = "banana";

  auto it = myMap.find(1);
  if (it != myMap.end()) {
    std::cout << "Found key 1: " << it->second << "\n";
  } else {
    std::cout << "Key 1 not found.\n";
  }

  it = myMap.find(3);
  if (it == myMap.end()) {
    std::cout << "Key 3 not found.\n";
  }

  return 0;
}

使用 [] 操作符

虽然 [] 操作符不是查找操作，但它可以用来访问具有特定键的元素。如果元素不存在，它将创建一个新元素并初始化其值。

示例:

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "apple";

    std::cout << myMap[1] << std::endl;  // Outputs: apple
    std::cout << myMap[2] << std::endl;  // Creates a new element with key 2 and default value (empty string)

    return 0;
}

使用 at 函数

at 函数用于安全地访问具有特定键的元素。如果元素不存在，它会抛出一个 std::out_of_range 异常。

语法:

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

示例:

#include <map>
#include <iostream>
#include <stdexcept>  // For std::out_of_range

int main() {
  std::map<int, std::string> myMap;
  myMap[1] = "apple";

  try {
    std::cout << myMap.at(1) << std::endl;  // Outputs: apple
    std::cout << myMap.at(2) << std::endl;  // Throws std::out_of_range
  } catch (const std::out_of_range& e) {
    std::cout << "Exception: " << e.what() << std::endl;
  }

  return 0;
}

std::map 的插入操作

插入单个元素

使用 insert 成员函数可以插入单个元素。这个函数的返回值是一个 std::pair，其中第一个元素是指向插入元素的迭代器，第二个元素是一个布尔值，表示插入是否成功（如果元素已存在，则插入失败）。

语法:

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

示例:

#include <map>
#include <iostream>
#include <string>

int main() {
  std::map<int, std::string> number;
  std::pair<std::map<int, std::string>::iterator, bool> ret = number.insert(std::make_pair(7, "nanjing"));

  if (ret.second) {
    std::cout << "该元素插入成功" << std::endl;
    // ret.first 取出来的是指向 map 元素（pair<int, string>）的迭代器
    // 再用箭头运算符访问到的是 int 和 string 的内容
    std::cout << ret.first->first << " : " << ret.first->second << std::endl;
  } else {
    std::cout << "该元素插入失败" << std::endl;
  }
  std::cout << std::endl;

  return 0;
}

插入一组元素

可以使用 insert 成员函数插入多个元素。这可以通过迭代器范围或初始化列表来完成。

语法:

void insert(InputIterator first, InputIterator last);
void insert(std::initializer_list<value_type> ilist);

示例:

#include <map>
#include <iostream>
#include <string>

int main() {
  std::map<int, std::string> number = {{1, "beijing"}, {2, "shanghai"}};
  std::map<int, std::string> number2;

  // 迭代器方式
  number2.insert(number.begin(), number.end());

  // 列表方式
  std::cout << std::endl;
  number2.insert({{4, "guangzhou"}, {22, "hello"}});

  for (const auto& pair : number2) {
    std::cout << pair.first << " : " << pair.second << std::endl;
  }

  return 0;
}

使用 emplace 函数

emplace 函数用于就地构造元素，避免额外的复制或移动操作。

语法:

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

示例:

#include <map>
#include <iostream>
#include <string>

int main() {
  std::map<int, std::string> number;
  auto ret = number.emplace(7, "nanjing");

  if (ret.second) {
    std::cout << "该元素插入成功" << std::endl;
    std::cout << ret.first->first << " : " << ret.first->second << std::endl;
  } else {
    std::cout << "该元素插入失败" << std::endl;
  }
  std::cout << std::endl;

  return 0;
}

std::map 的下标操作

  1. 返回值： operator[] 返回对 std::map 中元素的引用，该元素是一个 std::pair，其中包含 key 和 value。
  2. 下标值代表键：在 std::map 中使用下标操作符时，提供的下标值实际上是键（key），而不是传统数组或向量中的索引。
  3. 插入新元素：如果键不存在于 std::map 中，operator[] 会插入一个新的键值对，其中键是下标操作符的参数，值是该值类型的默认值。
  4. 写操作：operator[] 允许对值进行写操作，即使键原本不存在于 std::map 中。这不会影响 std::map 的排序，因为排序只与键相关。
#include <map>
#include <iostream>
#include <string>

int main() {
  std::map<int, std::string> myMap;

  // 访问已存在的键
  myMap[1] = "apple";

  // 访问不存在的键，插入新元素
  myMap[2] = "banana";

  // 修改已存在的元素
  myMap[1] = "green apple";

  // 访问新插入的元素
  std::cout << "Key 1: " << myMap[1] << std::endl; // 输出 "Key 1: green apple"
  std::cout << "Key 2: " << myMap[2] << std::endl; // 输出 "Key 2: banana"

  // 访问不存在的键，插入新元素，键为3，默认值为空字符串
  std::cout << "Key 3: " << myMap[3] << std::endl; // 输出 "Key 3: "（默认值）

  return 0;
}

元素类型：std::map 的元素是 std::pair，其中第一个元素是键（key_type），第二个元素是值（value_type）。键的类型必须支持比较操作以确保元素可以被排序。

注意事项：

  • 使用 operator[] 时，如果键不存在，则会创建一个新的元素。这可能会导致不必要的性能开销，特别是在遍历键值时。
  • 如果需要检查键是否存在，应使用 find 方法或 count 方法，而不是直接使用 operator[]。
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇