65.9K
CodeProject 正在变化。 阅读更多。
Home

一个类似 STL 的双向映射

Joaquín M López Muñoz
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.93/5 (72投票s)

2002年10月11日

24分钟阅读

viewsIcon

815936

downloadIcon

2493

一个实现双向映射的模板容器，与 STL 良好融合。

目录

引言

std::map 是一个管理（const key, value）对的容器，允许基于键的 O(log n) 查找。映射要求键唯一 - 而值可以重复。

有时，我们希望值也唯一，并且能够对两种类型进行快速查找。这种容器可以建模为**双向映射**，它对构成对的两种类型完全对称。接下来，我们将这两种类型称为 from_type 和 to_type。

bimap 以 STL 容器的精神实现双向映射。在许多方面，bimap 的行为类似于普通的 (const from_type, const to_type) 对的 std::map，但额外增加了 to_type 值唯一的约束。此外，映射提供的所有方法（插入、删除、快速查找、operator []）都为 to_type 值复制了一份。

命名空间

作为对这个出色网站的小小致敬，并为了避免名称冲突，bimap 位于 codeproject 命名空间中。为简洁起见，本文中我们将省略 codeproject:: 前缀。

基本用法

使用 bimap 非常简单，如以下示例所示

#pragma warning(disable:4503)

#include "bimap.h"
#include <iostream>
#include <string>

using codeproject::bimap;

int main(void)
{
  bimap<int,std::string> bm;

  bm[1]="Monday";
  bm[2]="Tuesday";
  bm[3]="Wednesday";
  bm[4]="Thursday";
  bm[5]="Friday";
  bm[6]="Saturday";
  bm[7]="Sunday";

  std::cout<<"Thursday occupies place #"<<bm["Thursday"]<<
             " in the week (european style)"<<std::endl;
  return 0;
}

输出

Thursday occupies place #4 in the week (european style)

这看起来像是使用了普通的 std::map，直到注意到 bm["Thursday"] 的调用，它通过 to_type 值执行快速访问。

bimap 的对称性施加了一些 std::map 中不存在的约束

bimap<string,int> ranking;
ranking["Tom"]=2;
ranking["Bob"]=3;
ranking["Joe"]=2; // throws bimap_base::duplicate_value
// throws throws bimap_base::value_not_found
cout<<"First scorer: "<<ranking[1]<<endl;

当尝试将值赋给 bimap 中已存在的值时，会抛出 bimap_base::duplicate_value：这是容器两侧值唯一性的结果。至于 bimap_base::value_not_found，当尝试访问不存在的键时会抛出此异常：此行为与 std::map 不同，后者会自动为 operator [] 引用的不存在的键分配默认值；bimap 不能采用这种方法，因为它违反了唯一性约束。

成员命名空间 from 和 to

考虑这个例子

bimap <int,int> bm;
bm[1]=5; // which side of the bimap are we referring to?

由于在这种情况下 from_type 和 to_type 相同，我们面临一个歧义问题：如何引用 bimap 的某一边？解决方案由**成员命名空间** from 和 to 提供。我们稍后将详细讨论成员命名空间的概念，但以下内容应清楚地说明它们如何用于解决歧义

bimap <int,int> bm;
bm.from[1]=5; // assigns 5 to the "from" value 1
bm.to[4]=2;   // assigns 4 to the "to" value 2

成员命名空间 from 和 to 实际上可以用于标记 bimap 的所有方法和类型

bimap <int,int> bm;
bimap <int,int>::from::const_iterator it;

for(it=bm.from.begin();it!=bm.from.end();++it){
  // lists pairs in (from,to) order
  cout<<it->first<<"="<<it->second;<<endl; 
}

即使没有歧义，使用成员命名空间也没有坏处。默认情况下，所有没有明确成员命名空间声明的类型和方法都被假定属于 from 成员命名空间，这允许将 bimap 视为常规 std::map（除了双向性施加的唯一性约束）。如果不存在歧义，未标记的调用会自动解析到 to 成员命名空间，如以下示例所示

bimap<int,string> bm;
bm.find("Hello"); // equivalent to bm.to.find("Hello")

成员命名空间 from 和 to 的另一个有趣之处是，只要需要关联容器，就可以传递它们，如以下示例所示

template <typename container>
void dump(const container& c)
{
  for(container::const_iterator it=c.begin();it!=c.end();++it){
    cout<<it->first<<""<<it->last<<endl;
  }
}
 
bimap<string,string> bm;
dump(bm.from);
dump(bm.to); // reverse order

测试套件

除了 *bimap.h* 之外，还提供了一个测试套件，它彻底检查了实现的正确性。该套件还作为 bimap 各种用法的简要指南，此处未详细解释。建议您阅读套件代码并学习如何使用 bimap 的示例。*VC++ 用户注意：构建程序时请确保设置编译器选项 /GX 和 /EHa。*

编译器状态

bimap 已在以下编译器中成功测试

  • VC++ 6.0sp5
  • VC++ 7.0 (又名 .NET 2002)
  • VC++ 7.1 (又名 .NET 2003)
  • GNU GCC 3.2, 3.3, 3.4, 3.4.2
  • Metrowerks CodeWarrior 8.3

代码已尽力使其尽可能符合标准，因此它很可能在其他编译器上无需修改即可工作。如果您能在您喜欢的环境中尝试测试套件并报告结果，我将不胜感激。如果只需少量调整即可使 bimap 在特定编译器上工作，则可以在下一版本中考虑移植。

问题

分配器支持

分配器处理不如预期顺利。出现两个困难

  • VC++ 6.0 不支持分配器中的 rebind：这导致了一些类型差异和偶尔对 allocator_type 实际类型的默认假设。其他编译器没有这个问题。
  • swap 函数假定分配器等效性（即，假定两个相同类型的分配器能够管理彼此分配的数据）：尚未找到以异常安全的方式处理分配器非等效性的解决方案。

使用 std::allocator 时，这是迄今为止最常见的情况，不会出现任何问题。

显式引用类型 from 和 to

以下语句无法编译

codeproject::bimap<int,int>::from* f;

这不是编译器错误，而是由于成员命名空间 from 和 to 的定义方式而产生的细微差别。正确的表达式需要 class 关键字

class codeproject::bimap<int,int>::from* f;

问题只在引用 from 和 to 类型时出现：使用嵌入在这些类型中的类型时不需要额外的 class 关键字

codeproject::bimap<int,int>::from::iterator it; // OK, no 'class' needed

提示式插入

对于 std::map 和其他关联容器，标准要求如果提示迭代器紧邻插入点之前，则提示式插入的摊销常数时间性能。由于 VC++ 6.0 的 STL 实现中存在一个 bug，bimap 内部依赖此实现，因此采用了不同的策略：当提示紧邻插入点**之后**时，发生摊销常数时间。

该问题已在 VC++ 7.0 的 STL 实现中得到纠正。在这里，bimap 保证当提示紧邻插入点之前或之后时，具有摊销常数时间。

在其他编译器中，遵循标准规则，即提示应在插入点之前。

全局 swap 函数

此问题仅适用于 VC++ 6.0 和 7.0。提供了全局 swap 函数来交换两个 bimap 的内容，可选择通过它们的 from 或 to 成员命名空间。这些函数位于 codeproject 命名空间中。根据 C++ Koenig 查找规则，以下内容应该没问题

bimap<int,int> bm1,bm2;
swap(bm1,bm2); // should call codeproject::swap()

不幸的是，VC++ 不为非运算符函数实现 Koenig 查找，因此调用的是 std::swap 而不是上面的代码片段。标准禁止为 bimap 重载 std::swap，因此唯一的选择是显式限定 swap

bimap<int,int> bm1,bm2;
codeproject::swap(bm1,bm2);

参考

Types

bimap<
typename from_type, typename to_type,
typename from_compare=std::less<from_type>,
typename to_compare=std::less<to_type>,
typename allocator_type=
  std::allocator<direct_pair<const from_type,const to_type> > >

指定 from_type 和 to_type 类型的双向映射。这些必须是可复制类型，但与 std::map 不同，它们不需要默认可构造。bimap 两侧值的排序分别根据 from_compare 和 to_compare 类型的谓词进行。

key_type, from::key_type

from_type 的同义词。

to::key_type

to_type 的同义词。

mapped_type, from::mapped_type, referent_type, 
         from::referent_type, data_type, from::data_type

to_type 的同义词。

to::mapped_type, to::referent_type, to::data_type

from_type 的同义词。

key_compare, from::key_compare

from_compare 的同义词。

to::key_compare

to_compare 的同义词。

allocator_type, from::allocator_type, to::allocator_type

allocator_type 的同义词。

value_type, from::value_type

特定于实现的类型，可转换为 std::pair<const from_type, const to_type>。

to::value_type

特定于实现的类型，可转换为 std::pair<const to_type, const from_type>。

value_compare, from::value_compare

特定于实现的函数对象类型，根据 from_compare 和 to_compare（按此顺序）按字典序比较 value_type 对象。

to::value_compare

特定于实现的函数对象类型，根据 to_compare 和 from_compare（按此顺序）按字典序比较 to::value_type 对象。

size_type, from::size_type, to::size_type

allocator_type::size_type 的同义词。

difference_type, from::difference_type, to::difference_type

allocator_type::difference_type 的同义词。

pointer, from::pointer

value_type * 的同义词。

to::pointer

to::value_type * 的同义词。

const_pointer, from::const_pointer

const value_type * 的同义词。

to::const_pointer

const to::value_type * 的同义词。

reference, from::reference

value_type& 的同义词。

to::reference

to::value_type& 的同义词。

const_reference, from::const_reference

const value_type& 的同义词。

to::const_reference

const to::value_type& 的同义词。

iterator, from::iterator

指向 value_type 类型元素的双向迭代器。

to::iterator

指向 to::value_type 类型元素的双向迭代器。

const_iterator, from::const_iterator

指向 const value_type 类型元素的双向迭代器。

to::const_iterator

指向 const to::value_type 类型元素的双向迭代器。

reverse_iterator, from::reverse_iterator

指向 value_type 类型元素的双向反向迭代器。

to::reverse_iterator

指向 to::value_type 类型元素的双向反向迭代器。

const_reverse_iterator, from::const_reverse_iterator

指向 const value_type 类型元素的双向反向迭代器。

to::const_reverse_iterator

指向 const to::value_type 类型元素的双向反向迭代器。

inv_bimap

此成员 typedef 标识一个 from_type 和 to_type 颠倒的 bimap 类型。例如，codeproject::bimap<int,double>::inv_bimap 等效于 codeproject::bimap<double,int>。

VC++ 6.0：由于 VC++ 6.0 中分配器支持的限制，inv_bimap 假定 std::allocator 作为分配器类型，而不是从定义它的 bimap 的分配器类型重新绑定。

异常

codeproject::bimap_base::duplicate_value: public std::logic_error

当尝试插入违反 from_type 和 to_type 值唯一性的操作时，由某些方法抛出。

codeproject::bimap_base::value_not_found: public std::logic_error

当指定元素不存在于 bimap 中时，由各种形式的 operator[] 抛出。

构造函数和赋值

explicit bimap(
const from_compare& from_comp=from_compare(),
const to_compare& to_comp=to_compare(),
const allocator_type& al=allocator_type())

构造一个空 bimap，使用提供的比较和分配参数，如果未提供则使用默认值。

复杂度：常数时间。

bimap(const bimap& r)

构造给定 bimap 的副本。比较和分配对象也从给定 bimap 复制。

复杂度：一般为 O(n log n)，如果 r 是单调的（即 x<y 意味着 r[x]<r[y] 对于 r 中的每个 (x, r[x]), (y, r[y])），则为 O(n)。

explicit bimap(const inv_bimap& r)

从给定 inv_bimap 构造映射。

复杂度：一般为 O(n log n)，如果 r 是单调的（即 x<y 意味着 r[x]<r[y] 对于 r 中的每个 (x, r[x]), (y, r[y])），则为 O(n)。

template <typename it_type> bimap(
it_type first,it_type last,
const from_compare& from_comp=from_compare(),
const to_compare& to_comp=to_compare(),
const allocator_type& al=allocator_type())

构造一个映射，并用范围 [first, last) 中的值填充它。还可以额外指定比较器和分配器对象。

抛出

  • 当尝试插入的 from_type 或 to_type 值已存在于 bimap 中时，抛出 duplicate_value。

复杂度：一般为 O(n log n)，如果 [first, last) 按其 first 值排序，则为一半时间，如果该区间是单调的（即 it1->first<it2->first 意味着 it1->second<it2->second 对于 [first, last) 中的每个 it1, it2），则为 O(n)。

~bimap()

析构 bimap。

复杂度：O(n)

bimap& operator=(const bimap& r)

将给定 bimap 赋值给当前 bimap。保留原始的比较器和分配器对象。*注意：假定分配器等效。*

复杂度：一般为 O(n log n)，如果 r 是单调的（即 x<y 意味着 r[x]<r[y] 对于 r 中的每个 (x, r[x]), (y, r[y])），则为 O(n)。

class from& from.operator=(const from& r)

这等效于调用 operator=(owner)，其中 owner 是 r 所属的 bimap。

复杂度：一般为 O(n log n)，如果 r 是单调的（即 x<y 意味着 r[x]<r[y] 对于 r 中的每个 (x, r[x]), (y, r[y])），则为 O(n)。

class to& to.operator=(const to& r)

这等效于调用 operator=(owner)，其中 owner 是 r 所属的 bimap。

复杂度：一般为 O(n log n)，如果 r 是单调的（即 x<y 意味着 r[x]<r[y] 对于 r 中的每个 (x, r[x]), (y, r[y])），则为 O(n)。

比较

bool operator==(const bimap& r) const
bool operator!=(const bimap& r) const
bool operator< (const bimap& r) const
bool operator> (const bimap& r) const
bool operator<=(const bimap& r) const
bool operator>=(const bimap& r) const
bool from.operator==(const from& r) const
bool from.operator!=(const from& r) const
bool from.operator< (const from& r) const
bool from.operator> (const from& r) const
bool from.operator<=(const from& r) const
bool from.operator>=(const from& r) const

bimap 的比较是根据其元素的 from_type 值按字典序进行的。

复杂度：O(n)，其中 n 是被比较 bimap 长度的最小值。

bool to.operator==(const to& r) const
bool to.operator!=(const to& r) const
bool to.operator< (const to& r) const
bool to.operator> (const to& r) const
bool to.operator<=(const to& r) const
bool to.operator>=(const to& r) const

bimap 的比较是根据其元素的 to_type 值按字典序进行的。这通常与根据 from_type 值进行的比较不等效。

复杂度：O(n)，其中 n 是被比较 bimap 长度的最小值。

迭代器检索

iterator begin()
from::iterator from.begin()

返回指向 bimap 开头（从 from_type 侧看）的 iterator。提供了 const 版本，返回相应的 const_iterator。

复杂度：常数时间

to::iterator to.begin()

返回指向 bimap 开头（从 to_type 侧看）的 to::iterator。提供了 const 版本，返回相应的 to::const_iterator。

复杂度：常数时间

iterator end()
from::iterator from.end()

返回指向 bimap 结尾（从 from_type 侧看）的 iterator。提供了 const 版本，返回相应的 const_iterator。

复杂度：常数时间

to::iterator to.end()

返回指向 bimap 结尾（从 to_type 侧看）的 to::iterator。提供了 const 版本，返回相应的 to::const_iterator。

复杂度：常数时间

reverse_iterator rbegin()
from::reverse_iterator from.rbegin()

返回指向 bimap 结尾（从 from_type 侧看）之后的 reverse_iterator。提供了 const 版本，返回相应的 const_reverse_iterator。

复杂度：常数时间

to::reverse_iterator to.rbegin()

返回指向 bimap 结尾（从 to_type 侧看）之后的 to::reverse_iterator。提供了 const 版本，返回相应的 to::const_reverse_iterator。

复杂度：常数时间

reverse_iterator rend()
from::reverse_iterator from.rend()

返回指向 bimap 第一个元素（从 from_type 侧看）的 reverse_iterator。提供了 const 版本，返回相应的 const_reverse_iterator。

复杂度：常数时间

to::reverse_iterator to.rend()

返回指向 bimap 第一个元素（从 to_type 侧看）的 to::reverse_iterator。提供了 const 版本，返回相应的 to::const_reverse_iterator。

复杂度：常数时间

实用成员函数

size_type size() const
from::size_type from.size() const
to::size_type to.size() const

返回映射中的元素数量。

复杂度：常数时间

size_type max_size() const
from::size_type from.max_size() const
to::size_type to.max_size() const

返回可能的最长 bimap 的长度。

复杂度：常数时间

bool empty() const
bool from.empty() const
bool to.empty() const

指示映射是否为空。

复杂度：常数时间

allocator_type get_allocator() const
from::allocator_type from.get_allocator() const
to::allocator_type to.get_allocator() const

返回 bimap 所持有的 allocator_type 对象的副本。

复杂度：常数时间

插入和擦除

(implementation specific return type) 
           operator[](const key_type& key)
(implementation specific return type) 
           from.operator[](const from::key_type& key)

operator[] 的行为与 std::map 相同。返回的对象是特定于实现的，但它提供了一个赋值运算符和到 to_type& 的自动转换，以便可以编写以下语句

bimap<int,string> bm;
bm[1]="Hello"; //assignment
string s=bm[1]; // retrieval of a string&

提供了此运算符的 const 版本。

在某些情况下，编译器无法自动执行到 to_type& 的转换：在这种情况下，可以使用辅助 get() 方法

bimap<int,string> bm;
string s=bm[1].get();

抛出

  • 当尝试将值赋给 bimap 中已包含的 to_type 时，抛出 duplicate_value。在 from_type 值被重新分配给它已经绑定的相同 to_type 值的情况下，不会抛出异常。
  • 当查询 bimap 中不存在的 from_type 值的 to_type 值时，抛出 value_not_found。

查找复杂度：O(log n)

赋值复杂度：O(log n)（查找时间的两次）

(implementation specific return type) 
            operator[](const to::key_type& key)*
(implementation specific return type) 
            to.operator[](const to::key_type& key)

*仅在 from_type!=to_type 时可用。

operator[] 的行为与 std::map 相同。返回的对象是特定于实现的，但它提供了一个赋值运算符和到 from_type& 的自动转换，以便可以编写以下语句

bimap<int,string> bm;
bm["Hello"]=1; // assignment
int i=bm["Hello"]; // retrieval of an int&

提供了此运算符的 const 版本。

在某些情况下，编译器无法自动执行到 from_type& 的转换：在这种情况下，可以使用辅助 get() 方法

bimap<int,string> bm;
int i=bm["Hello"].get();

抛出

  • 当尝试将值赋给 bimap 中已包含的 from_type 时，抛出 duplicate_value。在 to_type 值被重新分配给它已经绑定的相同 from_type 值的情况下，不会抛出异常。
  • 当查询 bimap 中不存在的 to_type 值的 from_type 值时，抛出 value_not_found。

查找复杂度：O(log n)

赋值复杂度：O(log n)（查找时间的两次）

std::pair<iterator, bool> insert(const value_type& x)
std::pair<from::iterator, bool> 
               from.insert(const from::value_type& x)

当且仅当没有已存在的元素具有等效的 from_type 值时，将给定的 value_type 插入到 bimap 中。在任何一种情况下，返回对的 iterator 部分指向 bimap 中具有等效 from_type 值的元素。bool 成员指示是否真的发生了插入。

抛出

  • 当没有具有等效 from_type 值的先前元素存在，但 to_type 部分已存在于 bimap 中时，抛出 duplicate_value。

复杂度：O(log n)

std::pair<to::iterator, bool> insert(const to::value_type& x)
std::pair<to::iterator, bool> to.insert(const to::value_type& x)

当且仅当没有已存在的元素具有等效的 to_type 值时，将给定的 to::value_type 插入到 bimap 中。在任何一种情况下，返回对的 to::iterator 部分指向 bimap 中具有等效 to_type 值的元素。bool 成员指示是否真的发生了插入。

抛出

  • 当没有具有等效 to_type 值的先前元素存在，但 from_type 部分已存在于 bimap 中时，抛出 duplicate_value。

复杂度：O(log n)

iterator insert(iterator it, const value_type& x)
from::iterator from.insert(from::iterator it, 
                       const from::value_type& x)

将 x 插入到 bimap 中，使用 it 作为定位插入点的提示。返回指向插入元素的迭代器（如果已包含具有等效 from_type 值的元素，则返回现有元素的迭代器）。

抛出

  • 当没有具有等效 from_type 值的先前元素存在，但 to_type 部分已存在于 bimap 中时，抛出 duplicate_value。

复杂度：O(log n)，但如果 it 紧邻插入点之前，则时间减半。

VC++ 6.0 复杂度：O(log n)，但如果 it 紧邻插入点之后，则时间减半。

VC++ 7.0 复杂度：O(log n)，但如果 it 紧邻插入点之前或之后，则时间减半。

to::iterator insert(to::iterator it, const to::value_type& x)
to::iterator to.insert(to::iterator it, const to::value_type& x)

将 x 插入到 bimap 中，使用 it 作为定位插入点的提示。返回指向插入元素的迭代器（如果已包含具有等效 to_type 值的元素，则返回现有元素的迭代器）。

抛出

  • 当没有具有等效 to_type 值的先前元素存在，但 from_type 部分已存在于 bimap 中时，抛出 duplicate_value。

复杂度：O(log n)，但如果 it 紧邻插入点之前，则时间减半。

VC++ 6.0 复杂度：O(log n)，但如果 it 紧邻插入点之后，则时间减半。

VC++ 7.0 复杂度：O(log n)，但如果 it 紧邻插入点之前或之后，则时间减半。

std::pair<from::iterator,to::iterator> 
   insert(from::iterator fit,to::iterator tit, const value_type& x)

将 x 插入到 bimap 中，分别使用 fit 和 tit 作为定位 from 和 two 部分中插入点的提示。返回一对，包含指向插入元素（如果值已包含，则为现有元素）的 from 和 to 迭代器。

抛出

  • 如果 x 的 from_type 或 to_type 已存在于 bimap 中，则抛出 duplicate_value。

复杂度：一般为 O(log n)，如果其中一个提示紧邻插入点之前，则时间减半，如果两个提示都紧邻相应的插入点之前，则为摊销常数时间。

VC++ 6.0 复杂度：一般为 O(log n)，如果其中一个提示紧邻插入点之后，则时间减半，如果两个提示都紧邻相应的插入点之后，则为摊销常数时间。

VC++ 7.0 复杂度：一般为 O(log n)，如果其中一个提示紧邻插入点之前或之后，则时间减半，如果两个提示都紧邻相应的插入点之前或之后，则为摊销常数时间。

template<typename it_type> void insert(it_type first,
                                               it_type last)
template<typename it_type> void from.insert(it_type first,
                                               it_type last)

插入范围 [first, last) 中的 value_type 元素。插入策略与单个值插入相同。

抛出

  • 在与插入单个值相同的情况下抛出 duplicate_value。

复杂度：O(m log m+n)，其中 m 是 [first, last) 的长度。

void insert(const to::value_type * first,const to::value_type * last)
template<typename it_type> void to.insert(it_type first,it_type last)

插入范围 [first, last) 中的 to::value_type 元素。插入策略与单个值插入相同。

抛出

  • 在与插入单个值相同的情况下抛出 duplicate_value。

复杂度：O(m log m+n)，其中 m 是 [first, last) 的长度。

void erase(iterator it)
void from.erase(from::iterator it)

在 VC++ 中替换为

iterator erase(iterator it)
from::iterator from.erase(from::iterator it)

擦除 it 指向的元素。

VC++：返回的 iterator 指向 bimap 中的下一个元素，如果不存在此类元素，则为 end()。

复杂度：O(log n)

void erase(to::iterator it)
void to.erase(to::iterator it)

在 VC++ 中替换为

iterator erase(to::iterator it)
to::iterator to.erase(to::iterator it)

擦除 it 指向的元素。

VC++：返回的 to::iterator 指向 bimap 中的下一个元素，如果不存在此类元素，则为 to.end()。

复杂度：O(log n)

void erase(iterator first,iterator last)
void from.erase(from::iterator first,from::iterator last)

擦除范围 [first, last) 中的元素。

复杂度：O(m log n)，其中 m 是 [first, last) 的长度。

void erase(to::iterator first,to::iterator last)
void to.erase(to::iterator first,to::iterator last)

擦除范围 [first, last) 中的元素。

复杂度：O(m log n)，其中 m 是 [first, last) 的长度。

size_type erase(const key_type& key)
from::size_type from.erase(const from::key_type& key)

如果存在，擦除其 from_type 部分等于 key 的元素。根据是否发生删除返回 1 或 0。

复杂度：O(log n)（基于迭代器的插入时间的两次）。

size_type erase(const to::key_type& key)*
to::size_type to.erase(const to::key_type& key)

*仅在 from_type!=to_type 时可用。

如果存在，擦除其 to_type 部分等于 key 的元素。根据是否发生删除返回 1 或 0。

复杂度：O(log n)（基于迭代器的插入时间的两次）。

void clear()
void from.clear()
void to.clear()

这些成员函数解析为对 erase(begin(),end()) 的调用

复杂度：O(n log n)

void swap(bimap& x)
void from.swap(bimap::from x)
void to.swap(bimap::to x)

交换 bimap 的元素与 x 的元素。*注意：假定分配器等效。*

复杂度：常数时间

void codeproject::swap(bimap& x,bimap& y)
void codeproject::swap(bimap::from& x,bimap::from& y)
void codeproject::swap(bimap::from& x,bimap::from& y)

这些是全局函数。它们交换 x 和 y 的元素。*注意：假定分配器等效。*

复杂度：常数时间

搜索

key_compare key_comp() const
from::key_compare from.key_comp() const

返回用于比较 from_type 键的内部 key_compare 对象的副本。

复杂度：常数时间

to::key_compare to.key_comp() const

返回用于比较 to_type 键的内部 to::key_compare 对象的副本。

复杂度：常数时间

value_compare value_comp() const
from::value_compare from.value_comp() const

返回一个类型为 value_compare 的对象，它与 from.key_comp() 和 to.key_comp() 引起的字典序一致。

复杂度：常数时间

to::value_compare to.value_comp() const

返回一个类型为 to::value_compare 的对象，它与 to.key_comp() 和 from.key_comp() 引起的字典序一致。

复杂度：常数时间

iterator find(const key_type& key)
from::iterator from.find(const from::key_type& key)

返回指向 from_type 值等于 key 的元素的迭代器，如果不存在此类元素，则返回 end()。提供了 const 版本，返回 const_iterator。

复杂度：O(log n)

to::iterator find(const to::key_type& key)*
to::iterator to.find(const to::key_type& key)

*仅在 from_type!=to_type 时可用。

返回指向 to_type 值等于 key 的元素的迭代器，如果不存在此类元素，则返回 to.end()。提供了 const 版本，返回 to::const_iterator。

复杂度：O(log n)

size_type count(const key_type& key) const
from::size_type from.count(const from::key_type& key) const

如果 bimap 包含其 from_type 部分等于 key 的元素，则返回 1，否则返回 0。

复杂度：O(log n)

size_type count(const to::key_type& key) const*
to::size_type to.count(const to::key_type& key) const

*仅在 from_type!=to_type 时可用。

如果 bimap 包含其 to_type 部分等于 key 的元素，则返回 1，否则返回 0。

复杂度：O(log n)

iterator lower_bound(const key_type& key)
from::iterator from.lower_bound(const from::key_type& key)

返回指向 bimap 中（从 from 成员命名空间看）第一个 from_type 值不小于 key 的元素的迭代器。提供了 const 版本，返回 const_iterator。

复杂度：O(log n)

to::iterator lower_bound(const to::key_type& key)*
to::iterator to.lower_bound(const to::key_type& key)

*仅在 from_type!=to_type 时可用。

返回指向 bimap 中（从 to 成员命名空间看）第一个 to_type 值不小于 key 的元素的迭代器。提供了 const 版本，返回 to::const_iterator。

复杂度：O(log n)

iterator upper_bound(const key_type& key)
from::iterator from.upper_bound(const from::key_type& key)

返回指向 bimap 中（从 from 成员命名空间看）第一个 from_type 值大于 key 的元素的迭代器。提供了 const 版本，返回 const_iterator。

复杂度：O(log n)

to::iterator upper_bound(const to::key_type& key)*
to::iterator to.upper_bound(const to::key_type& key)

*仅在 from_type!=to_type 时可用。

返回指向 bimap 中（从 to 成员命名空间看）第一个 to_type 值大于 key 的元素的迭代器。提供了 const 版本，返回 to::const_iterator。

复杂度：O(log n)

std::pair<iterator, iterator> equal_range(const key_type& key)
std::pair<from::iterator, from::iterator> 
                    from.equal_range(const from::key_type& key

返回一对迭代器，其第一个成员为 lower_bound(key)，第二个成员为 upper_bound(key)。提供了 const 版本，返回相应的 const_iterator。

复杂度：O(log n)

std::pair<to::iterator, to::iterator> 
              equal_range(const to::key_type& key)*
std::pair<to::iterator, to::iterator> 
              to.equal_range(const to::key_type& key)

*仅在 from_type!=to_type 时可用。

返回一对迭代器，其第一个成员为 to.lower_bound(key)，第二个成员为 to.upper_bound(key)。提供了 const 版本，返回相应的 to::const_iterator。

复杂度：O(log n)

附录 1：成员命名空间

bimap 使用一种我称之为**成员命名空间**的构造。成员命名空间与命名空间有一些相似之处，但它们并不完全相同，并且 C++ 本身并不支持它们。本附录简要介绍了成员命名空间及其在某些情况下证明有用的原因，并概述了如何在标准 C++ 中模拟它们。

假设我们正在定义一个存储整数的双向队列。这样的队列有两个端点，比如 head 和 tail，提供通常的 push 和 pull 操作。由于一个类不能拥有两个同名同参数的成员函数，所以问题就出现了如何为队列的每个端点命名相应的成员函数。一个朴素的方法是简单地在成员函数名称上加上一些消歧前缀

class twoway_queue
{
public:
  void head_push(int n);
  int  head_pull();
  void tail_push(int n);
  int  tail_pull();
  ...
};

这个简单的解决方案存在几个限制

  • 它在美学上令人不悦。
  • 它不适用于运算符，例如 operator []。
  • 有时，我们希望使用具有预先存在的通用代码的类，这些代码假定成员函数具有某些名称，如以下示例所示
    template<typename queue_type> void fill_n(
                           queue_type& q,int n)
{
  for(int i=1;i<n;++i)q.push(i);
}

    在这些情况下，名称修饰会破坏通用代码预期的“接口”，使其无法使用。

成员命名空间通过在定义的类中引入额外的作用域级别来解决所有这些问题

class twoway_queue
{
public:
  memberspace head //warning, "memberspace" is not C++
  { 
  public:
    void push(int n);
    int  pull();
  }
 
  memberspace tail
  {
  public:
    void push(int n);
    int  pull();
  }
  ...
};

成员命名空间的使用非常简单

twoway_queue q;
q.head.push(1);
cout<<q.tail.pull()<<endl;
fill_n(q.head,100);

成员命名空间带来的额外作用域级别不仅限于成员（通过 operator . 调用），它还用于定义局部类型（通过 :: 引用）

// class to convert between ints and their 
// string representations and viceversa
class int2string_queue 
{
public:
  memberspace int_end
  {
  public:
    typedef int type;
    void push(int n);
    int pull();
  }
   
  memberspace str_end
  {
  public:
    typedef string type;
    void push(string str);
    string pull();
  }
...
};
 
int2string_queue q;
int2string_queue::str_end::type a; // a string
a=q.str_end.pull();
cout<<a<<endl;

因此，成员命名空间可以被视为扮演嵌入对象和类内命名空间角色的双重构造。

实现

虽然 C++ 不直接支持成员命名空间，但可以通过一个鲜为人知的、源自 C 语言的语法规则来有效地模拟它们，该规则允许对象和类拥有相同的名称

class A
{
  ...
};
class A A; // legal C++! object A is of type A

我们可以利用这个规则为成员命名空间的实现奠定基础

class twoway_queue
{
public:
  class head
  { 
  public:
    void push(int n);
    int  pull();
  }head; // head is both a nested 
         // class and an embedded object
  ...
};

这种构造对嵌套类的内存布局没有或只有最小的惩罚。为了确保封装类和成员命名空间的 private 成员之间可以相互访问，我们只需安排必要的 friend 声明

class twoway_queue
{
public:
  class head
  { 
    friend twoway_queue;
  public:
    void push(int n);
    int  pull();
  }head;
  friend class head;
  ...
};

完成这个构建只剩下最后一块砖：当成员空间内的代码需要访问封装类的某个成员时，它必须找出它嵌入的对象。这可以在编译时解决，如果我们注意到成员空间对象在封装类内的确切位置是预先已知的，这样我们就可以强制将其“向上转换”为整个类，就像这样

class twoway_queue
{
  class head
  {
  public:
    void push(int n)
    {
      ...
      
      owner().length++; // access private member 
                        // length of twoway_queue
    }   
  ...
  private:
    twoway_queue& owner()
    {
      return *reinterpret_cast<twoway_queue*>(
        reinterpret_cast<char*>(this)-offsetof(
                                 twoway_queue,head));
    }
  }head;
  ...
}

还有一些不重要的细节需要完善，例如定义 owner 的 const 版本，并通过声明复制构造函数和赋值运算符为 private 来强制成员空间对象不应存在于类中定义的位置之外。

附录 2：数据结构

为了提供类似于 std::map 的 from_type 和 to_type 键功能，bimap 维护两个指向元素的 std::set。该图显示了包含元素 (1,'c')、(3,'a') 和 (2,'b') 的 bimap<int,char> 的数据布局

然而，仍然存在一个问题：STL 关联容器应该包含（键，值）对。从 to_type 部分的角度来看，这个要求没有得到满足，因为 two_type 值在对中排在第二位。为了解决这个问题，使用了以下技巧：定义了两个模板类，名为 direct_pair 和 inv_pair；direct_pair 的行为与常规 std::pair 相同，而 inv_pair 的 first 和 second 成员按相反顺序排列，first 是对象布局中的第二个。因此，一个 direct_pair<A,B> 可以被 reinterpret_cast 转换为一个 inv_pair<B,A>，反之亦然。from::iterator 和 to::iterator 分别设置为指向 direct_pair 和 inv_pair，尽管实际上它们指向相同的内存块。从 STL 等通用算法的角度来看，from::iterator 和 to::iterator 的行为都符合预期，指向一个其名为 first 的成员是键，second 是值的对象。以下 UML 图显示了不同类型之间的关系

致谢

  • 感谢 Alexandru Savescu，他测试了该库在 VC++ 7.0 中的一些 beta 版本并指出了各种错误。
  • Manuel Prieto Martín 在 VC++ 7.0 中测试了最终版本 1.0。Jorge Munuera Andreo 在此编译器上检查了最终版本 1.1。
  • 使 bimap 在 VC++ 之外的编译器下运行的动机来自 Bala Swaminathan，他完成了 GCC 的初始移植，版本 1.1 是基于此编写的。他还测试了 GCC 不同版本下的最终版本 1.1。
  • Andrew Pollard 提供了一个解决方法，用于抑制 GCC 中一些与 offsetof 使用相关的恼人警告。
  • David Phillip Oster 提供了将 bimap 移植到 CodeWarrior 8.3 的修复。他、Dmitry Markman 和 Herb Davis 测试了此编译器的最终版本 1.1。
  • 非常感谢 Steve Robb 找到（并分享）了一种使 VC++ 7.1 编译该库而不会崩溃的方法，当时似乎无法在不更改 bimap 的公共接口的情况下完成此操作。
  • Gregoire Banderet 测试了版本 1.3 在 GCC 3.3、GCC 3.4 和 VC++ 7.1 下的情况。

参考文献

实现代码相当混乱，并利用了几种巧妙的技术来模拟部分模板特化。想法来自以下来源

  • Alexandrescu, A.: Modern C++ Design: Generic Programming and Design Patterns Applied, ch. 2, Addison-Wesley, February 2001.
  • Boost, type_traits 库, boost::is_same<T,U> 模板, 2001 年 4 月, boost.org。
  • Czarnecki, K., Eisenecker, U.: Generative Programming - Methods, Tools, and Applications, Addison-Wesley, June 2000.
  • Marcus, M., Jones, J.: "Simulated partial Specialization for C++", 2000 年 9 月，原始链接不再可用，文章存储在 web.archive.org。

版本历史

  • 2002年10月9日 - 1.0 版。
    • 初次发布。请留意频繁更新！
  • 2003年2月6日 - 1.1 版。
    • bimap::erase(to::iterator,to::iterator) 错误地返回了一个迭代器。文档对此点也存在错误。
    • 不正确地使用 allocator::allocate 和 allocator::deallocate 导致使用了比必要更多的内存。
    • 改进了语言一致性，涉及缺失的 typename 和 template 关键字、错误的 friend 声明以及 VC++ 中 <iterator> 某些功能的损坏实现。
    • 如果编译器支持，则使用 allocator::rebind。
    • 修复了复制构造函数中分配器和比较对象构造的一些不一致。
    • 分配器对象曾经被无故地设置为 protected：已更改为与其余内部对象相同的 private。
    • 进行了一些调整，以使其在 GNU GCC 和 Metrowerks CodeWarrior 下编译。
    • GCC 不喜欢模板参数和已定义类型具有相同的名称：我不知道这是否真的符合标准。
  • 2006年1月10日 - 1.2 版。
    • bimap 现在适用于 VC 7.1。这一长期要求的升级得益于 Steve Robb，他找到了一种避免旧版库触发内部编译器错误的方法。
  • 2006年10月26日 - 1.3 版。
    • 代码已更新，以便正确处理一种（强制性的）模板机制，称为两阶段名称查找。因此，bimap 现在适用于现代版本的 GCC。
© . All rights reserved.