STL 101 第 D 部分 - 排序关联容器，Set 和 Map

• 下载演示项目 - 83.7 Kb
• 下载源代码 - 6.28 Kb

引言

欢迎来到我的 STL 系列的第四部分。这次我想看看两个名为 set 和 map 的容器。我将先解释 set，然后看看 map 能带来什么。

创建 set

据我所知，所有 STL 实现都将这两个容器实现为二叉树。因此，push_back/pop_back 范例在这里不起作用 - 项目是按顺序插入的，所以您无法指定位置。相反，我们使用 insert 方法，该方法可以选择性地接受一个位置。这是对 STL 的一个建议，告诉它从哪里开始查找插入位置，如果正在构建一个大型 set，这显然可以极大地提高速度。要从 set 中删除项目，我们需要使用 find 算法并将返回的迭代器传递给 erase 函数。每当使用 find 算法时，都应该检查返回值是否等于 end()，以防找不到该项目。

set<STRING> setString; 
setString.insert("this"); 
setString.insert("is"); 
setString.insert("a"); 
setString.insert("test"); 
setString.insert("boys"); 
cout << "setString" << endl << endl; 

set<STRING>::iterator it = setString.begin(); 

while(it != setString.end()) 
{
    cout << *it << endl; 
    ++it; 
} 

it = setString.find("boys"); 
if (it != setString.end()) 
    setString.erase(it); 
    
it = setString.begin(); 

cout << endl << endl << "We removed the 'boys'" << endl << endl; 

while(it != setString.end()) 
{ 
    cout << *it << endl; 
    ++it;
}

这会产生以下输出：

setString
a
boys
is
test
this

We removed the 'boys'
a
is
test
this

指定排序顺序

当创建 set 时，我们可以做的另一件事是指定项目的排序方式。我也可以在此容器中使用 string，但从现在开始我将改用 char*。我们将创建一个与之前数据相同的 set，但使用如下的仿函数将其反向排序。

struct gtstr
{
    bool operator()(const char * s1, const char * s2) const
    {
        return (strcmp(s1, s2) > 0);
    }
};

现在在我们的 main 函数中

set<char gtstr*,> setString2;
setString2.insert("this");
setString2.insert("is");
setString2.insert("a");
 setString2.insert("test");
setString2.insert("boys");
cout
<<
endl
<<

"setString2"  <<  endl  <<  endl;

copy(setString2.begin(), setString2.end(),
     ostream_iterator<char*>(cout, "\r\n"));

输出如下：

setString2
this
test
is
boys
a

正如您所见，我们的策略允许项目按反向顺序排序。虽然这是一个微不足道的例子，但用户定义的类型始终需要此类仿函数，因为无法进行默认排序。

set 的优点

set 比其他容器有许多优点。它的插入成本远低于 vector，搜索成本远低于 list，在某些情况下是绝佳的折衷。正如 Scott Meyers 所指出的，如果您创建一个不太可能更改的容器，那么排序数组可能是更好的选择。在这两种情况下，主要优点都来自于易于搜索已排序的容器，而 STL 提供了许多专门用于 set 的函数。

Set 算法

STL 包含一些对排序范围执行 set 相关功能的算法，如下所示

函数名称	函数返回
includes	如果 set one 中的范围存在于 set two 中，则返回 true
set_union	两个 set 中的所有元素
set_intersection	同时存在于两个 set 中的元素
set_difference	仅存在于 set one 中的元素
set_symmetric_difference	仅存在于两个 set 中任一一个的元素

Set 和 map 提供双向迭代器，因此任何接受这些迭代器的其他算法都可以与它们一起使用，并且任何支持至少这些迭代器的排序容器都可以与上面列出的 set 函数一起使用。以下代码在两个相似但不完全相同的 set 上使用了后四种算法

set<char gtstr*,> setString3;

setString3.insert("this");
setString3.insert("could");
setString3.insert("well");
setString3.insert("be");
setString3.insert("the");
setString3.insert("test");

cout << endl << "Set  3"  << endl  <<  endl;

copy(setString3.begin(), setString3.end(), ostream_iterator<char*>(cout, "\r\n"));

cout << endl << endl <<  "Set  Difference"  << endl  <<  endl;

std::set_difference(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

cout << endl << endl <<  "Set  Intersection"  << endl  <<  endl;

std::set_intersection(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

cout << endl << endl <<  "Set  Symmetric  Difference" << endl  <<  endl;

std::set_symmetric_difference(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

cout << endl << endl <<  "Set  Union"  << endl  <<  endl;

std::set_union(setString2.begin(), setString2.end(), 
         setString3.begin(), setString3.end(),
    ostream_iterator<char *>(cout, " "));

输出如下

Set 3
well
this
the
test
could
be
Set Difference
is boys a
Set Intersection
this test
Set Symmetric Difference
well the could be is boys a
Set Union
well this the test could be is boys a

关于哈希 set 的说明

如前所述，set 和 map 通常实现为二叉树。另一种选择是使用哈希表，虽然它们尚不属于标准，但许多实现都提供哈希 set 和 map。哈希的优点是它可能比二叉树提供更好的性能，但二叉树提供稳定的性能，而哈希表在最坏情况下可能提供 O(n) 的性能。我猜这就是为什么当时间紧迫时，二叉树实现进入了标准，而哈希实现则被推迟了。

映射

map 本质上是一个 set，它还在每个位置存储第二个值。第一个值可以被视为一个键，通过它可以找到第二个值。一个我们都可能使用过的例子存在于 MFC 的核心。因为 MFC 将 HWND 封装到一个类中，但最终必须在一个全局的 WndProc 中处理它，所以它创建了一个 map，该 map 将 HWND 映射到一个 CWnd* 实例。然后 WinProc 可以通过查找它收到的 HWND 来访问该类。

要添加到 map，我们可以使用 insert 方法，但使用数组表示法要容易得多，如下所示

map mapInt2String;

mapInt2String[0] = "string number 0";
mapInt2String[2] = "string number 2";
mapInt2String[3] = "string number 3";
mapInt2String[5] = "string number 5";
mapInt2String[6] = "the quick brown fox jumped over the lazy dog";

项目可以以相同的方式提取，但有一个小问题。[] 操作符会在某个位置不存在一个项目时创建一个新项目。以下代码说明了这个问题

cout << "\r\n\r\n\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n";

cout << "mapInt2String[6] = " << mapInt2String[6];

cout << "\r\nMap Int2String has " << mapInt2String.size()
     << " elements\r\n";

cout << "mapInt2String[1] = " <<mapInt2String[1];

cout << "\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n";

这输出以下内容

mapInt2String has 5 elements
mapInttoString[6] = the quick brown fox jumped over the lazy dog
mapInt2String has 5 elements
mapInttoString[1] =
mapInt2String has 6 elements

正确访问 map 中的元素

删除元素的方法是使用 erase 函数，而检查元素是否存在的方法是在访问它之前使用 find。

cout << "\r\nErase rogue element...\r\n";

mapInt2String.erase(mapInt2String.find(1));

cout << "\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n";

if (mapInt2String.find(4) != mapInt2String.end())
    cout << "mapInt2String[4] = " << mapInt2String[4];

cout << "\r\nMap Int2String has " << mapInt2String.size() 
     << " elements\r\n\r\n\r\n\r\n";

这输出以下内容

Erase rogue element....
mapInt2String has 5 elements
mapInt2String has 5 elements

换句话说，我们第二次尝试访问一个不存在的元素并没有导致不必要的插入。

Map 迭代器

作为一个 STL 容器，map 使用迭代器来控制对其元素的访问。然而，map 在每个位置存储两个值，那么迭代器给了我们什么来处理呢？map 的迭代器返回一个 pair<key, value>，这两个值可以分别使用 pair.first 和 pair.second 来访问。以下代码说明了这一点

std::map<int string,>::iterator itMap = mapInt2String.begin();

while (itMap != mapInt2String.end())
{
    cout << "First element = " << itMap->first << endl;
    cout << "Second element = " << itMap->second << endl;
    ++itMap;
}

这将输出以下内容

First element = 0
Second element = string number 0
First element = 2
Second element = string number 2
First element = 3
Second element = string number 3
First element = 5
Second element = string number 5
First element = 6
Second element = the quick brown fox jumped over the lazy dog

第一个和第二个元素提供读写访问，因此元素可以如下更改

itMap = mapInt2String.find(0);

if (itMap != mapInt2String.end())
    itMap->second = "Would you, could you in a car ? "
                         "Eat them, eat them, here they are !!";

再次打印列表会发现这个元素现在已经被更改了。以同样的方式访问 first 允许更改元素的键。

确定这一点后，访问元素的更好方法是捕获我们 find 测试返回的迭代器，并对其调用 second，因为在确定元素存在后使用 [] 操作符需要两次查找，而存储迭代器只需要一次。

使用 multiset/multimap

set 和 map 都需要一个唯一的键，也就是说，将同一个值插入 set 两次只会产生一次插入，对于 map 中具有相同键的两个元素也是如此。当需要多个具有相同值的元素时，我们必须使用 multiset/multimap。这些容器的工作方式与其单元素对应物相同，但有一些额外的函数可以帮助我们使用它们

函数	Returns
计数	具有给定值的元素数量
lower_bound	包含给定值的第一个元素
upper_bound	包含给定值的最后一个元素
equal_range	一对迭代器，它们定义了包含给定值的范围。

我希望您觉得这篇文章很有用，并希望它能激发您使用 STL。到目前为止，我主要谈论了 STL 提供的不同容器（尽管有些仍未涵盖），以及它们如何被专门化。然而，STL 的真正力量在于它与标准库提供的算法的接口方式。到目前为止，本系列中已经出现了一些算法，但下一篇文章将尝试列出许多算法并探讨它们的使用方式。

下次见。