STL中lower_bound的应用

C++编程思想第二卷第六章讲解了STL算法相关的知识，学习了之后找来课后练习题6-33，原题是这样描述的，“编写一个程序，给定一个姓氏，找出每个有这样姓氏的人以及他或她的电话号码。使用处理序列范围的算法（例如upper_bound、lower_bound、equal_range等等），以姓氏作为主关键字，名字作为次关键字进行排序。假定从形式如下的文件中读入姓名及电话号码。
John Doe 3459483
Nick Bonham 3492930
Jane Doe 2832819”

这里用数组代替文件进行输入。看到这样的问题，思路是使用STL的MAP容器进行储存，原题说使用姓氏作为关键字，那我们不妨定义一个类Name储存姓氏信息，

class Name {
private:
    string familyName;
    string givenName;
public:
    Name(string FName = "", string GName = "") :
            familyName(FName), givenName(GName) {
    }
    virtual ~Name() {
    }
    const string& getFamilyName() const {
        return familyName;
    }
    const string& getGivenName() const {
        return givenName;
    }
}

其中有family name 和given name两个string类型的成员变量，分别用来存储姓氏和名字。而使用Name作为容器MAP的key我们还需要做一个很重要的事情，那就是重载运算符"<"，而且这个方法中一定不能写错，必须保证如果给定两个对象A跟B，如果有A < B为TRUE，则B < A一定为FALSE。重载代码如下，

bool operator <(const Name & rhs) const {
        if (familyName < rhs.familyName) {
            return true;
        } else if (familyName == rhs.familyName) {
            if (givenName < rhs.givenName)
                return true;
        }
        return false;
    }

遵循题目要求使用family name作为主关键字，我们首先比对family name，如果其相等再比对given name，注意这里方法的实现。

下面我们要考虑如何定义一个数据结构来表示人名和电话号码，我们考虑使用一个二维数组，方便起见对姓氏，名字以及电话号码都是用string类型进行表示，
 string NameArray[][3] =
 {{"John", "Doe",    "3459483" },
  { "Nick", "Bonham", "3492930" },
  { "Jane", "Doe",    "2832819" },
  { "Adam", "Clark",  "6518324" },
  { "Judy", "Foast",  "9821572" },
  { "Zeus", "Lenos",  "4552341" },
  { "Cole", "Minas",  "1351244" },
  { "Ooos", "Clark",  "1562553" } };
有了这些输入，我们就可以把它们读入到MAP容器中，进行操作，MAP容器的定义如下，
map infoMap;
往map中插入成员需要用到pair类型，这也不难理解，因为map中的元素都是成对出现的，因此插入的形式就是这样，
infoMap.insert(pair(name, number));
下面就是最后一步，查找。
使用键盘进行输入，从控制台可以输入一个姓氏，可以使用std::cin，代码像这样cin >> FamilyName。
输入之后首先要把输入的姓氏转化成一个完整的姓名，然后才能进行查找，由于我们之前定义的Name类的构造函数使用了默认空字符串作为默认参数，这样我们就可以直接用键盘输入的姓氏构造一个待查找的键值key,
  string aFmlyName;
  cin >> aFmlyName;
  Name inputName(aFmlyName);
这样如果从键盘输入Bush，则会构造一个完整的Name("Bush", "")对象。
接下来进行查找，我们使用map容器提供的lower_bound方法（其实还有一个通用的lower_bound方法，不过map本身自带的效率更高），lower_bound方法返回一个iterator，这个iterator指向[first, end)的有序序列之中第一个可以插入value而不破坏原有容器顺序的位置。
而本身map中的各个元素都是经过排序的（排序过后同样姓氏的人会集中在一起，比如Lucas Hill 和 Mat Hill 会一前一后），这样我们的存储号码簿中有同样姓氏的情况，就可以通过lower_bound返回的指针进行自增操作，直到姓氏不符为止。完整的代码如下，

#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>
using namespace std;

class Name {
private:
    string familyName;
    string givenName;
public:
    Name(string FName = "", string GName = "") :
            familyName(FName), givenName(GName) {
    }
    virtual ~Name() {
    }
    const string& getFamilyName() const {
        return familyName;
    }
    const string& getGivenName() const {
        return givenName;
    }
    bool operator <(const Name & rhs) const {
        if (familyName < rhs.familyName) {
            return true;
        } else if (familyName == rhs.familyName) {
            if (givenName < rhs.givenName)
                return true;
        }
        return false;
    }
};

int _tmain(int argc, _TCHAR* argv[]) {
    string NameArray[][3] =
    { { "John", "Doe",     "3459483" },
        { "Nick", "Bonham", "3492930" },
        { "Jane", "Doe",     "2832819" },
        { "Adam", "Clark", "6518324" },
        { "Judy", "Foast", "9821572" },
        { "Zeus", "Lenos", "4552341" },
        { "Cole", "Minas", "1351244" },
        { "Ooos", "Clark", "1562553" } };

    map<Name, string> infoMap;
    for (size_t i = 0; i < sizeof(NameArray) / (sizeof(string) * 3); i++) {
        Name tmpName(NameArray[i][1], NameArray[i][0]);
        infoMap.insert(pair<Name, string>(tmpName, NameArray[i][2]));
    }

    // display the sorted name and numbers
    for (map<Name, string>::iterator iter = infoMap.begin();
            iter != infoMap.end(); iter++) {
        cout << iter->first.getGivenName() << " ";
        cout << iter->first.getFamilyName() << " ";
        cout << iter->second << endl;
    }

    while (true) {
        cout << "Input the family name that you want to search: " << endl;
        string aFmlyName;
        cin >> aFmlyName;
        if (aFmlyName == "exit")
            break;
        Name inputName(aFmlyName);
        map<Name, string>::iterator iter = infoMap.lower_bound(inputName);
        if (iter == infoMap.end() ||
            iter->first.getFamilyName() != inputName.getFamilyName()) {
            cout << "Nothing has been found, try again" << endl;
            continue;
        }

        cout << "...here's the info that you need:" << endl;
        while (true) {
            cout << iter->first.getGivenName() << " ";
            cout << iter->first.getFamilyName() << " ";
            cout << iter->second << endl;
            iter++;
            if (iter == infoMap.end() ||
                iter->first.getFamilyName() != inputName.getFamilyName())
                break;
        }
    }
    cout << " * * program terminated * *" << endl;
    return 0;
}

以下是输出，