数据结构的典型用例

2019/12/05 C/C++

基于C/C++下的数据结构的高级用法。

字符串的划分

常见的问题是如何将一个string按照空格划分并返回一个容器。

  1. 按照1个空格位进行划分。
  2. substr(a,b),从a位置开始截取长度为b的子串。
string str = "Hello world.";
vector<string> result;

int posi = 0;
int head = 0;

while((posi = str.find(' ', posi)) != string::npos) {
    result.push_back(str.substr(head, posi-head));
    head = ++posi;
}
result.push_back(str.substr(head));

对数据结构的遍历

除了使用迭代器以外,还可以使用auto来执行循环。

vector<string> vec;
map<string, int> maps;

for (auto item:vec) {
    cout << item << endl;
}

for (auto item:maps) {
    cout << item.first << " " << item.second << endl;
}

for (auto i=maps.begin(); i!=maps.end(); i++) {
    cout << item->first << " " << item->second << endl;
}

对map进行排序

默认情况下map是按key升序排序的,如果要对value进行排序,需要转换为vector。

  1. 使用lambda需要开启std=c++11。
typedef pair<string, int> PAIR;

map<PAIR> maps;
vector<PAIR> vec(maps.begin(), maps.end());

// value降序
sort(vec.begin(), vec.end(), [](const PAIR &x, const PAIR &y) -> int {
    return x.second > y.second;
});
// value升序
sort(vec.begin(), vec.end(), [](const PAIR &x, const PAIR &y) -> int {
    return x.second < y.second;
});

双列自定义排序

第一列升序排序,如果相同时,第二列降序排序

typedef pair<int, int> PAIR;
vector<PAIR> vec;

sort(vec.begin(), vec.end(), [](const PAIR &x, const PAIR &y) -> int {
    if (x.first == y.first) {
        return x.second > y.second;
    } else {
        return x.first < y.first;
    }
});

Search

    Table of Contents