Week3

Week 3 STL¶

STL(Standard Template Library)，是C++标准库.

STL分成三个部分：

containers class templates, common data structures
Algorithms Functions that operate on ranges of elements.
Iterators Generalization of pointers, access elements in a uniform manner.

首先是Container:

sequential: array(static), vector(dynamic)
deque(double-ended queue)
forward_list(single-linked), list(doubly-linked)

Associative:

set(collection of unique keys)
map(collection of key-value pairs)
multiset, multimap

Unordered associative:

hashed by keys
unordered_set,unordered_map
unordered_multiset,unordered_multimap

Adaptors:

stack, queue, priority_queue

Using the vector:

#include<iostream>
#include<vector>

using namespace std;

int main(){
    vector<int> x;
    for (int a = 0; a < 1000; a++)
        x.push_back(a);
    // push 0,1,…,999 into the vector 

    vector<int>::iterator p;
    for (p = x.begin(); p < x.end(); p++)
        cout << *p << " ";
}

Basic operations for vector:

Constructor/Destructor

at,operator[],front,back,data
Element access

begin, end, cbegin, cend
Iterators

empty, size, reserve, capacity
Capacity

clear, erase, insert, push_back
Modifiers

vector举例¶

#include<iostream>
#include<vector>

using namespace std;

int main(){
    vector<int> evens {2,4,6,8};
    evens.push_back(20);
    evens.push_back(22);
    evens.insert(evens.begin()+4,5,10);

    for (int i = 0; i < evens.size(); ++i)
        cout << evens[i] << ' ';
    cout << endl;

    //输出结果是2 4 6 8 10 10 10 10 10，所以上面的函数的意义是在begin+4开始插入5个10.

    //另一种迭代方式：
    for (vector<int>::iterator it = evens.begin(); it < evens.end(); ++it)
        cout << *it << ' ';
    cout << endl;

    // auto: 让编译器自己推导数据类型
    for (auto it = evens.begin(); it < evens.end(); ++it)
        cout << *it << ' ';
    cout << endl;

    // 将evens取出
    for (int e: evens)
        cout << e << ' ';
    cout << endl;
    //以上都是C++11的功能

    //值得说明的一点是，以下代码成立：
    vector<int> x;
    for (int a = 0;  < 1000; a++)
        x.push_back(a);
    vector<int>::iterator p;
    for (p = x.begin(); p < x.end(); p++)
        cout << *p << " ";
    // 这里使用 < x.end()是成立的，因为vector内存是连续的

    return 0;
}

list举例¶

#include<iostream>
#include<vector>

using namespace std;

int main(){

    list <string> s;
    s.push_back("Hello");
    s.push_back("world");
    s.push_bacl("stl");

    list<string>::iterator p;
    for (p = s.begin(); p != s.end(); p++)
        cout << *p << " ";
    return 0; 
}

map举例¶

#include<iostream>
#include<vector>
using namespace std;

int main(){
    map<string, float> price;
    price["snapple"] = 0.75;
    price["coke"] = 0.50;

    string item;
    double total = 0;
    while (cin >> item)
        total += price[item];
}

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

int main(){
    map<string, int> price_list;
    price_list["apple"] = 3;
    price_list["orange"] = 5;
    price_list["banana"] = 1;

    string item;
    int total = 0;
    while (cin >> item)
        total += price_list[item];

    cout << total << endl;
    return 0;
}

algorithm举例¶

Tips

STL算法模块举例

Typedefs¶

长的名字不便于代码书写与阅读，因此可以用typedef来简化，如：
```
typedef map<Name, list<PhoneNum>> PB;
PB phonebook;
PB::iterator finger; 
```
C++11中，可以使用auto, using等简化代码逻辑.

Using your own class

Might Need: operator = (); default constructor

For sorted types, like set,map: less-than operator, operator<().

示例：

class Student {
    string name;
    int score;
public:
    // 默认构造函数
    Student() : name(""), score(0) {}

    // 赋值运算符
    Student& operator=(const Student& other) {
        name = other.name;
        score = other.score;
        return *this;
    }

    // 小于运算符（按分数排序）
    bool operator<(const Student& other) const {
        return score < other.score;
    }
};
// 现在可以使用 set<Student> 了

Warning

C++有一种silent insertion的操作，如：

if (foo["bob"] == 1)

这段代码如果没有找到"bob"，会自动插入一个键值对进入，所以正确的写法是：

if (foo.count("bob"))
// or
if (foo.contains("bob"))