我的玻璃盒子

(转载)vector的有序化操作

原文链接:http://www.cppblog.com/eXile/archive/2008/01/29/42104.html

 

  在有些情况下,需要用到一个有序的vector。它的有序操作有三种:查找,插入,删除。
  插入实现:

template <typename Container>
inline void ordered_insert(Container& c,  typename Container::value_type const& t)
{
    c.insert(std::upper_bound(c.begin(), c.end(), t), t);
}

template <typename Container, typename Cmp>
inline void ordered_insert(Container& c, typename Container::value_type const& t, Cmp cmp)
{
    c.insert(std::upper_bound(c.begin(), c.end(), t, cmp), t);
}

  删除实现:

template <typename Container, typename It>
inline void erase_range(Container& c, std::pair<It, It> const& r)
{
    c.erase(r.first, r.second);
}

template <typename Container>
inline void ordered_erase(Container& c,  typename Container::value_type const& t)
{
    erase_range(c, std::equal_range(c.begin(), c.end(), t));
}

template <typename Container, typename T, typename Cmp>
inline void ordered_erase(Container& c, T const& t, Cmp cmp)
{
    erase_range(c, std::equal_range(c.begin(), c.end(), t, cmp));
}

  查找可通过binary_search, lower_bound, upper_bound, 或者equal_range实现。如果要实现类似map的关键字搜索,有一个技巧,就是用比较函数进行重载,比如学生要按学号查找,则用以下定义:

struct Student
{
int            id;
    std::string name;

    struct LessThan
    {
        bool operator() (Student const& x, Student const& y)
        {
            return x.id < y.id;
        }

        bool operator() (Student const& x, int id)
        {
            return x.id < id;
        }

        bool operator() (int id, Student const& y)
        {
            return id < y.id;
        }
    };
};

查找学号为5的学生:

std::vector<Student> students;

bool exist = std::binary_search(students.begin(), students.end(), 5, Student::LessThan());

删除学号为5的学生:

ordered_erase(students, 5, Student::LessThan());

posted on 2008-01-29 16:15 深蓝色系统 阅读(390) 评论(0)  编辑 收藏 引用 所属分类: Skills


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2011年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿(75)

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜