vector的有序化操作

客官°小女子只卖身不卖艺 2022-08-26 04:52 171阅读 0赞

## [vector的有序化操作][vector] ##

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

![None.gif][] template  < typename  Container >   
![None.gif][]inline void ordered\_insert(Container &  c,　  typename  Container::value\_type  const &  t)  
![None.gif][]\{  
![None.gif][] c.insert(std::upper\_bound(c.begin(), c.end(), t), t);  
![None.gif][]\}  
![None.gif][]  
![None.gif][]template  < typename  Container,  typename  Cmp >   
![None.gif][]inline void ordered\_insert(Container &  c,　 typename  Container::value\_type  const &  t,　Cmp cmp)  
![None.gif][]\{  
![None.gif][] c.insert(std::upper\_bound(c.begin(), c.end(), t, cmp), t);  
![None.gif][]\}  
![None.gif][]

删除实现：

![None.gif][] template  < typename  Container,  typename  It >   
![None.gif][]inline void erase\_range(Container &  c, std::pair < It, It >  const &  r)  
![None.gif][]\{  
![None.gif][] c.erase(r.first, r.second);  
![None.gif][]\}  
![None.gif][]  
![None.gif][]template  < typename  Container >   
![None.gif][]inline void ordered\_erase(Container &  c, 　 typename  Container::value\_type  const &  t)  
![None.gif][]\{  
![None.gif][] erase\_range(c, std::equal\_range(c.begin(), c.end(), t));  
![None.gif][]\}  
![None.gif][]  
![None.gif][]template  < typename  Container,  typename  T,  typename  Cmp >   
![None.gif][]inline void ordered\_erase(Container &  c, T  const &  t, Cmp cmp)  
![None.gif][]\{  
![None.gif][] erase\_range(c, std::equal\_range(c.begin(), c.end(), t, cmp));  
![None.gif][]\}  
![None.gif][]

查找可通过binary\_search, lower\_bound, upper\_bound, 或者equal\_range实现。如果要实现类似map的关键字搜索，有一个技巧，就是用比较函数进行重载，比如学生要按学号查找，则用以下定义：

![None.gif][] struct Student  
![None.gif][]\{  
![None.gif][] int  id;  
![None.gif][] std:: string  name;  
![None.gif][]  
![None.gif][] struct LessThan  
![None.gif][] \{  
![None.gif][] bool operator() (Student  const &  x, Student  const &  y)  
![None.gif][] \{  
![None.gif][] return x.id  <  y.id;  
![None.gif][] \}  
![None.gif][]  
![None.gif][] bool operator() (Student  const &  x,  int  id)  
![None.gif][] \{  
![None.gif][] return x.id  <  id;  
![None.gif][] \}  
![None.gif][]  
![None.gif][] bool operator() ( int  id, Student  const &  y)  
![None.gif][] \{  
![None.gif][] return id  <  y.id;  
![None.gif][] \}  
![None.gif][] \};  
![None.gif][]\};  
![None.gif][]

查找学号为5的学生：

std::vector<Student> students;  
![None.gif][]  
bool exist  =  std::binary\_search(students.begin(), students.end(),  5 , Student::LessThan());

删除学号为5的学生：

![None.gif][] ordered\_erase(students,  5 , Student::LessThan());

[vector]: http://www.cppblog.com/eXile/archive/2008/01/29/42104.html
[None.gif]: /images/20220824/97ff01268976424e820bb265574f7ca7.png