学步园

       sorted_vector是OpenCVS中定义的一个用于键值对Key-Value的结构，在进行排序和检索中使用它可以大大提高开发效率，其结构：

sing std::pair;
template<typename _KeyTp, typename _ValueTp> struct sorted_vector
{
    sorted_vector() {}
    void clear() { vec.clear(); }
    size_t size() const { return vec.size(); }
    _ValueTp& operator [](size_t idx) { return vec[idx]; }
    const _ValueTp& operator [](size_t idx) const { return vec[idx]; }

    void add(const _KeyTp& k, const _ValueTp& val)
    {
        pair<_KeyTp, _ValueTp> p(k, val);
        vec.push_back(p);
        size_t i = vec.size()-1;
        for( ; i > 0 && vec[i].first < vec[i-1].first; i-- )
            std::swap(vec[i-1], vec[i]);
        CV_Assert( i == 0 || vec[i].first != vec[i-1].first );
    }

    bool find(const _KeyTp& key, _ValueTp& value) const
    {
        size_t a = 0, b = vec.size();
        while( b > a )
        {
            size_t c = (a + b)/2;
            if( vec[c].first < key )
                a = c+1;
            else
                b = c;
        }

        if( a < vec.size() && vec[a].first == key )
        {
            value = vec[a].second;
            return true;
        }
        return false;
    }

    void get_keys(vector<_KeyTp>& keys) const
    {
        size_t i = 0, n = vec.size();
        keys.resize(n);

        for( i = 0; i < n; i++ )
            keys[i] = vec[i].first;
    }

    vector<pair<_KeyTp, _ValueTp> > vec;
};

   如下是一个根据输入sorted_vector及关键字，查找键值的函数：

template<typename _ValueTp> inline const _ValueTp* findstr(const sorted_vector<string, _ValueTp>& vec,
                                                           const char* key)
{
    if( !key )
        return 0;

    size_t a = 0, b = vec.vec.size();
    while( b > a )
    {
        size_t c = (a + b)/2;
        if( strcmp(vec.vec[c].first.c_str(), key) < 0 )
            a = c+1;
        else
            b = c;
    }

    if( ( a < vec.vec.size() ) && ( strcmp(vec.vec[a].first.c_str(), key) == 0 ))
        return &vec.vec[a].second;
    return 0;
}