前面还有两大题，单选题和多选题，1.5小时，期间遇到CLion无法输入EOF（后来发现是CMD+D以前做的题的测试样例都是先输入多少样例然后再输入样例的），前面基本上电脑上没调试直接交了都通过了。做到附加题剩20分钟，C++的thread库以前没用过，最后20分钟就在用pthread乱写，最后没提交。（当然现在已经学习过了，闭卷和可以看文档还是有挺大区别的）

C++ Basics

I. Remove the Duplicates(Vector Basics)

Description

Given a single line of integers separated by space, store them in a vector and then remove all the duplicates in the array. It is required that the result should be in the original order. i.e. Remove all the replicas except the first occurrence.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> v;
    vector<int> mark;

    int tmp;
    while(cin >> tmp) {
        v.push_back(tmp);
        cout << endl << tmp;
    }

    for(auto iter = v.begin(); iter != v.end(); advance(iter, 1)) {
        if(find(mark.begin(), mark.end(), *iter) == mark.end()) mark.push_back(*iter);
        else {
            auto t = iter;
            iter = prev(iter);
            v.erase(t);
        }
    }

    for(auto e: v) cout << e << " ";

    return 0;
}

II. The Largest Most Occurrence

• Remove from vector in an iteration

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    vector<int> v;

    int t; cin >> t;
    int tmp;
    while(t--) {
        cin >> tmp;
        v.push_back(tmp);
    }

    sort(v.begin(), v.end());

    int m;
    int m_count = 0;
    int count = 0;
    int curr = *v.begin();
    int pre = *v.begin();

    for(auto e: v) {
        if(e == curr) count++;
        else {
            if(count >= m_count) {
                m_count = count;
                m = pre;
            }
            count = 1;
            curr = e;
        }
        pre = e;
    }
    if(count >= m_count) m = pre;

    cout << m;

    return 0;
}

III. Sort Point

• Overload the < operator for Point

#include <iostream>
#include <vector>
#include <algorithm>

struct Point{
    int x;
    int y;
};

bool operator<(Point& const p1, const Point& p2) {
    if(p1.x < p2.x) return true;
    if(p1.x == p2.x) return p1.y < p2.y;
}

int main() {
    int x = 0;
    int y = 0;
    std::vector<Point> vec;

    while(std::cin >> x >> y) {
        Point p;
        p.x = x;
        p.y = y;
        vec.push_back(p);
    }

    std::sort(vec.begin(), vec.end());

    for(auto iter = vec.begin(); iter != vec.end(); ++iter) {
        std::cout << iter->x << " " << iter->y << std::endl;
    }

    return 0;
}

IV. Scoped Pointer

• Variable Lifecycle
• Operator Overloading

#include <iostream>

class ScopedPtr{
    int* ptr_n;
public:
    ScopedPtr(int* ptr_n)
            :
            ptr_n(ptr_n)
    {}

    ~ScopedPtr()
    {
        delete ptr_n;
    }

    int* get_n()
    {
        return ptr_n;
    }

    void set_n(int n)
    {
        *this->ptr_n = n;
    }

    ScopedPtr& operator*= (int i)
    {
        set_n(*get_n() * i);
        return *this;
    }

    ScopedPtr& operator*()
    {
        return *this;
    }
};

std::ostream& operator<< (std::ostream& os, ScopedPtr& ptr)
{
    os << *ptr.get_n();
    return os;
}

void test(int n) {
    ScopedPtr ptr(new int(n));

    *ptr *= 2;

    std::cout << *ptr << std::endl;
}

int main() {
    int n = 0;
    std::cin >> n;

    test(n);
    return 0;
}

附加题

• Multi-threading-safe hash table

Sample Input

(Different from the one given) The first line is the number of threads and followed by the insertion and queries. If an entry is found, return the value; otherwise, return “none”(quotation marks excluded).

4
get a
set a 1
set b 2
get b
set c 1
get a
get c
get d

Submission

I have never used the thread library before so I failed to write the program. This program is written after the exam. The program is actually easy if you’re familiar with the library(easier than pthread.h).

#include<iostream>
#include<string>
#include<thread>
#include<map>

std::map<std::string, std::string> m;
std::mutex in_mutex;
std::mutex out_mutex;
std::mutex m_mutex;

void set(const std::string &key, const std::string &value)
{
    m.insert(std::make_pair(key, value));
}

std::string get(const std::string &key)
{
    auto res = m.find(key);
    if(res== m.end()) return "none";

    return res->second;
}


void worker()
{
    std::unique_lock<std::mutex>lck{in_mutex};

    std::string instruction;
    while(std::cin >> instruction) {
        if(instruction == "set") {
            std::string key; std::cin >> key;
            std::string value; std::cin >> value;
            std::unique_lock<std::mutex>m_lck{m_mutex};
            set(key, value);
            m_lck.unlock();
        }
        if(instruction == "get") {
            std::string key; std::cin >> key;
            std::unique_lock<std::mutex>m_lck{m_mutex};
            std::unique_lock<std::mutex>out_lck{out_mutex};
            std::cout << get(key) << std::endl;
            out_lck.unlock();
            m_lck.unlock();
        }
    }

    lck.unlock();
}

int main()
{
    int n_threads; std::cin >> n_threads;

    while(n_threads--) {
        std::thread t{worker};
        t.join();
    }

    return 0;
}

References

1. http://www.cplusplus.com/reference/algorithm/find/