3.STL Associative Containers and Iterators

Associative Containers

• 没有顺序的概念
• 使用key而非index访问数据。
• 包括以下四种：
  • std::map<T1,T2>
  • std::set<T>
  • std::unordered_map<T1,T2>
  • std::unordered_set<T>

其中，std::map<T1,T2>和std::set<T>的key需要能够使用<来比较大小。

std::unordered_map<T1,T2>和std::unordered_set<T>则基于哈希，需要定义key的哈希函数。

map

map支持的几种操作：

• 插入k-v对
• 删除k-v对
• 检查一个特定的key是否存在
• 给定key，查询对应的value

插入k-v对

1. 使用方括号向map中插入k-v对：

map<string, int> numberMap;
// Indexing into a map into a nonexistent key implicitly creates a key/value pair.
numberMap["zero"] = 0; 
numberMap["one"] = 1;
numberMap["two"] = 2;

2. 使用insert插入k-v对

map<string, int> numberMap;
numberMap.insert(make_pair("zero", 0));
numberMap.insert(make_pair("one", 1));
numberMap.insert(make_pair("two", 2));

使用insert和[]的区别：

如果尝试使用insert函数将k-v对插入到map中，而该key已经存在，则map将不会插入k-v对，也不会更新与现有key关联的value。

/* Populate a map using [ ] */
map<string, string> one;
one["C++"] = "sad";
one["C++"] = "happy";  // one["C++"] == "happy"

/* Populate a map using insert */
map<string, string> two;
two.insert(make_pair("C++", "sad"));
two.insert(make_pair("C++", "happy")); // one["C++"] == "sad"

map的insert函数返回一个类型为<iterator, bool>的pair值。

pair中的bool值表示插入操作是否成功。结果为true表示k-v对已添加，结果为false表示key已经存在。

pair中迭代器指向映射中的k-v对。如果k-v对是新添加的，则该迭代器指向新插入的k-v对；如果k-v对已经存在，则迭代器指向阻止操作的现有k-v对。

因此，可以这样使用insert插入k-v对：

/* Try to insert normally. */
pair<map<string, int>::iterator, bool> result = myMap.insert(make_pair("STL", 137));
/* If insertion failed, manually set the value. */
if (!result.second)
    result.first->second = 137;

删除k-v对

myMap.erase("key");

检查特定的key是否存在

1. 使用count成员函数

if (myMap.count(key) == 0) 
    cout << “Not Found”;

2. 使用std::find()

if (find(myMap.begin(), myMap.end(), key) == myMap.end())
    cout << “Not Found”;

count实际上只是对find函数的调用。所以find稍微快一点。

给定key，查询对应的value

1. 使用[]

cout << numberMap["xyzzy"] << endl;

2. 使用.at成员函数

cout << myMap.at(1) << endl;

两者的区别：

若给定的key不存在，[]则会隐式的创建k-v对，以给定key为键，值为默认值。

若给定的key不存在，使用.at查询时则会报错。

例子：

std::map<int, std::string> myMap;
myMap[1] = "One";
cout << myMap.at(1) << endl; // 输出： "one"
cout << myMap.at(2) << endl; // 抛出 std::out_of_range 异常
cout << myMap[2] << endl;    // 输出空字符串

Set

• set是没有value的map的一种特殊情况。
  • 对应的value为true（若key存在），为false（若key不存在）。

举例：

set<int> mySet;
mySet.insert(137); // Now contains: 137
mySet.insert(42);  // Now contains: 42 137
mySet.insert(137); // Now contains: 42 137,没有改变集合的内容。集合不允许重复元素。

if (mySet.count(137)) //.count用于检查元素是否存在于集合中
    cout << "137 is in the set." << endl; // Printed
if (!mySet.count(500))
    cout << "500 is not in the set." << endl; // Printed
    
mySet.erase(137); // Removes 137, if it exists.

Iterator

每个容器以不同的格式存储其数据，迭代器为访问存储在容器中的数据提供了一种干净、一致的机制，而不管这些数据是如何存储的。

Every STL container class exports a member function begin() which yields an iterator pointing to the first element of that container.

Each STL container exports a special function called end() that returns an iterator to the element one past the end of the container.

使用迭代器遍历容器：

vector<int> myVector = /* ... some initialization ... */ 
for (vector<int>::iterator itr = myVector.begin(); 
     itr != myVector.end(); ++itr)
    cout << *itr << endl;

迭代器的美妙之处在于它们可以在任何STL容器上工作，包括set。

set<int> mySet = /* ... some initialization ... */
for (set<int>::iterator itr = mySet.begin(); 
     itr != mySet.end(); ++itr)
    cout << *itr << endl;

迭代器的用法不止有遍历元素。例如：

排序：

std::sort(vec.begin(), vec.end());

搜索：

const int elemToFind = 5; 
vector::iterator it = std::find(vec.begin(),  vec.end(), elemToFind);
if(it != vec.end()) { 
    cout << "Found: " << *it << endl; 
} else { 
    cout << "Element not found!" << endl; 
} 

确定范围：

单个迭代器指向容器类中的单个位置，并表示间接读取或写入该值的方法。

一对迭代器定义了两个位置，从而定义了一个元素范围。

set中提供了两个成员函数：

• lower_bound：接受一个值，然后返回一个迭代器，指向集合中第一个大于或等于该值的元素。
• upper_bound：接受一个值，返回一个迭代器，指向集合中第一个严格大于该值的元素。

// iterates over all elements in the set in the range [10, 100]
set<int>::iterator stop = mySet.upper_bound(100);
for (set<int>::iterator itr = mySet.lower_bound(10); itr != stop; ++itr)
    /* ... perform tasks... */

range based for loop的本质就是使用迭代器访问的简写：

// range based for loop
map<string, int> myMap;
for(auto thing : myMap) {
    doSomething(thing.first, thing.second);
}

// 本质：
map<string, int> myMap;
for(auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
    auto thing = *iter;
    doSomething(thing.first, thing.second);
}

Map Iterators

• map的迭代器略有不同，因为map同时拥有key和value。
• 如果解引用一个map<KeyType, ValueType>的迭代器，会得到一个类型为pair<const KeyType, ValueType>的pair

先看看pair：

pair<int, string> myPair;
myPair.first = 137; 
myPair.second = "C++ is awesome!";

pair<int, string> myPair = make_pair(137, "string!");  // create a pair on-the-fly

map迭代器的使用举例：

map<int, int> m;
map<int, int>::iterator i = m.begin();
map<int, int>::iterator end = m.end();
while(i != end) {
    cout << (*i).first << (*i).second << endl;
    ++i;
}

Iterator Types

一些看似很合理的使用迭代器的方法：

std::vector v(10); 
auto mid = v.begin() + v.size()/2;

std::deque d(13); 
auto some_iter = d.begin() + 3;

但如果对std::list（双向链表）执行上述操作就会报错：

这是由迭代器的类型导致的。

迭代器有5种类型：

所有类型的迭代器都有一些共同的特征:

• 可以从已有的迭代器中创建
• 可以使用++
• 可以使用==和!=比较

其余特征则取决于迭代器的类型：

Input Iterators

只读，即只能在表达式的右侧解引用。

vector<int> v = ... 
vector<int>::iterator itr = v.begin(); 
int val = *itr; 
*itr = 12; // 错误！

Output Iterators

只能写，即只能在表达式的左侧解引用。

vector<int> v = ... 
vector<int>::iterator itr = v.begin(); 
*itr = 12;
int val = *itr;  // 错误！！

Forward Iterators

可以读写以及++

vector<int> v = ... 
vector<int>::iterator itr = v.begin(); 
*itr = 12;
int val = *itr; 

Bidirectional Iterators

与Forward Iterators相同且可以--

vector<int> v = ... 
vector<int>::iterator itr = v.begin(); 
++itr; 
int val = *itr; 
--itr; 
int val2 = *itr; 

Random Access Iterators

和Bidirectional Iterators相同且可以使用+和-任意递增或递减

vector<int> v = ... 
vector<int>::iterator itr = v.begin(); 
itr += 3;
int val = *itr; 

invalidated iterators

例1：

修改后：

例2：

修改：

Multicontainers

multimap：一个key可以有多个不同的value。

multiset：可以包含多个key。

与普通版本的区别：

• count函数将返回容器中元素的实际数量，而不仅仅是二进制0或1。
• find函数仍然会返回迭代器，但它所指向的元素不能保证是该元素在容器中的唯一副本。
• erase将擦除指定键或元素的所有副本。
• 在multimap中不存在方括号，需要使用insert函数插入k-v对
• equal_range，返回一对<iterator, iterator>对象，表示容器中等于指定值的成员的范围，例如：

multimap<string, int> myMultiMap;
/* Store the result of the equal_range */
pair<multimap<string, int>::iterator, multimap<string, int>::iterator>
    myPair = myMultiMap.equal_range("STL");
/* Iterate over it! */
multimap<string, int>::iterator itr;
for(itr = myPair.first; itr != myPair.second; ++itr)
   cout << itr->first << ": " << itr->second << endl;

多容器在实践中相当少见，部分原因是它们可以很容易地使用其他方法来模拟。

例如，multimap<string, int>的行为类似于map<string, vector<int> >，因为两者都是将字符串映射到一定数量的int。