C++ Set

前言：这是一篇翻译的文章。在这篇文章中我们将看到如何用默认排序标准使用 std::set

Introduction

std :: set 是一个 associative container 和 header，使用的时候需要包含 #include<set>

Benefits and Features of std::set

  • 它不允许重复元素，即它只包含唯一元素。
  • Std :: set 使用模板参数，可以包含模任何指定类型的元素，即
std::set<int> // contains only int elements.
class Sample;
std::set<Sample> // contains only Sample class objects.

  • std :: set 内部用平衡二叉树存储元素。

  • 默认情况下，std :: set 使用 operator < 来比较两个元素，但是如果程序员自定义排序标准，即 comparator，那么它使用 comparator 而不是默认运算符 <

  • std :: set 将根据指定的排序标准（即默认条件运算符 < 或通过传递 comparator）保留插入的元素。

举个栗子

#include<iostream>
#include<set>
#include<string>
int main()
{
std::set<std::string> setOfNumbers;
// Lets insert four elements
setOfNumbers.insert("first");
setOfNumbers.insert("second");
setOfNumbers.insert("third");
setOfNumbers.insert("first");
// Only 3 elements will be inserted
std::cout<<"Set Size = "<<setOfNumbers.size()<<std::endl;
// Iterate through all the elements in a set and display the value.
for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
std::cout << ' ' << *it;
std::cout<<"\n";
return 0;
}

输出：

Set Size = 3
first second third

上面示例中的 setOfNumbers.size() 返回 3，因为 std::set 仅包含唯一元素，因此字符串“first”仅在集合中添加一次而再次调用 "first" 的时候被拒绝。

它使用运算符 < 进行比较，并按排序顺序保留所有元素，在上面的输出中，您可以检查所有字符串是否按排序顺序排列。

for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
std::cout << ' ' << *it;

但是你不能使用迭代器修改元素，因为如果你修改了元素值，那么std::set 的内部数据结构将会被破坏，它将不会保持平衡的二进制搜索树。因此，以后的添加和查找操作将无法正常工作。

How to search an element in std::set:

使用成员函数：

iterator find (const value_type& val) const;

它在容器中搜索与 val 相等的元素，如果找到则返回 iterator，否则返回 set::end 的 iterator。

举个栗子

#include<iostream>
#include<set>
#include<string>
int main()
{
std::set<std::string> setOfNumbers;
// Lets insert four elements
setOfNumbers.insert("first");
setOfNumbers.insert("second");
setOfNumbers.insert("third");
setOfNumbers.insert("first");
// Search for element in set using find member function
std::set<std::string>::iterator it = setOfNumbers.find("second");
if(it != setOfNumbers.end())
std::cout<<"'first'  found"<<std::endl;
else
std::cout<<"'first' not found"<<std::endl;
// Search for element in set using find member function
it = setOfNumbers.find("fourth");
if(it != setOfNumbers.end())
std::cout<<"'fourth'  found"<<std::endl;
else
std::cout<<"'fourth' not found"<<std::endl;
return 0;
}

输出：

‘first’ found
‘fourth’ not found

Why should we use std::set::find member method instead of std::find standard generic algorithm?

因为查找成员函数知道它的内部数据结构是平衡二进制搜索树，因此设计的查找操作会更快

How std::set verifies while insertion if element is already added or not

它在内部维护二进制平衡树，并在插入期间将新元素与已存在的节点进行比较，并在树中找到新元素的正确位置。如果该元素已经存在，那么它不会插入新元素。

但等一下，如果它使用运算符 < 用于两个元素的比较，那么它如何用运算符 < 检查两个元素是否相等？

它使用以下逻辑来检查 a 和 b 这两个元素是否相等，

如果 a < b 是 false，b < a 也是 false。那么意味着两者相等

验证 std::set 中插入的示例，

#include<iostream>
#include<set>
std::set<int> setOfNumbers;
void checkAndInsert(int num)
{
if(setOfNumbers.insert(num).second)
std::cout<<"Number "<<num<<" inserted sucessfuly\n";
else
std::cout<<"Number "<<num<<" was already present in set\n";
}
int main()
{
checkAndInsert(2);
checkAndInsert(3);
checkAndInsert(2);
checkAndInsert(1);
// Check the size of set
std::cout<<setOfNumbers.size()<<std::endl;
// Iterate through all the elements in a set and display the value.
for (std::set<int>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
std::cout << ' ' << *it;
std::cout<<"\n";
return 0;
}

输出：

Number 2 inserted sucessfuly
Number 3 inserted sucessfuly
Number 2 was already present in set
Number 1 inserted sucessfuly
3
1 2 3

How to remove an element in std::set

使用成员函数擦除，即

擦除成员函数有三个重载版本，

iterator  erase (const_iterator position);
size_type erase (const value_type& val);
iterator  erase (const_iterator first, const_iterator last);

举个栗子

#include<iostream>
#include<set>
#include<string>
int main()
{
std::set<std::string> setOfNumbers;
// Lets insert four elements
setOfNumbers.insert("first");
setOfNumbers.insert("second");
setOfNumbers.insert("third");
setOfNumbers.insert("first");
// Iterate through all the elements in a set and display the value.
for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
std::cout << ' ' << *it;
std::cout<<std::endl;
setOfNumbers.erase("third");
// Iterate through all the elements in a set and display the value.
for (std::set<std::string>::iterator it=setOfNumbers.begin(); it!=setOfNumbers.end(); ++it)
std::cout << ' ' << *it;
std::cout<<std::endl;
return 0;
}

输出：

first second third
first second

相关文章

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容