part3 关联容器
与序列容器区别
(1) 自动排序
(2) 比较是按照等价(equivalence)而不是相等(equality)
(3) set/map 不允许有重复
key points
(1) 等价的概念
(2) 比较函数的限制
(3) 指针关联容器, 要自定义比较函数
(4) 键的常量性(constness)的官方含义和实际含义
(5) 关联容器提高效率的建议
item19: 理解相等(equality)和等价(equivalence)的区别
1 STL中经常需要比较2个对象, 判断它们的值是否相同
2个代表性的函数算法find()和成员函数set::insert()对"相同"的定义不同: 相等和等价, 分别基于 operator== 和 operator<
关联容器所有成员函数(set::insert 和set::find()等)对相同的定义相同
相等并不一定意味所有数据成员都相等, 通常只关注某个字段
等价以"在已排序区间中对象值的相对排列顺序"为基础
2 为什么标准关联容器是基于等价而不是相等
例: 不区分大小写的 set<string, CIStringCompare[, equal_to<string> ] >, 决定排列顺序/是否等价的比较函数 忽略 字符串中字符大小写
item35: 实现了这样的函数 ciStringCompare, 不区分大小写的比较
但 set 需要一个`比较函数类型/functor`, 其 operator() 调用 ciStringCompare
struct CIStringCompare
: public binary_function <string, string, bool> // item40: 提供可配接能力
{
bool
operator()(const string& lhs, const string& rhs)
{
return ciStringCompare(lhs, rhs); // item35, 忽略大小写的字符串比较函数
}
};
标准关联容器自动排序, 所以必须用1个比较函数(默认为std::less)来决定 如何排序/排列顺序
(1) 若基于相等 判2个元素是否"相同", 则关联容器需要2个比较函数: 一个用于 排序(判/决定 2个值 的排列顺序/是否等价), 另一个用于 判相同(判/决定 2个值是否 相同/允许插入 )
-> 对non-multi容器(set/map)带来非常直观的混乱或错误
1)混乱: 成员函数实现可能基于相等, 这与正确的容器行为违背
2)错误: 破坏non-multi容器(set/map)keyPart值的唯一性(非重性); 会破坏multi容器(multiset/multimap)的排序规则
[1]
set<string, CIStringCompare, equal_to<string> > set2CF;
| |
| |
决定 排列顺序 决定 (key)值是否相同 => 决定是否允许插入
set2CF.insert("Abc");
set2CF.insert("abc");
CIStringCompare
"Abc" 与 "abc" 等价(无排列顺序) => 后者不应该被插入, 以保持容器的排序性
equal_to<string>
"Abc" 与 "abc" 不相等 => 不相同 => 后者可以插入
1) 假设实现保持了排序性, 后者没插入
成员函数 理应基于排序性/等价
=> if(set2CF.find("abc") != set2CF.end() ) // find 成功
但`成员函数find可能基于 相等`
=> if(set2CF.find("abc") != set2CF.end() ) // find 失败
=> 混乱
2) 假设实现允许后者插入 => `破坏`non-multi容器(set/map)key值的唯一性(非重性)`
[2] 上述换为 multiset
equal_to<string>
"Abc" 与 "abc" 不相等 => 不相同 => 后insert的"abc"插入
CIStringCompare
"Abc" 与 "abc" 等价 => 排列顺序(谁在前)不限定/不确定
=> `不能以确定的顺序遍历容器的元素`
假定 "abc" 在 "Abc" 前
`成员函数find可能基于 相等`
=> if(multiSet2CF.find("abc") != multiSet2CF.end() ) // find 成功
(2) 若基于等价 判2个元素是否"相同", 则关联容器只需1个比较函数: 既用于 排序(判2个值 的排列顺序/是否等价), 又用于 判相同(判/决定 2个值是否 相同/允许插入 )
set<string, CIStringCompare> cisSet;
cisSet.insert("Abc");
cisSet.insert("abc"); // "abc" 与 "Abc" 等价 => 相同 => "abc" 不被插入
if(cisSet.find("abc") != cisSet.end() ) // set::find 基于等价 => find 成功
if( find(cisSet.begin(), cisSet.end(), "abc" )
!= cisSet.end() ) // 算法 find() 基于相等 => find 失败
=> 优先选择成员函数(如 std::find) 而不是相应的非成员函数/算法(如 find)
3 等价的含义: 两个值(按指定的比较函数/排序准则)任一个都不在另一个的前面, 则这两个值(按该比较函数/排序准则)等价
默认 operator<
!(w1 < w2) && !(w2 < w1) // w1 < w2 不为真, 且 w2 < w1 不为真
client 如何知道2个对象是否等价? 答: 用关联容器的成员函数key_comp
默认 less == key_comp
// 在容器c的排列顺序中, w1在w2之前不为真, w2在w1之前也不为真
!c.key_comp()(w1, w2) && !c.key_comp()(w2, w1) // key_comp()返回1个函数对象实例
w1不在w2之前 => c.key_comp()(w1, w2)为false => !c.key_comp()(w1, w2)为true
4 关联容器的比较函数
[1] 目的是判2个元素的key值(对set/map, 也是value值/只是key值)是否相同
[2] 决定排列顺序/排序准则
5 基于等价的默认比较函数
less<T>
用 operator <
template <class T>
struct less : binary_function <T,T,bool>
{
bool operator() (const T& x, const T& y) const
{ return x < y; }
};
6 非排序关联容器 非标准的hashtable, 2种设计: 基于相等/基于等价
item20: 为指针/智能指针/迭代器 (行为像指针) 关联容器指定/自定义比较类型
总结
(1) 指针关联容器, 想按指针所指对象的值 排序, 必须自定义比较函数functor: 以 string* 为参数, 按指针所指的string值排序
(2) 智能指针/迭代器 关联容器, 本节的方法同样适用
1*iter 是指向string的指针 => set 按指针的值 排序
set<string*> pStrSet;
// <=>
set<string*, less<string*> > pStrSet;
// <=>
set<string*, less<string*>, allocator<string*> > pStrSet; // 这里不考虑分配器
set<string*> pStrSet;
pStrSet.insert("abc");
pStrSet.insert("bcd");
for(set<string*>::const_iterator iter = pStrSet.begin();
iter != pStrSet.end();
++iter)
cout << *iter << endl;
2 自定义 string指针关联容器 比较函数functor
struct StringPtrDereferenceLess
: public binary_function<const string*, const string*, bool> // item40
{
bool
operator()(const string* lhs, const string* rhs) const
{
return *lhs < *rhs;
}
};
typedef set<string*, StringPtrDereferenceLess> StringPtrSet;
StringPtrSet stringPtrSet;
// ...
(1) 手工循环
for(StringPtrSet::const_iterator iter = stringPtrSet.begin();
iter != stringPtrSet.end();
++iter)
cout << **iter << endl; // **iter 才是 string* 所指的 string 对象
(2) 明显隐含循环的算法
void print(const string* ps)
{
cout << *ps << endl;
}
for_each(stringPtrSet.begin(), stringPtrSet.end(), print);
(3) 算法的操作参数泛化 为 解除(指针)引用的functor, 并改用明显隐含循环的 算法 transform 配合 输出流迭代器 ostream_iterator 联用
struct Dereference
{
template<typename T>
const T&
operator()(const T* ptr) const
{
return *ptr;
}
};
// 指针容器中元素(指针)经 transform 第4(操作)参数转换(解引用)一下变为指针所指(string)对象
// => ostream_iterator 模板形参为所要打印的对象类型 string
transform(stringPtrSet.begin(), stringPtrSet.end(),
ostream_iterator<string>(std::cout, "\n"), // 输出区间迭代器
Dereference() );
Note: copy 不能直接用, 否则, 打印出的是容器中元素值, 即指针值(string*) -> 用 transform 的第4(操作)参数转换(解引用)一下, 变为指针所指(string)对象
// ostream_iterator 模板形参为所要打印的对象类型 string*
copy(stringPtrSet.begin(), stringPtrSet.end(),
ostream_iterator<string*>(cout, "\n") );
Note: 输出流迭代器 ostream_iterator 需要知道所要打印的对象类型
template <class T, // T: 所要输出的对象类型
class charT=char,
class traits=char_traits<charT> >
class ostream_iterator;
// Ctor: 第2参数为分隔符
ostream_iterator (ostream_type& s
[,const char_type* delimiter]);
3 2的泛化: 自定义 指针关联容器 比较函数functor
// 不考虑配接性
struct PtrDereferenceLess
{
template<typename T>
bool
operator()(const T* lhs, const T* rhs) const
{
return *lhs < *rhs;
}
};
// <=> 不必用 const PtrType lhs, const PtrType rhs
struct PtrDereferenceLess
{
template<typename PtrType>
bool
operator()(PtrType lhs, PtrType rhs) const
{
return *lhs < *rhs;
}
};
typedef set<string*, PtrDereferenceLess> StringPtrSet;
item21: 总是让比较函数在 等keyPart值(也应该等价)情况下返回false
原因: 等价 未必(即 =/>) keyPart值相等; 等keyPart值 必然(即=>) 等价 (否则, 会破坏non-multi容器keyPart值的唯一性; 破坏multi容器的排序规则, 进而弄错成员函数(如 equal_range)的判断结果(本应基于等keyPart值的元素等价) ) => 此时, 比较函数应返回false, 表示两者 没有先后 排列顺序
1 例: less_equal(即 <= ) 作 set 的比较类型 -> 判断出 2个等值元素不等价
=> 不相同(允许第2个值插入 => 破坏set容器key值的唯一性) & 有排列顺序(不确定行为)
对2个值而言, 等价既决定是否有 排列顺序, 又决定是否 相同: 等价时 无排列顺序 且 相同
set<int, less_equal<int> > s;
s.insert(10);
s.insert(10);
// 两个等值(10)元素: 10_L / 10_R, 判是否等价
!(10_L <= 10_R) && !(10_R <= 10_L)
// 即
false && false == false => 不等价 <=> 不相同
2 如何快速确定比较函数是否有错: 若对等值(==)返回true, 则比较函数有错
错: !( 左 < 右 ) <=> >=
对: 右 < 左
struct StringPtrDereferenceGreator
: public binary_function<const string*, const string*, bool>
{
bool
operator()(const string* lhs, const string* rhs) const
{
return !(*lhs < *rhs); // 旧的测试条件取反 -> 错
}
};
struct StringPtrDereferenceGreator
: public binary_function<const string*, const string*, bool>
{
bool
operator()(const string* lhs, const string* rhs) const
{
return *rhs < *lhs;
}
};
3 对 multiset/multimap, 虽然可以包含重复(等价)值, 但也应该保证等key值的元素等价
否则, 会 破坏容器的排序规则,进而 弄错 成员函数(如 equal_range)的判断结果(本应基于 等keyPart值的元素等价)
例: less_equal(即 <= ) 作 multiset/multimap 的比较类型
调 equal_range 得1对迭代器, 定义的区间包含等价值, 不会如我们期望的那样 包含2个等keyPart值的元素(10_L/10_R 不等价)`
multiset<int, std::less_equal<int> > s;
s.insert(10);
s.insert(10);
// std::pair<std::multiset<int>::iterator, std::multiset<int>::iterator>
auto bounds = equal_range(s.begin(), s.end(), 10)
std::cout << "bounds at pos " << (bounds.first - v.begin() );
std::cout << " and " << (bounds.second - v.begin() ) << '\n';
4 对关联容器排序的比较函数必须为它们所比较的对象 定义一个 "严格的弱序化"(strict weak ordering), 必须在 等keyPart值下返回false
item22: 切勿直接修改 set或multiset中keyPart的值
1 对标准关联容器, keyPart的值是否可以被直接修改 ？
keyPart: 对set/multiset是T类型元素的keyPart, 对map/multimap就是key
(1) 对 map/multimap而言, 第1模板形参类型为K时, 键(key)的类型是const K(常量类型) =>
编译器保证 keyPart不能被直接修改
map/multimap<K, V>
元素类型是 pair<const K, V>
键(key)的类型是 常量类型(const K)
(2) 对 set/multiset而言, 第1模板形参类型(是 元素类型)为T时, 键(key)/元素的类型是T,keyPart的类型是T中决定容器排列顺序(保证容器行为正确)的1个部分 =>
keyPart的值被直接修改(编译器允许)时, 会破坏容器(的排序性, 进而破坏容器的正确行为) => 必须避免;
但当key(键)/元素的 non-KeyPart值 被直接修改(编译器允许)时, 能保证容器正确性
set/multiset<T>
同样的逻辑是否可以用于map/multimap中的keyPart?
答: 理论上可以, 但C++标准不允许
例: 修改set/multiset元素值而不修改keyPart值的例子
class Employee
{
private:
int id; // keyPart
std::string title; // 头衔, nonkeyPart => 被修改是合理的
};
struct IDLess
: public binary_function<Employee, Employee, bool>
{
bool
operator()(const Employee& lhs, const Employee& rhs )
{
return lhs.getId() < rhs.getId();
}
};
typedef set<Employee, IDLess> EmpIdSet;
EmpIdSet empIdSet;
2 是否可以间接修改关联容器key的nonKeyPart的值: 可以
(1)对set/multiset, 正确且可移植的做法
用 const_cast<non-const T 引用>, 即 const_cast<T &> 强转掉 key值本身(而不能是copy)的常量性(constness)
set/multiset
const_cast<T &>
auto iter = empIdSet.find(targetElem);
if(iter != empIdSet.end() )
const_cast<T &>(*iter).setTitle("Leader");
(2)对map/multimap, 因为元素 pair<const K, V> 的第一部分是const, 上述做法将导致未定义结果
map/multimap
const_cast<K &>
(3) 对4种关联容器均安全可移植的方法
[1] 找到 想修改的元素, 记录返回的迭代器作为后续insert的hint(提示), 以将插入的效率从对数时间提高到常数时间
找到: 最优办法见 item45)
[2] 构造1份 non-const 拷贝
[3] 修改该拷贝的 nonKeyPart
[4] 删除元素, 通常用erase
[5] 用带hint的insert, 插入修改后copy
keyPart 不变 => 顺序相同 => 插入的位置与原被删除的位置`相同或紧邻
相同: set/mutiset
紧邻: map/multimap
EmpIdSet empIdSet;
Employee targetElem;
// ...
EmpIdSet::iterator iter = empIdSet.find(targetElem);
if(iter != empIdSet.end() )
{
Employee eCopy(*iter);
eCopy.setTitle("leader");
se.erase(iter++);
se.insert(iter, eCopy); // 插入的位置与原来相同
}
3 尽管 set/multiset的元素不是const, 但STL实现有办法防止它们被修改; 对此, C++标准没有统一要求
方法: 迭代器解引用后返回const引用
set<T>::iterator 的 operator* 返回 const T&
4 试图直接修改set/multiset元素的代码不可移植
如果你重视可移植性, 就不要这么做
item23: 考虑用排序的vector替代关联容器
3类容器适用场景
查找速度
hash容器 > 排序的vector > 标准关联容器
1 hash容器
适用场景: 无序
2 排序的vector
(1) 适用场景: 同一类操作([1] 插/删 [2] 查找 [3] 改值 <=> 删+插 ) 集中于同一阶段 => 3个主要阶段
[1] 设置: 插/删
[2] 查找
[3] 重组 改值 <=> 删+插
(2) 时空性能 可能比关联容器好, 原因:
[1] 排序的vector可用二分查找算法 binary_search/lower_bound/equal_range 等(item34/item45), 保证了与关联容器相近的对数查找时间
[2] 为什么比关联容器时空性能好 ?
1] 每个元素的size小, 无需prev/next/parent指针
2] 局部性: 连续内存 => 内存页错误 少, 且内存集中 => 二分查找更快
(3) 排序的vector替换map/multimap时, 必须去掉 map/multimap元素pair<const K, V>的第1元素的const, 换成pair<K, V>
原因: 排序时, vector元素通过赋值被移动 => pair的2个部分都必须是可被赋值
(4) 需要2个比较函数: 本质都基于key/K类型, 但接口不同
[1] 排序比较函数: 2个参数都是 pair
[2] 查找比较函数: 2个参数1个是 pair, 1个是 K 类型
typedef pair<string, int> strIntPair;
class DataCmp
{
public:
bool
operator()(const strIntPair& lhs,
const strIntPair& ) const // 排序用
{
return keyLess(lhs.first, rhs.first);
}
bool
operator()(const strIntPair& lhs,
const strIntPair::first_type& k) const // 查找用, 形式1
{
return keyLess(lhs.first, k);
}
bool
operator()(const strIntPair::first_type&,
const strIntPair& rhs) const // 查找用, 形式2
{
return keyLess(k, rhs.first);
}
private:
bool
keyLess(const strIntPair::first_type& kLhs,
const strIntPair::first_type& kRhs) const // 公共比较函数
{
return kLhs < kRhs;
}
};
3 标准关联容器
(1) 适用场景: 没法预测下一个操作是什么
(2) 性能好的原因: STL实现对插/删/查找混合操作做了优化
item24: 效率至关重要时, 请在map::operator[]与map::insert之间谨慎选择
1 map的下标函数 operator[]与众不同, 设计目的是为了提供 "添加(key不存在) 或 更新(key存在)"
m[k] = v;
// <=>
m.operator[](k) = v;
检查 键k是否已经在map中, 若否, 则添加 元素pair(k, v); 若是, 则更新 k关联的value为v
具体实现: 2步
[1] operator[]返回引用, 指向k关联的value, k不在map/multimap中时, 构造value类型的默认对象返回
[2] v 被赋值给引用所指的对象
1 添加时, insert比下标operator[]高效: 下标operator[] 多了临时对象的构造、析构和v的赋值
(1) 用 operator[] 添加
m[k] = v;
<=>
typedef map<K, V> KVMap;
// step1
pair<KVMap::iterator, bool> hintPair =
m.insert(KVMap::value_type(k, V() ) );
// step2
hintPair.first->second = v; // Note: hintPair.first 即 pair<K, V> 的 iter
KVMap::value_type 是 pair<K, V>
(2) 用 insert 添加
m.insert(KVMap::value_type(k, v) );
2 更新, 形势好反: 下标操作不需要构造/析构 pair<K, V>及其中的 K 和 V
(1) 用 operator[] 更新
m[k] = v; // 用 operator[] 更新
(2) 用 insert() 更新
m.insert(KVMap::value_type(k, v) ).first->second = v; // 用 insert() 更新
Note: m.insert(KVMap::value_type(k, v) ) 应该就够了, .first->second = v; 多余
3 STL最好提供(但没有)1个函数, 实现高效添加和更新
efficientAddOrUpdate(m, k, v)
思想: m.lower_bound(k) 返回的迭代器:
[1] 所指pair的key与k是/否等价 => k 是/否在m中 => 更新/insert
[2] 表明 可插入k的 第1个位置 => 等价区间的 前闭端
template<typename MapType,
typename K,
typename V>
typename MapType::iterator
efficientAddOrUpdate(MapType& m, const K& k, const V& v)
{
// 可插入 k的 第1个位置 => 等价区间的 前闭端
typename MapType::iterator lb =
m.lower_bound(k); // => !(m.key_comp()(lb->first, k) )
if(lb != m,end() &&
!(m.key_comp()(k, lb->first) ) ) // 与上一条语句结果接结合
{ // => lb 指向的pair的key 与 k等价 => k 在 m中
lb->second = v; // 与 map::operator[] 效果相似, 但更高效
return lb;
}
else // 与 map::insert( MPair(k, v) ) 效果相似, 返回值不同
{
typedef typename MapType::value_type MPair;
return m.insert(lb, MPair(k, v) );
}
}
4 map::insert 3中形式3种返回值: pair/iterator/void
pair<iterator,bool>
insert (const value_type& val);
iterator
insert (iterator position,
const value_type& val);
template <class InputIterator>
void
insert (InputIterator first, InputIterator last);
