三个比较小的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来明确只读的语义。
讨论这个的时候还可以讨论一下所有权的概念
optional处理非侵入式异常处理机制
如果json格式串是非法的怎么办？抛出一个异常，然后catch？
当然可以，但是C++17给了我们另外的做法
茗一：C++17 新特性之 std::optional（上）
在C++23中给出了更好的东西
std::expected - cppreference.com
通过递归下降对json字符串进行parser
递归下降是常见的parser方式
代码
#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吧
使用C++模板编程
使用类似STL，支持自定义类型与自定义比较函数
迭代器遍历
就是在类里面还有一个内部类
比如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老师的视频
线程池的设计
实现多线程安全的任务队列
其实就是给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=======
我们就是用的这个来把任务交给线程池，然后执行的
内部利用完美转发获取可调用对象的函数签名
lambda与function包装任务
严格鸽：c++函数进化史 （函数，函数指针，function，仿函数，lambda）
严格鸽：现代C++学习——实现一个std::function
RAII管理线程池的生命周期
就是普通的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);
}
}
数字马力一面92人在聊
