STL

maltimap 和 map

栽自http://cplus.about.com/od/stltutorial/l/aa120103f.htm maltimap 的区别在于 maltimap 允许一个 key 对应多个 value ，而 map 不可以。

对于含有多个 value 的 key ，可以用下面的方式遍历所 有 value.

maltimap<string,float>::iterator it;
for(it= ml.lower_bound();it!=ml.upper_bound();it++){
  //...
}

#include <map>//The map include file is used for both map and multimap
#include <string>
#include <iostream>
using namespace std;
int main() {
   multimap<string,float> grades;

// Maps and multimaps deal with pairs
   pair<string,float> p1("John",85.6);
   pair<string,float> p2("John",23.6);
   pair<string,float> p3("John",60.0);
   pair<string,float> p4("Elmo",100.0);
   pair<string,float> p5("Elmo",98.7);
   pair<string,float> p6("Elmo",99.2);
   pair<string,float> p7("Oscar",15.1);
   pair<string,float> p8("Oscar",6.7);

// Insert grades into grades
   grades.insert(p1);
   grades.insert(p2);
   grades.insert(p3);
   grades.insert(p4);
   grades.insert(p5);
   grades.insert(p6);
   grades.insert(p7);
   grades.insert(p8);

// Iterators
   multimap<string,float>::iterator iter;
   multimap<string,float>::iterator lower;
   multimap<string,float>::iterator upper;

   lower = grades.lower_bound("John");
   upper = grades.upper_bound("John");

   float sum = 0.0;
   for (iter = lower; iter != upper; iter++) {
      sum += iter->second;
   }
   float avg = sum / grades.count("John");

   cout << "John's average is " << avg << endl;

   lower = grades.lower_bound("Elmo");
   upper = grades.upper_bound("Elmo");

   sum = 0.0;
   for (iter = lower; iter != upper; iter++) {
      sum += iter->second;
   }
   avg = sum / grades.count("Elmo");

   cout << "Elmo's average is " << avg << endl;

   lower = grades.lower_bound("Oscar");
   upper = grades.upper_bound("Oscar");

   sum = 0.0;
   for (iter = lower; iter != upper; iter++) {
      sum += iter->second;
   }
   avg = sum / grades.count("Oscar");

   cout << "Oscar's average is " << avg << endl;

   return 0;

}

John's average is 56.4
Elmo's average is 99.3
Oscar's average is 10.9
There are 0 entries for Oscar

判断一个 container 是否为空 size vs empty

一定要用 empty() , 而不是 size() != 0 ， 因为很 多容器 empty() 的算法复杂度都是 1 ， 而有些容器 的 size() 的算法复杂度是 O(n) 。

删除变量 erase vs clear

不要用 c.erase(c.begin(),c.end()) 代替 c.clear() ， 因为对于有些容器，前者要跟复杂一些。

it ++ vs ++ it

++it 要比 it++ 快一些，因为减少了 iterator 对象的拷贝构造函数。

容易错误使用的 map

下面的程序会出现 segment fault, 也就是内存非法访问。 因为没有注意到作为 map 的 key_type 必须是可以比较的。而且是可以长期存储的。

int main (int argc, char * argv[])
{
   map <const char * , int *> m;    //map <string , int *> m; 可以解决问题。
   char key[128];
   int i;

   for(i=0;i<10;i++){
      sprintf(key,"aa%d",i);
      m[key] = new int;
      *(m[key]) =i;
   }

   cout << *(m["aa2"]) << endl;

   return 0;
}

下面的程序的输出不是程序预想的结果，可以通过检查地址得到答案。

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

int main()
{
  // 原文中是  map<const char*, int, ltstr> months;
  map<const char*, int> months; //结果是很奇怪的。
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  cout << "june -> " << months["june"] << endl;
  cout << "june -> " << months[key] << endl;
  cout << "addr1:" << (void*)key << ";"
       << "addr2:" << (void*)"june" << ";"
       << "addr3:" << (void*) "june" << ";"
       << endl;

}