原文链接: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());