part3 關(guān)聯(lián)容器
與序列容器區(qū)別
(1) 自動(dòng)排序
(2) 比較是按照等價(jià)(equivalence)而不是相等(equality)
(3) set/map 不允許有重復(fù)
key points
(1) 等價(jià)的概念
(2) 比較函數(shù)的限制
(3) 指針關(guān)聯(lián)容器, 要自定義比較函數(shù)
(4) 鍵的常量性(constness)的官方含義和實(shí)際含義
(5) 關(guān)聯(lián)容器提高效率的建議
item19: 理解相等(equality)和等價(jià)(equivalence)的區(qū)別
1 STL中經(jīng)常需要比較2個(gè)對(duì)象, 判斷它們的值是否相同
2個(gè)代表性的函數(shù)算法find()和成員函數(shù)set::insert()對(duì)"相同"的定義不同: 相等和等價(jià), 分別基于 operator== 和 operator<
關(guān)聯(lián)容器所有成員函數(shù)(set::insert 和set::find()等)對(duì)相同的定義相同
相等并不一定意味所有數(shù)據(jù)成員都相等, 通常只關(guān)注某個(gè)字段
等價(jià)以"在已排序區(qū)間中對(duì)象值的相對(duì)排列順序"為基礎(chǔ)
2 為什么標(biāo)準(zhǔn)關(guān)聯(lián)容器是基于等價(jià)而不是相等
例: 不區(qū)分大小寫的 set<string, CIStringCompare[, equal_to<string> ] >, 決定排列順序/是否等價(jià)的比較函數(shù) 忽略 字符串中字符大小寫
item35: 實(shí)現(xiàn)了這樣的函數(shù) ciStringCompare, 不區(qū)分大小寫的比較
但 set 需要一個(gè)`比較函數(shù)類型/functor`, 其 operator() 調(diào)用 ciStringCompare
struct CIStringCompare
: public binary_function <string, string, bool> // item40: 提供可配接能力
{
bool
operator()(const string& lhs, const string& rhs)
{
return ciStringCompare(lhs, rhs); // item35, 忽略大小寫的字符串比較函數(shù)
}
};
標(biāo)準(zhǔn)關(guān)聯(lián)容器自動(dòng)排序, 所以必須用1個(gè)比較函數(shù)(默認(rèn)為std::less)來決定 如何排序/排列順序
(1) 若基于相等 判2個(gè)元素是否"相同", 則關(guān)聯(lián)容器需要2個(gè)比較函數(shù): 一個(gè)用于 排序(判/決定 2個(gè)值 的排列順序/是否等價(jià)), 另一個(gè)用于 判相同(判/決定 2個(gè)值是否 相同/允許插入 )
-> 對(duì)non-multi容器(set/map)帶來非常直觀的混亂或錯(cuò)誤
1)混亂: 成員函數(shù)實(shí)現(xiàn)可能基于相等, 這與正確的容器行為違背
2)錯(cuò)誤: 破壞non-multi容器(set/map)keyPart值的唯一性(非重性); 會(huì)破壞multi容器(multiset/multimap)的排序規(guī)則
[1]
set<string, CIStringCompare, equal_to<string> > set2CF;
| |
| |
決定 排列順序 決定 (key)值是否相同 => 決定是否允許插入
set2CF.insert("Abc");
set2CF.insert("abc");
CIStringCompare
"Abc" 與 "abc" 等價(jià)(無排列順序) => 后者不應(yīng)該被插入, 以保持容器的排序性
equal_to<string>
"Abc" 與 "abc" 不相等 => 不相同 => 后者可以插入
1) 假設(shè)實(shí)現(xiàn)保持了排序性, 后者沒插入
成員函數(shù) 理應(yīng)基于排序性/等價(jià)
=> if(set2CF.find("abc") != set2CF.end() ) // find 成功
但`成員函數(shù)find可能基于 相等`
=> if(set2CF.find("abc") != set2CF.end() ) // find 失敗
=> 混亂
2) 假設(shè)實(shí)現(xiàn)允許后者插入 => `破壞`non-multi容器(set/map)key值的唯一性(非重性)`
[2] 上述換為 multiset
equal_to<string>
"Abc" 與 "abc" 不相等 => 不相同 => 后insert的"abc"插入
CIStringCompare
"Abc" 與 "abc" 等價(jià) => 排列順序(誰在前)不限定/不確定
=> `不能以確定的順序遍歷容器的元素`
假定 "abc" 在 "Abc" 前
`成員函數(shù)find可能基于 相等`
=> if(multiSet2CF.find("abc") != multiSet2CF.end() ) // find 成功
(2) 若基于等價(jià) 判2個(gè)元素是否"相同", 則關(guān)聯(lián)容器只需1個(gè)比較函數(shù): 既用于 排序(判2個(gè)值 的排列順序/是否等價(jià)), 又用于 判相同(判/決定 2個(gè)值是否 相同/允許插入 )
set<string, CIStringCompare> cisSet;
cisSet.insert("Abc");
cisSet.insert("abc"); // "abc" 與 "Abc" 等價(jià) => 相同 => "abc" 不被插入
if(cisSet.find("abc") != cisSet.end() ) // set::find 基于等價(jià) => find 成功
if( find(cisSet.begin(), cisSet.end(), "abc" )
!= cisSet.end() ) // 算法 find() 基于相等 => find 失敗
=> 優(yōu)先選擇成員函數(shù)(如 std::find) 而不是相應(yīng)的非成員函數(shù)/算法(如 find)
3 等價(jià)的含義: 兩個(gè)值(按指定的比較函數(shù)/排序準(zhǔn)則)任一個(gè)都不在另一個(gè)的前面, 則這兩個(gè)值(按該比較函數(shù)/排序準(zhǔn)則)等價(jià)
默認(rèn) operator<
!(w1 < w2) && !(w2 < w1) // w1 < w2 不為真, 且 w2 < w1 不為真
client 如何知道2個(gè)對(duì)象是否等價(jià)? 答: 用關(guān)聯(lián)容器的成員函數(shù)key_comp
默認(rèn) less == key_comp
// 在容器c的排列順序中, w1在w2之前不為真, w2在w1之前也不為真
!c.key_comp()(w1, w2) && !c.key_comp()(w2, w1) // key_comp()返回1個(gè)函數(shù)對(duì)象實(shí)例
w1不在w2之前 => c.key_comp()(w1, w2)為false => !c.key_comp()(w1, w2)為true
4 關(guān)聯(lián)容器的比較函數(shù)
[1] 目的是判2個(gè)元素的key值(對(duì)set/map, 也是value值/只是key值)是否相同
[2] 決定排列順序/排序準(zhǔn)則
5 基于等價(jià)的默認(rèn)比較函數(shù)
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 非排序關(guān)聯(lián)容器 非標(biāo)準(zhǔn)的hashtable, 2種設(shè)計(jì): 基于相等/基于等價(jià)
item20: 為指針/智能指針/迭代器 (行為像指針) 關(guān)聯(lián)容器指定/自定義比較類型
總結(jié)
(1) 指針關(guān)聯(lián)容器, 想按指針?biāo)笇?duì)象的值 排序, 必須自定義比較函數(shù)functor: 以 string* 為參數(shù), 按指針?biāo)傅膕tring值排序
(2) 智能指針/迭代器 關(guān)聯(lián)容器, 本節(jié)的方法同樣適用
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指針關(guān)聯(lián)容器 比較函數(shù)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) 手工循環(huán)
for(StringPtrSet::const_iterator iter = stringPtrSet.begin();
iter != stringPtrSet.end();
++iter)
cout << **iter << endl; // **iter 才是 string* 所指的 string 對(duì)象
(2) 明顯隱含循環(huán)的算法
void print(const string* ps)
{
cout << *ps << endl;
}
for_each(stringPtrSet.begin(), stringPtrSet.end(), print);
(3) 算法的操作參數(shù)泛化 為 解除(指針)引用的functor, 并改用明顯隱含循環(huán)的 算法 transform 配合 輸出流迭代器 ostream_iterator 聯(lián)用
struct Dereference
{
template<typename T>
const T&
operator()(const T* ptr) const
{
return *ptr;
}
};
// 指針容器中元素(指針)經(jīng) transform 第4(操作)參數(shù)轉(zhuǎn)換(解引用)一下變?yōu)橹羔標(biāo)?string)對(duì)象
// => ostream_iterator 模板形參為所要打印的對(duì)象類型 string
transform(stringPtrSet.begin(), stringPtrSet.end(),
ostream_iterator<string>(std::cout, "\n"), // 輸出區(qū)間迭代器
Dereference() );
Note: copy 不能直接用, 否則, 打印出的是容器中元素值, 即指針值(string*) -> 用 transform 的第4(操作)參數(shù)轉(zhuǎn)換(解引用)一下, 變?yōu)橹羔標(biāo)?string)對(duì)象
// ostream_iterator 模板形參為所要打印的對(duì)象類型 string*
copy(stringPtrSet.begin(), stringPtrSet.end(),
ostream_iterator<string*>(cout, "\n") );
Note: 輸出流迭代器 ostream_iterator 需要知道所要打印的對(duì)象類型
template <class T, // T: 所要輸出的對(duì)象類型
class charT=char,
class traits=char_traits<charT> >
class ostream_iterator;
// Ctor: 第2參數(shù)為分隔符
ostream_iterator (ostream_type& s
[,const char_type* delimiter]);
3 2的泛化: 自定義 指針關(guān)聯(lián)容器 比較函數(shù)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: 總是讓比較函數(shù)在 等keyPart值(也應(yīng)該等價(jià))情況下返回false
原因: 等價(jià) 未必(即 =/>) keyPart值相等; 等keyPart值 必然(即=>) 等價(jià) (否則, 會(huì)破壞non-multi容器keyPart值的唯一性; 破壞multi容器的排序規(guī)則, 進(jìn)而弄錯(cuò)成員函數(shù)(如 equal_range)的判斷結(jié)果(本應(yīng)基于等keyPart值的元素等價(jià)) ) => 此時(shí), 比較函數(shù)應(yīng)返回false, 表示兩者 沒有先后 排列順序
1 例: less_equal(即 <= ) 作 set 的比較類型 -> 判斷出 2個(gè)等值元素不等價(jià)
=> 不相同(允許第2個(gè)值插入 => 破壞set容器key值的唯一性) & 有排列順序(不確定行為)
對(duì)2個(gè)值而言, 等價(jià)既決定是否有 排列順序, 又決定是否 相同: 等價(jià)時(shí) 無排列順序 且 相同
set<int, less_equal<int> > s;
s.insert(10);
s.insert(10);
// 兩個(gè)等值(10)元素: 10_L / 10_R, 判是否等價(jià)
!(10_L <= 10_R) && !(10_R <= 10_L)
// 即
false && false == false => 不等價(jià) <=> 不相同
2 如何快速確定比較函數(shù)是否有錯(cuò): 若對(duì)等值(==)返回true, 則比較函數(shù)有錯(cuò)
錯(cuò): !( 左 < 右 ) <=> >=
對(duì): 右 < 左
struct StringPtrDereferenceGreator
: public binary_function<const string*, const string*, bool>
{
bool
operator()(const string* lhs, const string* rhs) const
{
return !(*lhs < *rhs); // 舊的測(cè)試條件取反 -> 錯(cuò)
}
};
struct StringPtrDereferenceGreator
: public binary_function<const string*, const string*, bool>
{
bool
operator()(const string* lhs, const string* rhs) const
{
return *rhs < *lhs;
}
};
3 對(duì) multiset/multimap, 雖然可以包含重復(fù)(等價(jià))值, 但也應(yīng)該保證等key值的元素等價(jià)
否則, 會(huì) 破壞容器的排序規(guī)則,進(jìn)而 弄錯(cuò) 成員函數(shù)(如 equal_range)的判斷結(jié)果(本應(yīng)基于 等keyPart值的元素等價(jià))
例: less_equal(即 <= ) 作 multiset/multimap 的比較類型
調(diào) equal_range 得1對(duì)迭代器, 定義的區(qū)間包含等價(jià)值, 不會(huì)如我們期望的那樣 包含2個(gè)等keyPart值的元素(10_L/10_R 不等價(jià))`
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 對(duì)關(guān)聯(lián)容器排序的比較函數(shù)必須為它們所比較的對(duì)象 定義一個(gè) "嚴(yán)格的弱序化"(strict weak ordering), 必須在 等keyPart值下返回false
item22: 切勿直接修改 set或multiset中keyPart的值
1 對(duì)標(biāo)準(zhǔn)關(guān)聯(lián)容器, keyPart的值是否可以被直接修改 炉旷？
keyPart: 對(duì)set/multiset是T類型元素的keyPart, 對(duì)map/multimap就是key
(1) 對(duì) map/multimap而言, 第1模板形參類型為K時(shí), 鍵(key)的類型是const K(常量類型) =>
編譯器保證 keyPart不能被直接修改
map/multimap<K, V>
元素類型是 pair<const K, V>
鍵(key)的類型是 常量類型(const K)
(2) 對(duì) set/multiset而言, 第1模板形參類型(是 元素類型)為T時(shí), 鍵(key)/元素的類型是T,keyPart的類型是T中決定容器排列順序(保證容器行為正確)的1個(gè)部分 =>
keyPart的值被直接修改(編譯器允許)時(shí), 會(huì)破壞容器(的排序性, 進(jìn)而破壞容器的正確行為) => 必須避免;
但當(dāng)key(鍵)/元素的 non-KeyPart值 被直接修改(編譯器允許)時(shí), 能保證容器正確性
set/multiset<T>
同樣的邏輯是否可以用于map/multimap中的keyPart?
答: 理論上可以, 但C++標(biāo)準(zhǔn)不允許
例: 修改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 是否可以間接修改關(guān)聯(lián)容器key的nonKeyPart的值: 可以
(1)對(duì)set/multiset, 正確且可移植的做法
用 const_cast<non-const T 引用>, 即 const_cast<T &> 強(qiáng)轉(zhuǎn)掉 key值本身(而不能是copy)的常量性(constness)
set/multiset
const_cast<T &>
auto iter = empIdSet.find(targetElem);
if(iter != empIdSet.end() )
const_cast<T &>(*iter).setTitle("Leader");
(2)對(duì)map/multimap, 因?yàn)樵?pair<const K, V> 的第一部分是const, 上述做法將導(dǎo)致未定義結(jié)果
map/multimap
const_cast<K &>
(3) 對(duì)4種關(guān)聯(lián)容器均安全可移植的方法
[1] 找到 想修改的元素, 記錄返回的迭代器作為后續(xù)insert的hint(提示), 以將插入的效率從對(duì)數(shù)時(shí)間提高到常數(shù)時(shí)間
找到: 最優(yōu)辦法見 item45)
[2] 構(gòu)造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實(shí)現(xiàn)有辦法防止它們被修改; 對(duì)此, C++標(biāo)準(zhǔn)沒有統(tǒng)一要求
方法: 迭代器解引用后返回const引用
set<T>::iterator 的 operator* 返回 const T&
4 試圖直接修改set/multiset元素的代碼不可移植
如果你重視可移植性, 就不要這么做
item23: 考慮用排序的vector替代關(guān)聯(lián)容器
3類容器適用場(chǎng)景
查找速度
hash容器 > 排序的vector > 標(biāo)準(zhǔn)關(guān)聯(lián)容器
1 hash容器
適用場(chǎng)景: 無序
2 排序的vector
(1) 適用場(chǎng)景: 同一類操作([1] 插/刪 [2] 查找 [3] 改值 <=> 刪+插 ) 集中于同一階段 => 3個(gè)主要階段
[1] 設(shè)置: 插/刪
[2] 查找
[3] 重組 改值 <=> 刪+插
(2) 時(shí)空性能 可能比關(guān)聯(lián)容器好, 原因:
[1] 排序的vector可用二分查找算法 binary_search/lower_bound/equal_range 等(item34/item45), 保證了與關(guān)聯(lián)容器相近的對(duì)數(shù)查找時(shí)間
[2] 為什么比關(guān)聯(lián)容器時(shí)空性能好 ?
1] 每個(gè)元素的size小, 無需prev/next/parent指針
2] 局部性: 連續(xù)內(nèi)存 => 內(nèi)存頁(yè)錯(cuò)誤 少, 且內(nèi)存集中 => 二分查找更快
(3) 排序的vector替換map/multimap時(shí), 必須去掉 map/multimap元素pair<const K, V>的第1元素的const, 換成pair<K, V>
原因: 排序時(shí), vector元素通過賦值被移動(dòng) => pair的2個(gè)部分都必須是可被賦值
(4) 需要2個(gè)比較函數(shù): 本質(zhì)都基于key/K類型, 但接口不同
[1] 排序比較函數(shù): 2個(gè)參數(shù)都是 pair
[2] 查找比較函數(shù): 2個(gè)參數(shù)1個(gè)是 pair, 1個(gè)是 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 // 公共比較函數(shù)
{
return kLhs < kRhs;
}
};
3 標(biāo)準(zhǔn)關(guān)聯(lián)容器
(1) 適用場(chǎng)景: 沒法預(yù)測(cè)下一個(gè)操作是什么
(2) 性能好的原因: STL實(shí)現(xiàn)對(duì)插/刪/查找混合操作做了優(yōu)化
item24: 效率至關(guān)重要時(shí), 請(qǐng)?jiān)?code>map::operator[]與map::insert之間謹(jǐn)慎選擇
1 map的下標(biāo)函數(shù) operator[]與眾不同, 設(shè)計(jì)目的是為了提供 "添加(key不存在) 或 更新(key存在)"
m[k] = v;
// <=>
m.operator[](k) = v;
檢查 鍵k是否已經(jīng)在map中, 若否, 則添加 元素pair(k, v); 若是, 則更新 k關(guān)聯(lián)的value為v
具體實(shí)現(xiàn): 2步
[1] operator[]返回引用, 指向k關(guān)聯(lián)的value, k不在map/multimap中時(shí), 構(gòu)造value類型的默認(rèn)對(duì)象返回
[2] v 被賦值給引用所指的對(duì)象
1 添加時(shí), insert比下標(biāo)operator[]高效: 下標(biāo)operator[] 多了臨時(shí)對(duì)象的構(gòu)造同规、析構(gòu)和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 更新, 形勢(shì)好反: 下標(biāo)操作不需要構(gòu)造/析構(gòu) 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) ) 應(yīng)該就夠了, .first->second = v; 多余
3 STL最好提供(但沒有)1個(gè)函數(shù), 實(shí)現(xiàn)高效添加和更新
efficientAddOrUpdate(m, k, v)
思想: m.lower_bound(k) 返回的迭代器:
[1] 所指pair的key與k是/否等價(jià) => k 是/否在m中 => 更新/insert
[2] 表明 可插入k的 第1個(gè)位置 => 等價(jià)區(qū)間的 前閉端
template<typename MapType,
typename K,
typename V>
typename MapType::iterator
efficientAddOrUpdate(MapType& m, const K& k, const V& v)
{
// 可插入 k的 第1個(gè)位置 => 等價(jià)區(qū)間的 前閉端
typename MapType::iterator lb =
m.lower_bound(k); // => !(m.key_comp()(lb->first, k) )
if(lb != m,end() &&
!(m.key_comp()(k, lb->first) ) ) // 與上一條語句結(jié)果接結(jié)合
{ // => lb 指向的pair的key 與 k等價(jià) => 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);
