C++ STL 学习笔记

  1. 云栖社区>
  2. 博客>
  3. 正文

C++ STL 学习笔记

橘子红了呐 2017-11-16 22:42:00 浏览620
展开阅读全文

#.string 建议

  使用string 的方便性就不用再说了,这里要重点强调的是string的安全性。    

  string并不是万能的,如果你在一个大工程中需要频繁处理字符串,而且有可能是多线程,那么你一定要慎重(当然,在多线程下你使用任何STL容器都要慎重)。

  string的实现和效率并不一定是你想象的那样,如果你对大量的字符串操作,而且特别关心其效率,那么你有两个选择,首先,你可以看看你使用的STL版本中string实现的源码;另一选择是你自己写一个只提供你需要的功能的类。

  string的c_str()函数是用来得到C语言风格的字符串,其返回的指针不能修改其空间。而且在下一次使用时重新调用获得新的指针。

  string的data()函数:如果string的size()不为0,返回的指针指向string对应的字符串的第一个字符,大小为size()个;如果string的size()为0,返回一个非null的指针,该指针不能被解引用。 对于c_str() data()函数,返回的指针指向的内容都是const的,内容都是由string本身拥有,不可修改其内容。其原因是许多string实现的时候采用了引用机制,也就是说,有可能几个string使用同一个字符存储空间。而且你不能使用sizeof(string)来查看其大小。

  尽量去使用操作符,这样可以让程序更加易懂(特别是那些脚本程序员也可以看懂)。

  find()函数都返回一个size_type类型,这个返回值一般都是所找到字符串的位置,如果没有找到,则返回string::npos。有一点需要特别注意,所有和string::npos的比较一定要用string::size_type来使用,不要直接使用int或者unsigned int等类型。

#.sort 建议

  默认的都是从小到大排序

  1.若需对vector, string, deque, 或 array 容器进行全排序,你可选择sort或stable_sort;

  2.若只需对vector, string, deque, 或 array 容器中取得top n的元素,部分排序partial_sort是首选.   如:前5个:partial_sort(vect.begin(), vect.begin()+5, vect.end());

  3.若对于vector, string, deque 或 array 容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序,nth_element是最理想的。   如:找排在第5的位置 nth_element(vect.begin(), vect.begin()+4, vect.end()); //注意是begin()+4

  partial_sort()和nth_element()都把5个最小的放在前面

  4.若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition。   如:student exam("pass", 60); stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

  5.若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。

  6.sort, stable_sort, partial_sort, 和nth_element算法都需要以随机迭代器(random access iterators)为参数,因此这些算法能只能用于vector, string, deque, 和array等容器,对于标准的关联容器map、set、multimap、multiset等,这些算法就有必要用了,这些容器本身的比较函数使得容器内所有元素一直都是有序排列的。

  7.对于容器list,看似可以用这些排序算法,其实也是不可用的(其iterator的类型并不是随机迭代器),不过在需要的时候可以使用list自带的排序函数sort(有趣的是list::sort函数和一个“稳定”排序函数的效果一样)。 对一个list容器使用partial_sort或nth_element,只能间接使用: 方法(1):把list中的元素拷贝到带有随机迭代器的容器中,然后再使用这些算法; 方法(2):生成一个包含list::iterator的容器,直接对容器内的list::iterator进行排序,然后通过list::iterator得到所指的元素; 方法(3):借助一个包含iterator的有序容器,然后反复把list中的元素连接到你想要链接的位置。

  list成员函数的行为和它们兄弟的行为经常不同。如想从容器删除对象,调用remove,remove_if和unique算法后,必须接着调用erase才能真正删除对象,但list的remove,remove_if和unique真的删除掉了对象。sort算法不能用于list,但list可以调用自己的sort成员函数。

  8.partition和stable_partition与sort、stable_sort、partial_sort和nth_element不同,它们只需要双向迭代器。因此可以在任何标准序列迭代器上使用partition和stable_partition

  9.时间和空间复杂度: stable_sort > sort > partial_sort > nth_element > stable_partition > partition

#.删除容器中的特定值

  1.如果容器是vector string deque,使用erase和remove的惯用法:          

  c.erase(remove(c.begin(),c.end(),value),c.end())   remove并不能“真的”删除元素,因为它做不到,如果你真的要删除元素,要在remove上接上erase

  2.如果容器是list,使用list::remove (ls.remove(value))

  3.如果容器是关联容器,用erase删除容器中满足一个特定条件的值:c.erase(c.begin())  

  1.如果容器是vector string deque,使用erase和remove_if的惯用法

  2.如果容器是list,使用list::remove_if

  3.如果容器是关联容器,用remove_copy_if和swap,或写一个循环遍历容器元素,把迭代器传给erase时后置递增它。

循环遍历删除容器中的值:

复制代码
//顺序容器循环遍历容器元素删除值:
for(vector<int>::iterator i=c.begin(); i!=c.end(); )
    if( condition(*i) ) i=c.erase(i);
    else ++i;

//关联容器循环遍历容器元素删除值:关联容器的erase(i)会返回删除元素的个数,这里只关心删除的值
for(map<int,int>::iterator i=c.begin(); i!=c.end(); )
    if( condition(*i) ) c.erase(i++);
    else ++i;
复制代码

#.迭代器失效

vector:

1.当插入(push_back)一个元素后,end操作返回的迭代器肯定失效。

2.当插入(push_back)一个元素后,capacity返回值与没有插入元素之前相比有改变,则需要重新加载整个容器,此时begin和end操作返回的迭代器都会失效。

3.当进行删除操作(erase,pop_back)后,指向删除点的迭代器失效;指向删除点后面的元素的迭代器也将全部失效。

deque迭代器的失效情况:

1.在deque容器首部(push_front)或者尾部(push_back)插入元素不会使得任何迭代器失效。

2.在其首部(pop_front)或尾部(pop_back)删除元素则只会使指向被删除元素的迭代器失效。

3.在deque容器的任何其他位置的插入(insert)和删除(erase)操作将使指向该容器元素的所有迭代器失效。

list/set/map

1.删除时,指向该删除节点的迭代器失效

迭代器使用注意事项:

1.resize 操作可能会使迭代器失效。在 vector 或 deque 容器上做 resize 操作有可能会使其所有的迭代器都失效。

2.不要存储 end 操作返回的迭代器。添加或删除 deque 或 vector 容器内的元素都会导致存储的end迭代器失效。

3.使用越界的下标,或调用空容器的 front 或 back 函数,都会导致程序出现严重的错误。

4.赋值和 assign 操作使左操作数容器的所有迭代器失效。swap 操作则不会使迭代器失效。完成 swap 操作后,尽管被交换的元素已经存放在另一容器中,但迭代器仍然指向相同的元素。

5.由于 assign 操作首先删除容器中原来存储的所有元素,因此,传递给 assign 函数的迭代器不能指向调用该函数的容器内的元素。

6.只适用于vector和deque容器的迭代器操作:iter + n、iter - n、iter1 += iter2、>, >=, <, <=

7.list 容器的迭代器既不支持算术运算(加法或减法),也不支持关系运算(<=, <, >=, >),它只提供前置和后置的自增、自减运算以及相等(不等)运算。

#.使用“交换技巧”来休整过剩容量

  class Contestant{....}
  vector<Contestant> v;
  ....  //是v变大然后删除部分
  vector<Contestant>(v).swap(v); //在v上“收缩到合适”(v.size()=v.capacity())
  vector<Contestant>( ).swap(v); //清除v而且最小化它的容量

  string s;
  .....     //是s变大然后删除部分
  string(s).swap(s); //在s上“收缩到合适”
  string( ).swap(s); //清除s而且最小化它的容量

#.为指针的关联容器指定比较类型(不是比较函数)

set<string*> ssp; //建立一个指针的关联容器,容器会以指针的值排序,所以输出时候string不会按字典顺序

复制代码
struct StringLess: public binary_function<const string*, const string*, bool>
{
    bool operator()(const string* ps1,const string* ps2) const
    {
        return *ps1 < *ps2;
    }
};

typedef set<string*,StringLess> StringPtrSet;
StringPtrSet ssp;
复制代码

或者:

复制代码
struct DereferenceLess
{
    template<typename PtrType>
    bool operator()(PtrType p1, PtrType p2) const
    {
        return *p1 < *p2;
    }
};

set<string*,DereferenceLess> ssp;
复制代码

如果有一个智能指针或迭代器的关联容器,也得为它指定“比较类型”

#.equal_range的用法

复制代码
 typedef vector<string>::iterator vit; 
 typedef pair<vit,vit> vitpair;
 sort(svec.begin(),svec.end());
 vitpair vp = equal_range(svec.begin(),svec.end(),"aaa");
 if(vp.first != vp.second)
    cout<<"\nFind the string\n";
 else cout<<" Not find the string\n";
 if(vp.first != vp.second)
    cout<<"There are "<<distance(vp.first,vp.second)<<" aaa \n";
复制代码

#.使iterator(i)指向const iterator(ci)

   typedef vector<int>::iterator Iter;
   typedef vector<int>::const_iterator ConstIter;
   从iterator到const iterator没有隐式类型转换,也不能用Iter i(const_cast<Iter>(ci));因为iterator(i)和const iterator(ci)是两种完全不同的类型
   可以用以下技巧:
   advance(i,distance<ConstIter>(i,ci)); //使i指向ci指向的元素
   建议:尽量用iterator代替const_iterator和reverse_iterator

#.只能操作有序数据的算法

  搜索算法:  binary_search,lower_bound,upper_bound,equal_range,   set_union,set_intersection,set_difference,set_symmetric_difference   merge, inplace_merge includes

  一般用于有序区间:unique,unique_copy  

#.保证用于算法的比较函数和用于排序的一致

  sort(v.begin(),v.end(),greater<int>())
  //bool it = binary_search(v.begin(),v.end(),5); //error 默认的是升序,会导致未定义的行为
  bool it = binary_search(v.begin(),v.end(),5,greater<int>());

#.用accumulate和for_each来统计区间

  #include<numeric>   //包含accumulate
  double sum = accumulate(v.begin(),v.end(),0.0);

#.ptr_fun(),mem_fun()和mem_fun_ref()的用法

  ptr_fun()可以把指向一个函数的指针转化为一个函数对象。函数必须是一元或是二元函数(不能为无参的函数)
  transform(begin,end,dest,not1(ptr_fun(fun)));

  mem_fun 与 mem_fun_ref 是为了使 STL 算法可以将成员函数(member functions)当作参数而加入的,如下:
  list<Widget *> lpw;
  for_each(lpw.begin(), lpw.end(),mem_fun(&Widget::test)); // pw->test();

  vector<Widget> vw;
  for_each(vw.begin(), vw.end(),mem_fun_ref(&Widget::test)); // w.test();
  mem_fun_ref的作用和用法跟mem_fun一样,唯一的不同就是:当容器中存放的是对象实体的时候用mem_fun_ref,当容器中存放的是对象的指针的时候用mem_fun。

#.避免对 set 及 multiset 的key进行原地修改

  这里的“键部分(key part)”指的是 set/multiset 存储的对象 T 中对 set/multiset 的排序算法有影响的部分,或者说是参与排序的部分。比如下例中 User::ID:

复制代码
class User {
public:
    unsigned int ID;
    string name;
    unsinged int age;
    const string& gettitle() const;
    void settitle(string& title);  
};

class UserIDLess : public binary_function<User, User, bool> {
public:
    operator() (const User &lhs, const User &rhs) const {
       return lhs.ID < rhs.ID;
    }
};
typedef set<User, UserIDLess> IDUserSet;
复制代码

修改 set/multiset 中的对象时,注意不要改变对象的key(对set/multiset的排序算法有影响的部分),否则容器会被破坏。
如果必须改变键部分,采取如下策略:
1. 找到要修改的对象。i = set.find();
2. 复制对象。        User b(*i);
3. 修改复制的对象。  b.changeSome();
4. 删除原对象。      set.erase(i++); //自增这个迭代器,保持它有效
5. 插入复制的对象。  set.insert(i,b);

#.copy_if的正确实现(STL里没有copy_if)

复制代码
#include <iostream>
#include <vector>
#include <functional>
#include <iterator>
#include <algorithm>
using namespace std;

template<typename InputIterator,typename OutputIterator,typename Predicate>
OutputIterator copy_if(InputIterator begin,InputIterator end,OutputIterator destBegin,Predicate p)
{
    while(begin!=end)
    {
        if(p(*begin)) *destBegin++=*begin;
        ++begin;
    }
    return destBegin;
}

int main()
{
    int a[]={0,3,2,1,5,4,6,8,7,9};
    vector<int> v(a,a+sizeof(a)/sizeof(int));
    cout<<"\nOutput the number greater than 4:\n";
    copy_if(v.begin(),v.end(),ostream_iterator<int>(cout," "),bind2nd(greater<int>(),4));
    cout<<"\nOutput the number greater than 4:\n";
    //STl里没有copy_of,但有 remove_copy_of
    remove_copy_if(v.begin(),v.end(),ostream_iterator<int>(cout," "),bind2nd(less_equal<int>(),4)); 

    return 0;
}
复制代码

#.使仿函数类可适配

ptr_fun可以使四个标准函数适配器(not1、not2、bind1st和bind2nd)存在某些typedef,提供这些必要的typedef的函数对象称为可适配的。

operator()带一个实参的仿函数类,要继承的结构是std::unary_function。operator()带有两个实参的仿函数类,要继承的结构是std::binary_function。

unary_function和binary_function是模板,所以你不能直接继承它们。取而代之的是,你必须从它们产生的类继承,而那就需要你指定一些类型实参,对于unary_function,你必须指定的是由你的仿函数类的operator()所带的参数的类型和它的返回类型。对于binary_function,你要指定三个类型:你的operator的第一个和第二个参数的类型,和你的operator地返回类型。

两个的例子:

复制代码
template<typename T>
class MeetsThreshold: public unary_function<Widget, bool>
{
private:
    const T threshold;

public:
    MeetsThreshold(const T& threshold);
    bool operator()(const Widget&) const;
    ...
};

struct WidgetNameCompare:public binary_function<Widget, Widget, bool>
{
    bool operator()(const Widget& lhs, const Widget& rhs) const;
};
复制代码

一般来说,传给unary_function或binary_function的非指针类型都去掉了const和引用。

当operator()的参数是指针时这个规则变了。这里有一个和WidgetNameCompare相似的结构,但这个使用Widget*指针:

struct PtrWidgetNameCompare:public binary_function<const Widget*, const Widget*, bool> 
{
    bool operator()(const Widget* lhs, const Widget* rhs) const;
};

#.其他

当用某个模板类型下的成员前面需加上typename,但是不能用class更不能用struct
typename vector<T>::iterator it = v.begin();

用empty()来代替检查size()是否为0

给map添加一个元素时,insert比operator[]效率高

更新已经在map的元素时,operator[]效率高

尽量用算法代替手写循环

尽量用成员函数代替同名算法

C++中重载[]要两个版本来满足需要:

复制代码
char & String::operator[](int n)
{
    return data[n];
}

const char & String::operator[](int n) const
{
    return data[n];
}
复制代码

网友评论

登录后评论
0/500
评论
橘子红了呐
+ 关注