三个比较小的C++项目与简历内容(json,跳表,线程池)

对于可以写到简历上的项目,webserver已经烂大街了,所以这里放出三个百行的小项目——(json解析器,跳表,线程池)。

当然,这三个东西就是用来充数或者是"八股触发器"。所以对于有比较好的项目人来说,是比较简陋的。

当然为了当好八股触发器的作用,我会给出每个小项目可以写在简历上的东西,并且给出相应的八股内容。

(所以在阅读的时候,你可以先阅读八股内容来进行一波学习)

json解析器

内容

项目名称:使用C++17标准的json解析器

使用variant 管理json数据类型 ,string_view进行代理模式明确只读语义,optional处理非侵入式异常处理机制。

通过递归下降对json字符串进行parser,解析后支持动态修改,并重新输出json格式,接口设计便捷,使用方便。

使用

int main() {
    std::ifstream fin("json.txt");
    std::stringstream ss; ss << fin.rdbuf();
    std::string s{ ss.str() };
    auto x = parser(s).value();
    std::cout << x << "\n";
    x["configurations"].push({true});
    x["configurations"].push({Null {}});
    x["version"] = { 114514LL };
    std::cout << x << "\n";
}

八股内容

使用variant 管理json数据类型

json的数据类型有很多,我们需要维护一个type来记录当前的类型,但是我们懒,不想手动维护怎么办呢?

严格鸽:C/C++ union 使用教程 (常见操作与缺陷)

严格鸽:现代C++学习——实现多类型存储std::variant

string_view进行代理模式明确只读语义

如果我们想要强调一个东西,他是只读的,可以选择用const来修饰他。

但是C++还提供了const_cast 这种东西,所以就有了view来明确只读的语义。

讨论这个的时候还可以讨论一下所有权的概念

C++ 17 std::string_view使用介绍

严格鸽:现代C++学习 —— 为什么需要std::move

严格鸽:现代C++学习—— 什么是RAII

optional处理非侵入式异常处理机制

如果json格式串是非法的怎么办?抛出一个异常,然后catch?

当然可以,但是C++17给了我们另外的做法

茗一:C++17 新特性之 std::optional(上)

在C++23中给出了更好的东西

std::expected - cppreference.com

通过递归下降对json字符串进行parser

递归下降是常见的parser方式

严格鸽:自己写一个编程语言(3) 从json入门的语法解析

代码

#include <iostream>
#include<variant>
#include<vector>
#include<map>
#include<optional>
#include<string>
#include<fstream>
#include <sstream>
namespace json {
    
    struct Node;
    using Null = std::monostate;
    using Bool = bool;
    using Int = int64_t;
    using Float = double;
    using String = std::string;
    using Array = std::vector<Node>;
    using Object = std::map<std::string, Node>;
    using Value = std::variant<Null, Bool, Int, Float, String, Array, Object>;
    struct Node {
        Value value;
        Node(Value _value) : value(_value) {}
        Node() : value(Null{}) {}
        auto& operator[](const std::string& key) {
            if (auto object = std::get_if<Object>(&value)) {
                return  (*object)[key];
            }
            throw std::runtime_error("not an object");
        }
        auto operator[](size_t index) {
            if (auto array = std::get_if<Array>(&value)) {
                return array->at(index);
            }
            throw std::runtime_error("not an array");
        }
        void push(const Node& rhs) {
            if (auto array = std::get_if<Array>(&value)) {
                array->push_back(rhs);
            }
        }
    };

    struct JsonParser {
        std::string_view json_str;
        size_t pos = 0;

        void parse_whitespace() {
            while (pos < json_str.size() && std::isspace(json_str[pos])) {
                ++pos;
            }
        }

        auto parse_null() -> std::optional<Value> {
            if (json_str.substr(pos, 4) == "null") {
                pos += 4;
                return Null{};
            }
            return{};
        }

        auto parse_true() -> std::optional<Value> {
            if (json_str.substr(pos, 4) == "true") {
                pos += 4;
                return true;
            }
            return {};
        }

        auto parse_false() -> std::optional<Value> {
            if (json_str.substr(pos, 5) == "false") {
                pos += 5;
                return false;
            }
            return {};
        }

        auto parse_number()->std::optional<Value> {
            size_t endpos = pos;
            while (endpos < json_str.size() && (
                std::isdigit(json_str[endpos]) ||
                json_str[endpos] == 'e' ||
                json_str[endpos] == '.')) {
                endpos++;
            }
            std::string number = std::string{ json_str.substr(pos, endpos - pos) };
            pos = endpos;
            static auto is_Float = [](std::string& number) {
                return number.find('.') != number.npos ||
                    number.find('e') != number.npos;
            };
            if (is_Float(number)) {
                try {
                    Float ret = std::stod(number);
                    return ret;
                }
                catch (...) {
                    return {};
                }
            }
            else {
                try {
                    Int ret = std::stoi(number);
                    return ret;
                }
                catch (...) {
                    return {};
                }
            }
        }

        auto parse_string()->std::optional<Value> {
            pos++;// "
            size_t endpos = pos;
            while (pos < json_str.size() && json_str[endpos] != '"') {
                endpos++;
            }
            std::string str = std::string{ json_str.substr(pos, endpos - pos) };
            pos = endpos + 1;// "
            return str;
        }
        auto parse_array()->std::optional<Value> {
            pos++;// [
            Array arr;
            while (pos < json_str.size() && json_str[pos] != ']') {
                auto value = parse_value();
                arr.push_back(value.value());
                parse_whitespace();
                if (pos < json_str.size() && json_str[pos] == ',') {
                    pos++;// ,
                }
                parse_whitespace();
            }
            pos++;// ]
            return arr;
        }

        auto parse_object() ->std::optional<Value> {
            pos++;// {
            Object obj;
            while (pos < json_str.size() && json_str[pos] != '}') {
                auto key = parse_value();
                parse_whitespace();
                if (!std::holds_alternative<String>(key.value())) {
                    return {};
                }
                if (pos < json_str.size() && json_str[pos] == ':') {
                    pos++;// ,
                }
                parse_whitespace();
                auto val = parse_value();
                obj[std::get<String>(key.value())] = val.value();
                parse_whitespace();
                if (pos < json_str.size() && json_str[pos] == ',') {
                    pos++;// ,
                }
                parse_whitespace();
            }
            pos++;// }
            return obj;

        }

        auto parse_value() ->std::optional<Value> {
            parse_whitespace();
            switch (json_str[pos]) {
            case 'n':
                return parse_null();
            case 't':
                return parse_true();
            case 'f':
                return parse_false();
            case '"':
                return parse_string();
            case '[':
                return parse_array();
            case '{':
                return parse_object();
            default:
                return parse_number();
            }
        }

        auto parse() ->std::optional<Node> {
            parse_whitespace();
            auto value = parse_value();
            if (!value) {
                return {};
            }
            return Node{ *value };
        }
    };


    auto parser(std::string_view json_str) ->std::optional<Node> {
        JsonParser p{ json_str };
        return p.parse();
    }


    class JsonGenerator {
    public:
        static auto generate(const Node& node) -> std::string {
            return std::visit(
                [](auto&& arg) -> std::string {
                    using T = std::decay_t<decltype(arg)>;
                    if constexpr (std::is_same_v<T, Null>) {
                        return "null";
                    }
                    else if constexpr (std::is_same_v<T, Bool>) {
                        return arg ? "true" : "false";
                    }
                    else if constexpr (std::is_same_v<T, Int>) {
                        return std::to_string(arg);
                    }
                    else if constexpr (std::is_same_v<T, Float>) {
                        return std::to_string(arg);
                    }
                    else if constexpr (std::is_same_v<T, String>) {
                        return generate_string(arg);
                    }
                    else if constexpr (std::is_same_v<T, Array>) {
                        return generate_array(arg);
                    }
                    else if constexpr (std::is_same_v<T, Object>) {
                        return generate_object(arg);
                    }
                },
                node.value);
        }
        static auto generate_string(const String& str) -> std::string {
            std::string json_str = "\"";
            json_str += str;
            json_str += '"';
            return json_str;
        }
        static auto generate_array(const Array& array) -> std::string {
            std::string json_str = "[";
            for (const auto& node : array) {
                json_str += generate(node);
                json_str += ',';
            }
            if (!array.empty()) json_str.pop_back();
            json_str += ']';
            return json_str;
        }
        static auto generate_object(const Object& object) -> std::string {
            std::string json_str = "{";
            for (const auto& [key, node] : object) {
                json_str += generate_string(key);
                json_str += ':';
                json_str += generate(node);
                json_str += ',';
            }
            if (!object.empty()) json_str.pop_back();
            json_str += '}';
            return json_str;
        }
    };

    inline auto generate(const Node& node) -> std::string { return JsonGenerator::generate(node); }


    auto  operator << (std::ostream& out, const Node& t) ->std::ostream& {
        out << JsonGenerator::generate(t);
        return out;
    }

    
}
using namespace json;


int main() {
    std::ifstream fin("json.txt");
    std::stringstream ss; ss << fin.rdbuf();
    std::string s{ ss.str() };
    auto x = parser(s).value();
    std::cout << x << "\n";
    x["configurations"].push({true});
    x["configurations"].push({Null {}});
    x["version"] = { 114514LL };
    std::cout << x << "\n";
}

跳表

内容

项目名称:基于跳表实现的轻量级KV存储

采用skiplist作为底层数据结构,支持插入,删除,查询等常见操作。

使用C++模板编程,使用类似STL,支持自定义类型与自定义比较函数(可以传入lambda与仿函数),迭代器遍历。

使用

{
    //使用lambda
    auto cmp = [](const string& a, const string& b) {return a.length() < b.length(); };
    skip_list < string, int, decltype(cmp)> list(cmp);
    list.insert("aab", 1321);
    list.insert("hello", 54342);
    list.insert("world", 544);
    for (auto it = list.begin(); it != list.end(); it++) {
        cout << it->key << " " << it->value << endl;
    }
}

cout << "==================================" << endl;

{
    //使用仿函数
    struct cmp {
        bool operator()(int a, int b) {
            return a > b;
        }
    };
    skip_list < int, int, cmp> list{};
    for (int i = 1; i <= 10; i++)list.insert(rand() % 20, rand());
    for (auto it = list.find(10); it != list.end(); it++) {
        cout << it->key << " " << it->value << endl;
    }
}

cout << "==================================" << endl;

{
    //默认小于号
    skip_list<int, int>list;
    list.insert(1, 3);
    list.insert(1, 3);
    list.insert(4, 3);
    list.insert(5, 3);
    list.insert(1, 3);
    list.insert(4, 3);
    for (auto it = list.begin(); it != list.end(); it++) {
        cout << it->key << " " << it->value << endl;
    }

}

输出

aab 1321

world 544

hello 54342

==================================

10 31181

9 8161

7 20531

6 12560

==================================

1 3

4 3

5 3

八股内容

采用skiplist作为底层数据结构

跳表是一种引入了随机化的数据结构。

实际上,你把网上找到的跳表的图片,斜着一下看,是不是很像一个BST呢(

对于这方面的内容,还是看看oiwiki吧

跳表 - OI Wiki

使用C++模板编程

C++模板学习实践

使用类似STL,支持自定义类型与自定义比较函数

严格鸽:现代C++学习——利用模板把函数当作参数

迭代器遍历

就是在类里面还有一个内部类

比如set<int>::iterator 就是 set<int> 这个类的内部的一个类

代码

#include<iostream>
#include<string>
#include<set>
#include<time.h>
using namespace std;
template<typename T>
struct Less {
    bool operator () (const T & a , const T & b) const {
        return a < b;
    }
};
template<typename K, typename V,typename Comp = Less<K>>
class skip_list {
private:
    struct skip_list_node {
        int level;
        const K key;
        V value;
        skip_list_node** forward;
        skip_list_node() :key{ 0 }, value{ 0 }, level{ 0 }, forward{0} {}
        skip_list_node(K k, V v, int l, skip_list_node* nxt = nullptr) :key(k), value(v), level(l) {
            forward = new skip_list_node * [level + 1];
            for (int i = 0; i <= level; ++i) forward[i] = nxt;
        }
        ~skip_list_node() { delete[] forward; }
    };
    using node = skip_list_node;
    void init() {
        srand((uint32_t)time(NULL));
        level = length = 0;
        head->forward = new node * [MAXL + 1];
        for (int i = 0; i <= MAXL; i++)
            head->forward[i] = tail;
    }
    int randomLevel() {
        int lv = 1; while ((rand() & S) < PS) ++lv;
        return MAXL > lv ? lv : MAXL;
    }
    int level;
    int length;
    static const int MAXL = 32;
    static const int P = 4;
    static const int S = 0xFFFF;
    static const int PS = S / P;
    static const int INVALID = INT_MAX;
    node* head, * tail;
    Comp less;
    node* find(const K& key, node** update) {
        node* p = head;
        for (int i = level; i >= 0; i--) {
            while (p->forward[i] != tail && less(p->forward[i]->key, key)) {
                p = p->forward[i];
            }
            update[i] = p;
        }
        p = p->forward[0];
        return p;
    }
public:
    struct Iter {
        node* p;
        Iter() : p(nullptr) {};
        Iter(node* rhs) : p(rhs) {}
        node* operator ->()const { return (p);}
        node& operator *() const { return *p;}
        bool operator == (const Iter& rhs) { return rhs.p == p;}
        bool operator != (const Iter& rhs) {return !(rhs.p == p);}
        void operator ++() {p = p->forward[0];}
        void operator ++(int) { p = p->forward[0]; }
    };
   
    skip_list() : head(new node()), tail(new node()), less{Comp()} {
        init();    
    }
    skip_list(Comp _less) : head(new node()), tail(new node()),  less{_less} {
        init();
    }
    void insert(const K& key, const V& value) {
        node * update[MAXL + 1];
        node* p = find(key,update);
        if (p->key == key) {
            p->value = value;
            return;
        }
        int lv = randomLevel();
        if (lv > level) {
            lv = ++level;
            update[lv] = head;
        }
        node * newNode = new node(key, value, lv);
        for (int i = lv; i >= 0; --i) {
            p = update[i];
            newNode->forward[i] = p->forward[i];
            p->forward[i] = newNode;
        }
        ++length;
    }

    bool erase(const K& key) {
        node* update[MAXL + 1];
        node* p = find(key, update);
        if (p->key != key)return false;
        for (int i = 0; i <= p->level; ++i) {
            update[i]->forward[i] = p->forward[i];
        }
        delete p;
        while (level > 0 && head->forward[level] == tail) --level;
        --length;
        return true;
    }
    Iter find(const K&key) {
        node* update[MAXL + 1];
        node* p = find(key, update);
        if (p == tail)return tail;
        if (p->key != key)return tail;
        return Iter(p);
    }
    bool count(const K& key) {
        node* update[MAXL + 1];
        node* p = find(key, update);
        if (p == tail)return false;
        return key == p->key;
    }
    Iter end() {
        return Iter(tail);
    }   
    Iter begin() {
        return Iter(head->forward[0]);
    }
};
int main()
{
    {
        //使用lambda
        auto cmp = [](const string& a, const string& b) {return a.length() < b.length(); };
        skip_list < string, int, decltype(cmp)> list(cmp);
        list.insert("aab", 1321);
        list.insert("hello", 54342);
        list.insert("world", 544);
        for (auto it = list.begin(); it != list.end(); it++) {
            cout << it->key << " " << it->value << endl;
        }
    }

    cout << "==================================" << endl;
    
    {
        //使用仿函数
        struct cmp {
            bool operator()(int a, int b) {
                return a > b;
            }
        };
        skip_list < int, int, cmp> list{};
        for (int i = 1; i <= 10; i++)list.insert(rand()%20, rand());
        for (auto it = list.find(10); it != list.end(); it++) {
            cout << it->key << " " << it->value << endl;
        }
    }

    cout << "==================================" << endl;

    {
        //默认小于号
        skip_list<int, int>list;
        list.insert(1, 3);
        list.insert(1, 3);
        list.insert(4, 3);
        list.insert(5, 3);
        list.insert(1, 3);
        list.insert(4, 3);
        for (auto it = list.begin(); it != list.end();it++) {
            cout << it->key << " " << it->value << endl;
        }
       
    }

    {
        //可以添加 T && 实现move语义
        //添加重载 []
    }
    
}


线程池

内容

项目名称:简易线程池(C++17)

实现多线程安全的任务队列,线程池使用异步操作,提交(submit)使用与thread相同。

内部利用完美转发获取可调用对象的函数签名,lambda与function包装任务,使用RAII管理线程池的生命周期。

使用

{
    ThreadPool pool(8);
    int n = 20;
    for (int i = 1; i <= n; i++) {
        pool.submit([](int id) {
            if (id % 2 == 1) {
                this_thread::sleep_for(0.2s);
            }
            unique_lock<mutex> lc(_m);
            cout << "id : " << id << endl;
            }, i);
    }
}

八股内容

首先是多线程相关的,这里我推荐mq老师的视频

线程池的设计

Skykey:基于C++11实现线程池

实现多线程安全的任务队列

其实就是给queue加锁,这里使用了C++17的共享锁来实现类似读写锁的作用。

std::shared_mutex - cppreference.com

线程池使用异步操作

异步操作示例

packaged_task<int(int, int)> func([](int a, int b) {return a + b; });
auto ret = func.get_future();

thread t1{ [&]() {
         {unique_lock<mutex> lc(_m); cout << "======1=======\n"; }
         this_thread::sleep_for(2s);
         func(3, 5);
         {unique_lock<mutex> lc(_m); cout << "======1=======\n"; }
} };

thread t2{ [&]() {
        {unique_lock<mutex> lc(_m); cout << "======2=======\n"; }
        cout << ret.get() << "\n";
        {unique_lock<mutex> lc(_m); cout << "======2=======\n"; }
} };
{
    t1.join();
    t2.join();
}


输出

======2=======

======1=======

======1=======

8

======2=======

我们就是用的这个来把任务交给线程池,然后执行的

内部利用完美转发获取可调用对象的函数签名

李超:聊聊C++中的完美转发

lambda与function包装任务

严格鸽:c++函数进化史 (函数,函数指针,function,仿函数,lambda)

严格鸽:现代C++学习——实现一个std::function

RAII管理线程池的生命周期

就是普通的RAII了

严格鸽:现代C++学习—— 什么是RAII

代码

#include <iostream>
#include<thread>
#include<mutex>
#include <chrono>
#include<time.h>
#include<vector>
#include<queue>
#include<future>
#include <mutex>
#include <queue>
#include <functional>
#include <future>
#include <thread>
#include <utility>
#include <vector>
#include <condition_variable>
#include<string>
#include< shared_mutex>
using namespace std;

template<typename T>
struct safe_queue {
    queue<T>que;
    shared_mutex _m;
    bool empty() {
        shared_lock<shared_mutex>lc(_m);
        return que.empty();
    }
    auto size() {
        shared_lock<shared_mutex>lc(_m);
        return que.size();
    }
    void push(T& t) {
        unique_lock<shared_mutex> lc(_m);
        que.push(t);
    }
    bool pop(T& t) {
        unique_lock<shared_mutex> lc(_m);
        if (que.empty())return false;
        t = move(que.front());
        que.pop();
        return true;
    }
};
class ThreadPool {
private:
    class worker {
    public:
        ThreadPool* pool;
        worker(ThreadPool* _pool) : pool{ _pool } {}
        void operator ()() {
            while (!pool->is_shut_down) {
                {
                    unique_lock<mutex> lock(pool->_m);
                    pool->cv.wait(lock, [this]() {
                        return this->pool->is_shut_down ||
                            !this->pool->que.empty();
                        });
                }
                function<void()>func;
                bool flag = pool->que.pop(func);
                if (flag) {
                    func();
                }
            }
        }
    };
public:
    bool is_shut_down;
    safe_queue<std::function<void()>> que;
    vector<std::thread>threads;
    mutex _m;
    condition_variable cv;
    ThreadPool(int n) : threads(n), is_shut_down{ false } {
        for (auto& t : threads)t = thread{ worker(this) };
    }
    ThreadPool(const ThreadPool&) = delete;
    ThreadPool(ThreadPool&&) = delete;
    ThreadPool& operator=(const ThreadPool&) = delete;
    ThreadPool& operator=(ThreadPool&&) = delete;

    template <typename F, typename... Args>
    auto submit(F&& f, Args &&...args) -> std::future<decltype(f(args...))> {
        function<decltype(f(args...))()> func = [&f, args...]() {return f(args...); };
        auto task_ptr = std::make_shared<std::packaged_task<decltype(f(args...))()>>(func);
        std::function<void()> warpper_func = [task_ptr]() {
            (*task_ptr)();
        };
        que.push(warpper_func);
        cv.notify_one();
        return task_ptr->get_future();
    }
    ~ThreadPool() {
        auto f = submit([]() {});
        f.get();
        is_shut_down = true;
        cv.notify_all(); // 通知,唤醒所有工作线程
        for (auto& t : threads) {
            if (t.joinable()) t.join();
        }
    }
};
mutex _m;
int main()
{

    ThreadPool pool(8);
    int n = 20;
    for (int i = 1; i <= n; i++) {
        pool.submit([](int id) {
            if (id % 2 == 1) {
                this_thread::sleep_for(0.2s);
            }
            unique_lock<mutex> lc(_m);
            cout << "id : " << id << endl;
            }, i);
    }
}

全部评论
啥样才算是有价值的项目啊
8 回复 分享
发布于 2023-03-11 19:15 山东
第二个刚好在知乎看到,已经被人拿来买课了
4 回复 分享
发布于 2023-03-10 17:41 广东
ygg牛牛牛😍
3 回复 分享
发布于 2023-03-10 17:50 吉林
感谢大佬分享
2 回复 分享
发布于 2023-03-11 18:51 江西
114515(警撅
2 回复 分享
发布于 2023-03-11 22:01 安徽
我记得我之前在知乎看过这个
2 回复 分享
发布于 2023-03-23 15:36 广西
感谢分享
1 回复 分享
发布于 2023-03-18 22:18 湖北
又是ygg😍
1 回复 分享
发布于 2023-03-23 20:50 山东
不如楼主也开个课吧,我买
1 回复 分享
发布于 2023-03-25 21:59 广东
🐮
1 回复 分享
发布于 2023-03-27 13:15 广东
1 回复 分享
发布于 2023-04-03 08:33 陕西
柚子厨捏
1 回复 分享
发布于 2023-04-19 08:18 江西
感谢大佬分享
点赞 回复 分享
发布于 2023-03-10 17:19 安徽
其实可以直接std async会方便一点(
点赞 回复 分享
发布于 2023-03-11 05:38 美国
看这位大佬的帖子,学到了很多东西,感谢
点赞 回复 分享
发布于 2023-03-12 21:37 湖南
点赞 回复 分享
发布于 2023-03-13 07:46 辽宁
感谢大神分享
点赞 回复 分享
发布于 2023-03-15 02:41 天津
感谢感谢
点赞 回复 分享
发布于 2023-03-17 08:51 上海
线程池当年我也写过😂
点赞 回复 分享
发布于 2023-04-02 11:18 陕西
没有注释看着好费劲
点赞 回复 分享
发布于 2023-05-05 11:22 四川

相关推荐

评论
208
1505
分享
牛客网
牛客企业服务