vector_map 比map更高效的 key value 容器

vector_map 为什么比map效率高

1. vector是线性存储，map是二叉树树形，所以vector内存访问的局部性更好
2. vector,  一次分配一个比较大的空间（2^n的分配方式）， map每次都需要 new 或delele 一个树结点, 内存分配是很耗时的。
3. vector_map, 可以在数据构造阶段，使用push_back, 填充完，数据后调用一次sort就可以了（快速排序或堆排序）， 而map每次insert都是一次查找和树的旋转操作，整个过程就像是个插入排序。
4. vector_map, 中的查找，而二分查找，时间复杂度是稳定的log(n), 而map是在log(n) 和 2* log(n)之间 (因为map是红黑树树实现，不是平衡二差树)
5. vector比map消耗更少的内存，vector内部是数组，辅助数据也很少， map是树形结构，有至少3个指针来维持关系。

被滥用的map

       为什么大家一说到key,value 容器，就想到map, 因为 STL一开始只实现了map,  hash还是非标准的，但现实是我们大多数时候需要的只是 std:tr1::unorder_map， std::map 有大小关系， unorder_map没有。std::map的确很方便，但效率确实不高。

      对于写高性能的后台程序来说，只在很少需要的调用的地方，才可以使用std::map. 比如 配置文件的读取（只有启动的时候调用). 对于像 HTTP 请求参数解析或 HTTP header的解析，最好不要用map。

如果用了map，记得把这个map全局话，并不要调用map.clear(). 而是只去清楚 map的值，比如定义个clear_value(map)函数，这样也能提高些效率。

下面是我的vector_map实现：

#ifndef __VECTOR_MAP_H__
#define __VECTOR_MAP_H__
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

//wrapped vector for map
template<typename key_t, typename mapped_t, class compare_t = std::less<key_t> >
class vector_map_basic: public std::vector<std::pair<key_t, mapped_t> > {
public:
    typedef compare_t key_compare;
    typedef key_t key_type;
    typedef mapped_t mapped_type;
    typedef std::pair<key_t, mapped_t> value_type;
    typedef vector_map_basic<key_t, mapped_t, compare_t> this_type;
    typedef std::vector<value_type> container_type;

#define THIS_TYPE vector_map_basic<key_t, mapped_t, compare_t>

    void push_back(key_type const &key, mapped_type const &mapped) {
        push_back(make_pair(key, mapped));
    }

    class compare_for_find: public std::binary_function<value_type, key_type,
            bool> {
    public:
        explicit compare_for_find(key_compare const &comp) :
            comp_(comp) {
        }
        inline
        bool operator()(value_type const &node, key_type const &key) {
            return comp_(node.first, key);
        }

        key_compare comp_;
    };

    class compare_for_sort: public std::binary_function<value_type, value_type,
            bool> {
    public:
        explicit compare_for_sort(key_compare const &comp) :
            comp_(comp) {
        }

        inline
        bool operator()(value_type const &left, value_type const &right) {
            return comp_(left.first, right.first);
        }
        key_compare comp_;
    };

    //get
    bool get(key_type const &key, mapped_type & result) const {
        typename this_type::const_iterator it = find(key);
        if (it != data().end()) {
            result = it->second;
            return true;
        }
        return false;
    }

    inline std::pair<typename THIS_TYPE::const_iterator,
            typename THIS_TYPE::const_iterator> equal_range(key_type const &key) const {
        return std::equal_range(data().begin(), data().end(), key,
                compare_for_find(key_comp_));
    }

    inline std::pair<typename THIS_TYPE::iterator, typename THIS_TYPE::iterator> equal_range(
            key_type const &key) {
        return std::equal_range(data().begin(), data().end(), key,
                compare_for_find(key_comp_));
    }

    typename THIS_TYPE::const_iterator find(key_type const &key) const {
        typename this_type::const_iterator it = std::lower_bound(
                data().begin(), data().end(), key, compare_for_find(key_comp_));
        typename this_type::iterator iend = data().end();
        if (it != iend && !key_comp_(key, it->first))
            return it;
        return iend;
    }

    typename THIS_TYPE::iterator find(key_type const &key) {
        typename this_type::iterator it = std::lower_bound(data().begin(),
                data().end(), key, compare_for_find(key_comp_));
        typename this_type::iterator iend = data().end();
        if (it != iend && !key_comp_(key, it->first))
            return it;
        return iend;
    }

    key_compare key_comp() const {
        return key_comp_;
    }

    //sort
    void sort() {
        typename this_type::compare_for_sort comp(this->key_comp_);
        std::sort(data().begin(), data().end(), comp);
    }

    //
    void set_default_value(mapped_type const &def) {
        mapped_default_ = def;
    }

    mapped_type default_value() const {
        return mapped_default_;
    }

    typename THIS_TYPE::container_type const &
    data() const {
        return *this;
    }

    typename THIS_TYPE::container_type &
    data() {
        return *this;
    }

public:
    key_compare key_comp_;
    mapped_type mapped_default_;

#undef THIS_TYPE
};

//wrapped vector for map
template<typename key_t, typename mapped_t, class compare_t = std::less<key_t> >
class vector_map: public vector_map_basic<key_t, mapped_t, compare_t> {
public:

#define THIS_TYPE vector_map<key_t, mapped_t,compare_t>

    typedef vector_map this_type;
    typedef vector_map_basic<key_t, mapped_t, compare_t> parent_type;

    vector_map() {
    }

    //for fast insert

    void push_back(typename THIS_TYPE::value_type const &value) {
        push_back(value);
    }

    void push_back(typename THIS_TYPE::key_type const &key,
            typename THIS_TYPE::mapped_type const &mapped) {
        push_back(make_pair(key, mapped));
    }

    void set(typename THIS_TYPE::key_type const &key,
            typename THIS_TYPE::mapped_type const & val) {
        typename this_type::iterator iend = this->data().end(), it =
                std::lower_bound(this->data().begin(), iend, key,
                        typename this_type::compare_for_find(this->key_comp_));
        if (it != iend && !key_comp_(key, it->first)) {
            it -> second = val;
        } else {
            insert(it, make_pair(key, val));
        }
    }

    //like map insert
    void insert(typename this_type::value_type const &value) {
        this->set(value.first, value.second);
    }

    void insert(typename this_type::iterator pos,
            typename this_type::value_type const &value) {
        this->data().insert(pos, value);
    }

    //get
    bool get(typename THIS_TYPE::key_type const &key,
            typename THIS_TYPE::mapped_type & result) const {
        return parent_type::get(key, result);
    }

    typename THIS_TYPE::mapped_type const &
    operator[](typename THIS_TYPE::key_type const &key) const {
        typename this_type::mapped_type result = this->mapped_default_;
        get(key, result);
        return result;
    }

    typename THIS_TYPE::mapped_type &
    operator[](typename THIS_TYPE::key_type const &key) {
        typename this_type::iterator iend = this->data().end();
        typename this_type::iterator it = std::lower_bound(
                this->data().begin(), iend, key,
                typename this_type::compare_for_find(this->key_comp_));
        if (it != iend && !key_comp_(key, it->first)) {
            return it -> second;
        }
        return this->data().insert(it, make_pair(key, this->mapped_default_))->second;
    }
#undef THIS_TYPE
};

template<typename like_map_t, typename val_t>
void clear_value(like_map_t &map, val_t const & null_val) {
    for (typename like_map_t::iterator it = map.begin(), iend = map.end(); it
            != iend; ++it) {
        it->second = null_val;
    }
}

template<typename like_map_t>
void clear_value(like_map_t &map) {
    clear_value(map, typename like_map_t::mapped_type());
}

#endif //__VECTOR_MAP_H__

使用clear_value， 可以减少内存释放和分配，从而提高效率。

对于有些后台程序，只关心固定的param或http header, 那么那么还可以定制个数据结构，那样速度更快，下次介绍fixed_map.

WEB后台，还有影响效率的地方是使用滥用std::string,  这个可以实现个ref_str来解决。这个也下次介绍吧。