刷题常见错误以及心得

set

获取set最后一个元素 不能用 *st.end() 需要用 *st.rbegin(), 使用*set.end()只能获取到最后一个元素的索引。

set元素转vector的三种方法:

std::set<char> s = { 'a', 'b', 'c', 'd', 'e' };
std::vector<char> v(s.begin(), s.end());

std::set<char> s = { 'a', 'b', 'c', 'd', 'e' };
std::vector<char> v(s.size());
std::copy(s.begin(), s.end(), v.begin());

std::set<char> s = { 'a', 'b', 'c', 'd', 'e' };
std::vector<char> v;
v.assign(s.begin(), s.end());

set中的count():用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。并且set的find等返回的不是下标，因为没有set不是数组，返回的是迭代器，及对应值为value的指针
vector 的size函数返回vector大小，返回值类型为size_type，Member type size_type is an unsigned integral type，即无符号整数；
- vector<int> A;
- A.size()-1因为size返回值是无符号类型所以 A.size()-1越界，是个很大的数
- 正确使用 (int)(A.size()-1)

string

replace

string& replace (size_t pos, size_t len, const string& str); 用str替换指定字符串从起始位置pos开始长度为len的字符,如果第三个参数是想要整非字符串数据，需要调用to_string()方法

int main()  
{  
   string line = "this@ is@ a test string!";  
   line = line.replace(line.find("@"), 1, ""); //从第一个@位置替换第一个@为空  
   cout << line << endl;     
   return 0;  
}

output:this@ is a test string!

string& replace (const_iterator i1, const_iterator i2, const string& str);用str替换迭代器起始位置和结束位置的字符

 int main()  
{  
    string line = "this@ is@ a test string!";  
    line = line.replace(line.begin(), line.begin() + 6, "");  //用str替换从begin位置开始的6个字符  
    cout << line << endl;     
    return 0;  
}

output:is@ a test string!

map

map默认的排序是根据key在自动排序的，如果更具value来排序呢？

排序问题(更具Key自动排序和自定义排序)

#include <map>
#include <string>
#include <iostream>
using namespace std;

typedef pair<string, int> PAIR;

ostream &operator<<(ostream &out, const PAIR &p)
{
    return out << p.first << "\t" << p.second;
}

int main()
{
    map<string, int> name_score_map;
    name_score_map["LiMin"] = 90;
    name_score_map["ZiLinMi"] = 79;
    name_score_map["BoB"] = 92;
    name_score_map.insert(make_pair("Bing", 99));
    name_score_map.insert(make_pair("Albert", 86));
    for (map<string, int>::iterator iter = name_score_map.begin();
         iter != name_score_map.end();
         ++iter)
    {
        cout << *iter << endl;
    }
    return 0;
}

output:

Albert  86
Bing    99
BoB     92
LiMin   90
ZiLinMi 79

map的定义

template < class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair<const Key,T> > > class map;

第四个是 Allocator，用来定义存储分配模型的, 第三个参数class Compare = less<Key> 这也是一个class类型的，而且提供了默认值 less<Key>

实质是对operator()操作符的重载

template <class T> struct less : binary_function <T,T,bool> {
   bool operator() (const T& x, const T& y) const
   {return x<y;}
};

与less相对的还有greater：

template <class T> struct greater : binary_function <T,T,bool> {
  bool operator() (const T& x, const T& y) const
    {return x>y;}
};

map这里指定less作为其默认比较函数(对象)，所以我们通常如果不自己指定Compare，map中键值对就会按照Key的less顺序进行组织存储，因此我们就看到了上面代码输出结果是按照学生姓名的字典顺序输出的，即string的less序列

#include <map>
#include <string>
#include <iostream>
using namespace std;

typedef pair<string, int> PAIR;

ostream &operator<<(ostream &out, const PAIR &p)
{
    return out << p.first << "\t" << p.second;
}

int main()
{
    map<string, int, greater<string> > name_score_map;
    name_score_map["LiMin"] = 90;
    name_score_map["ZiLinMi"] = 79;
    name_score_map["BoB"] = 92;
    name_score_map.insert(make_pair("Bing", 99));
    name_score_map.insert(make_pair("Albert", 86));
    for (map<string, int>::iterator iter = name_score_map.begin();
         iter != name_score_map.end();
         ++iter)
    {
        cout << *iter << endl;
    }
    return 0;
}

output:

ZiLinMi  79
LiMin    90
BoB      92
Bing     99
Albert   86

写一个compare的类，让map按照自己想要的顺序来存储，比如，按照学生姓名的长短排序进行存储

struct CmpByKeyLength {
   bool operator()(const string& k1, const string& k2) {
      return k1.length() < k2.length()
   }
}

int main()
{
    map<string, int, CmpByKeyLength> name_score_map;
    name_score_map["LiMin"] = 90;
    name_score_map["ZiLinMi"] = 79;
    name_score_map["BoB"] = 92;
    name_score_map.insert(make_pair("Bing", 99));
    name_score_map.insert(make_pair("Albert", 86));
    for (map<string, int>::iterator iter = name_score_map.begin();
         iter != name_score_map.end();
         ++iter)
    {
        cout << *iter << endl;
    }
    return 0;
}

output:

BoB      92
Bing     99
LiMin    90
Albert   86
ZiLinMi  79

排序问题(更具Value自定义排序)

借助map提供的参数接口，为它指定相应Compare类，就可以实现对map按Key排序，是在创建map并不断的向其中添加元素的过程中就会完成排序。

如何实现Map的按Value排序呢？

第一反应是利用stl中提供的sort算法实现，但是sort算法有个限制，利用sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map也是一个集合容器，它里面存储的元素是pair，但是它不是线性存储的（像红黑树），所以利用sort不能直接和map结合进行排序。虽然不能直接用sort对map进行排序，那么可不可以把map中的元素放到序列容器（如vector）中，然后再对这些元素进行排序呢？要对序列容器中的元素进行排序，也有个必要条件：就是容器中的元素必须是可比较的，也就是实现了< 操作的。那么现在就来看下map中的元素满足这个条件么？

map中的元素类型为pair，定义如下：

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;
    pair() : first(T1()), second(T2()) {}
    pair(const T1 &x, const T2 &y) : first(x), second(y) {}
    template <class U, class V>
    pair(const pair<U, V> &p) : first(p.first), second(p.second) {}
}

pair也是一个模板类，这样就实现了良好的通用性。它仅有两个数据成员first 和 second，即 key 和 value，而且在<utility>头文件中，还为pair重载了 < 运算符，具体实现如下：

template <class _T1, class _T2>
inline bool
operator<(const pair<_T1, _T2> &__x, const pair<_T1, _T2> &__y)
{
    return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second);
}

其中__x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second) 这个less在两种情况下返回true，

第一种情况：__x.first < __y.first 这个好理解，就是比较key，如果__x的key 小于__y的key 则返回$true$。
!(__y.first < __x.first) && __x.second < __y.second
- 当然由于||运算具有短路作用，即当前面的条件不满足是，才进行第二种情况的判断。第一种情况__x.first < __y.first 不成立，即__x.first >= __y.first 成立，在这个条件下，我们来分析下 !(__y.first < __x.first) && __x.second < __y.second,!(__y.first < __x.first) ，看清出，这里是$y$的$key$不小于$x$的$key$ ，结合前提条件，__x.first < __y.first 不成立，即$x$的$key$不小于$y$的$key$ 即： !(__y.first < __x.first) && !(__x.first < __y.first ) 等价于 __x.first == __y.first ,也就是说，第二种情况是在key相等的情况下，比较两者的value（second）。

tauysi / Code

刷题常见错误以及心得

set

string

replace

map

排序问题(更具Key自动排序和自定义排序)

排序问题(更具Value自定义排序)

简介

发行版

贡献者

近期动态

tauysi / Code .gitee-modal { width: 500px !important; }

刷题常见错误以及心得

set

string

replace

map

排序问题(更具Key自动排序和自定义排序)

排序问题(更具Value自定义排序)

简介

发行版

贡献者

近期动态

搜索帮助

tauysi / Code