原文鏈接：http://m.shnenglu.com/eXile/archive/2008/01/29/42104.html
在有些情況下，需要用到一個(gè)有序的vector。它的有序操作有三種：查找，插入，刪除。
插入實(shí)現(xiàn)：
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);
}
刪除實(shí)現(xiàn)：
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));
}
查找可通過(guò)binary_search, lower_bound, upper_bound, 或者equal_range實(shí)現(xiàn)。如果要實(shí)現(xiàn)類(lèi)似map的關(guān)鍵字搜索，有一個(gè)技巧，就是用比較函數(shù)進(jìn)行重載，比如學(xué)生要按學(xué)號(hào)查找，則用以下定義：
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;
}
};
};
查找學(xué)號(hào)為5的學(xué)生：
std::vector<Student> students;
bool exist = std::binary_search(students.begin(), students.end(), 5, Student::LessThan());
刪除學(xué)號(hào)為5的學(xué)生：
ordered_erase(students, 5, Student::LessThan());