STL

算法 > sjtu机试 算法 模拟
发布时间 :
字数:2.5k 阅读 : 评论:

STL set

3.1.2 使⽤用set
定义⼀一个set对象：
set<int> s;
set<double> ss;

set的基本操作：

s.begin() // 返回指向第⼀一个元素的迭代器器
s.clear() // 清除所有元素
s.count() // 返回某个值元素的个数
s.empty() // 如果集合为空，返回true(真）
s.end() // 返回指向最后⼀一个元素之后的迭代器器，不不是最后⼀一个元素
s.equal_range() // 返回集合中与给定值相等的上下限的两个迭代器器
s.erase() // 删除集合中的元素
s.find() // 返回⼀一个指向被查找到元素的迭代器器
s.get_allocator() // 返回集合的分配器器
s.insert() // 在集合中插⼊入元素
s.lower_bound() // 返回指向⼤大于（或等于）某值的第⼀一个元素的迭代器器
s.key_comp() // 返回⼀一个⽤用于元素间值⽐比较的函数
s.max_size() // 返回集合能容纳的元素的最⼤大限值
s.rbegin() // 返回指向集合中最后⼀一个元素的反向迭代器器
s.rend() // 返回指向集合中第⼀一个元素的反向迭代器器
s.size() // 集合中元素的数⽬目
s.swap() // 交换两个集合变量量
s.upper_bound() // 返回⼤大于某个值元素的迭代器器
s.value_comp() // 返回⼀一个⽤用于⽐比较元素间的值的函数

STL vector

定义vector向量量对象：
vector<int> s;
// 定义⼀一个空的vector对象，存储的是int类型的元素
vector<int> s(n);
// 定义⼀一个含有n个int元素的vector对象
vector<int> s(first, last);
// 定义⼀一个vector对象，并从由迭代器器first和last定义的序列列[first, last)中复制初值

vector的基本操作：

s[i] // 直接以下标⽅方式访问容器器中的元素
    s.front() // 返回⾸首元素
    s.back() // 返回尾元素
    s.push_back(x) // 向表尾插⼊入元素x
    s.size() // 返回表⻓长
    s.empty() // 表为空时，返回真，否则返回假
    s.pop_back() // 删除表尾元素
    s.begin() // 返回指向⾸首元素的随机存取迭代器器
    s.end() // 返回指向尾元素的下⼀一个位置的随机存取迭代器器
    s.insert(it, val) // 向迭代器器it指向的元素前插⼊入新元素val
    s.insert(it, n, val) // 向迭代器器it指向的元素前插⼊入n个新元素val
    s.insert(it, first, last)
    // 将由迭代器器first和last所指定的序列列[first, last)插⼊入到迭代器器it指向的元素前⾯面
    s.erase(it) // 删除由迭代器器it所指向的元素
    s.erase(first, last) // 删除由迭代器器first和last所指定的序列列[first, last)
    s.reserve(n) // 预分配缓冲空间，使存储空间⾄至少可容纳n个元素
    s.resize(n) // 改变序列列⻓长度，超出的元素将会全部被删除，如果序列列需要扩展（原空间
    ⼩小于n），元素默认值将填满扩展出的空间
    s.resize(n, val) // 改变序列列⻓长度，超出的元素将会全部被删除，如果序列列需要扩展（原空间
    ⼩小于n），val将填满扩展出的空间
    s.clear() // 删除容器器中的所有元素
    s.swap(v) // 将s与另⼀一个vector对象进⾏行行交换
    s.assign(first, last)
    // 将序列列替换成由迭代器器first和last所指定的序列列[first, last)，[first, last)不不能是原序列列中的⼀一部分
    // 要注意的是，resize操作和clear操作都是对表的有效元素进⾏行行的操作，但并不不⼀一定会改变缓冲
    空间的⼤大⼩小
    // 另外，vector还有其他的⼀一些操作，如反转、取反等，不不再⼀一⼀一列列举
    // vector上还定义了了序列列之间的⽐比较操作运算符（>、<、>=、<=、==、!=），可以按照字典序⽐比
    较两个序列列。
    // 还是来看⼀一些示例例代码吧……
    /*
* 输⼊入个数不不定的⼀一组整数，再将这组整数按倒序输出
*/
    int main()
{
    vector<int> L;
    int x;
    while(cin >> x)
    {
        L.push_back(x);
    }
    for (int i = L.size() - 1; i >= 0; i--)
    {
        cout << L[i] << " ";
    }
    cout << endl;
    return 0;
}

string

int main()
{
    string s = "Hello!", name;
    cin >> name;
    s += name;
    s += '!';
    cout << s << endl;
    return 0;
}

/*
* 1064--Parencoding(吉林林⼤大学OJ) 题解⽚片段
* ⽤用string作为容器器,实现由P代码还原括号字符串串
*/
int main()
{
    int m;
    cin >> m; // p编码的⻓长度
    string str; // ⽤用来存放还原出来的括号字符串串
    int leftpa = 0; // 记录已经出现的左括号的总数
    for (int i = 0; i < m; i++)
    {
        int p;
        cin >> p;
        for (int j = 0; j < p - leftpa; j++)
        {
            str += '(';
        }
        str += ')';
        leftpa = p;
    }
    return 0;
}

定义stack对象：

stack<int> s;
stack<string> ss;

s.push(x); // ⼊入栈
s.pop(); // 出栈
s.top(); // 访问栈顶
s.empty(); // 当栈空时，返回true
s.size(); // 访问栈中元素个数

/*
* 1064--Parencoding（吉林林⼤大学OJ）
* string和stack实现
*/
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int m;
        cin >> m;
        string str;
        int leftpa = 0;
        for (int j = 0; j < m; j++)
        {
            int p;
            cin >> p;
            for (int k = 0; k < p - leftpa; k++)
            {
                str += '(';
            }
            str += ')';
            leftpa = p;
        }
        stack<int> s;
        for (string::iterator it = str.begin(); it != str.end(); it++)
        {
            if (*it == '(')
            {
                s.push(1);
            }
            else
            {
                int p = s.top();
                s.pop();
                cout << p << " ";
                if (!s.empty())
                {
                    s.top() += p;
                }
            }
            cout << '\n';
        }
    }
    return 0;
}

STL queue

queue<int> q;
queue<double> qq;

q.push(x); // ⼊入队列列
q.pop(); // 出队列列
q.front(); // 访问队⾸首元素
q.back(); // 访问队尾元素
q.empty(); // 判断队列列是否为空
q.size(); // 访问队列列中的元素个数

priority_queue<int> q;
priority_queue<pair<int, int> > qq; // 注意在两个尖括号之间⼀一定要留留空格，防⽌止误判
priority_queue<int, vector<int>, greater<int> > qqq; // 定义⼩小的先出队列列

priority_queue的基本操作：

q.empty() // 如果队列列为空，则返回true，否则返回false
q.size() // 返回队列列中元素的个数
q.pop() // 删除队⾸首元素，但不不返回其值
q.top() // 返回具有最⾼高优先级的元素值，但不不删除该元素
q.push(item) // 在基于优先级的适当位置插⼊入新元素

class T
{
    public:
    int x, y, z;
    T(int a, int b, int c) : x(a), y(b), z(c) {}
};
bool operator < (const T &tOne, const T &tTwo)
{
    return tOne.z < tTwo.z; // 按照z的顺序来决定tOne和tTwo的顺序
}
int main()
{
    priority_queue<T> q;
    q.push(T(4, 4, 3));
    q.push(T(2, 2, 5));
    q.push(T(1, 5, 4));
    q.push(T(3, 3, 6));
    while (!q.empty())
    {
        T t = q.top();
        q.pop();
        cout << t.x << " " << t.y << " " << t.z << '\n';
    }
    return 0;
}
/*
* 输出结果为：
* 4 4 3
* 1 5 4
* 2 2 5
* 3 3 6
*/
如果我们将第⼀一个例例⼦子中的⽐比较运算符重载为：
    bool operator < (const T &tOne, const T &tTwo)
{
    return tOne.z > tTwo.z; // 按照z的顺序来决定tOne和tTwo的顺序
}

STL map

定义map对象：

map<string, int> m;

map的基本操作：

/* 向map中插⼊入元素 */
m[key] = value; // [key]操作是map很有特⾊色的操作,如果在map中存在键值为
key的元素对, 则返回该元素对的值域部分,否则将会创建⼀一个键值为key的元素对,值域为默认值。
    所以可以⽤用该操作向map中插⼊入元素对或修改已经存在的元素对的值域部分。
    m.insert(make_pair(key, value)); // 也可以直接调⽤用insert⽅方法插⼊入元素对,insert操作会返回⼀一个
pair,当map中没有与key相匹配的键值时,其first是指向插⼊入元素对的迭代器器,其second为true;若
    map中已经存在与key相等的键值时,其first是指向该元素对的迭代器器,second为false。
    /* 查找元素 */
    int i = m[key]; // 要注意的是,当与该键值相匹配的元素对不不存在时,会创建键
值为key（当另⼀一个元素是整形时，m[key]=0）的元素对。
    map<string, int>::iterator it = m.find(key); // 如果map中存在与key相匹配的键值时,find操作将返
回指向该元素对的迭代器器,否则,返回的迭代器器等于map的end()(参⻅见vector中提到的begin()和end()
                                   操作)。
    /* 删除元素 */
    m.erase(key); // 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数。
m.erase(it); // 删除由迭代器器it所指定的元素对,并返回指向下⼀一个元素对的迭代器器。
/* 其他操作 */
m.size(); // 返回元素个数
m.empty(); // 判断是否为空
m.clear(); // 清空所有元素
Ex_One:
typedef map<int, string, less<int> > M_TYPE
    typedef M_TYPE::iterator M_IT
    typedef M_TYPR::const_iterator M_CIT
    int main()
{
    /? 17 358 v 2.1 2017.09.21
        M_TYPR myTestMap;
    myTestMap[3] = "No.3";
    myTestMap[5] = "No.5";
    myTestMap[1] = "No.1";
    myTestMap[2] = "No.2";
    myTestMap[4] = "No.4";
    M_IT itStop = myTestMap.find(2);
    cout << "myTestMap[2] = " << itStop->second << endl;
    itStop->second = "No.2 After modification";
    cout << "myTestMap[2] = " << itStop->second << endl;
    cout << "Map contents:" << endl;
    for (M_CIT it = myTestMap.begin(); it != myTestMap.end(); it++)
    {
        cout << it->second << endl;
    }
    return 0;
}
/*
* 程序的输出结果为：
* MyTestMap[2] = No.2
* MyTestMap[2] = No.2 After modification Map contents :
* No.1
* No.2 After modification
* No.3
* No.4
* No.5
*/

Ex_Two:
int main()
{
    map<string, int> m;
    m["one"] = 1;
    m["two"] = 2;
    // ⼏几种不不同的 insert 调⽤用⽅方法
    m.insert(make_pair("three", 3));
    m.insert(map<string, int>::value_type("four", 4));
    m.insert(pair<string, int>("five", 5));
    string key;
    while (cin >> key)
    {
        map<string, int>::iterator it = m.find(key);
        if (it == m.end())
        {
            cout << "No such key!" << endl;
        }
        else
        {
            cout << key << " is " << it->second << endl;
            cout << "Erased " << m.erase(key) << endl;
        }
    }
    return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com

赏

©022 张辰琦

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏