cpp c++面试常考算法题汇总

THE LAST TIME

❝
The last time, I have learned

希望看到的人，能够对他的学习、工作有帮助，同时也希望有能力的人可以一起来完善此文档，让它可以发挥出更大的价值。

手写c++的unique_ptr

实际的 std::unique_ptr 还包括更多的功能，例如自定义删除器、数组支持等

template <typename T>class unique_ptr {public:explicit unique_ptr(T* ptr = nullptr) : ptr_(ptr) {}~unique_ptr() { delete ptr_; }// 删除复制构造函数和复制赋值运算符unique_ptr(const unique_ptr&) = delete;unique_ptr& operator=(const unique_ptr&) =delete;  // 提供移动构造函数和移动赋值运算符unique_ptr(unique_ptr&&// other) noexcept : ptr_(other.ptr_) { other.ptr_ = nullptr; }unique_ptr& operator=(unique_ptr&& other) noexcept {    if (this != &other) {        delete ptr_;        ptr_ = other.ptr_;        other.ptr_ = nullptr;    }    return *this;}T* operator->() { return ptr_; }T& operator*() { return *ptr_; }private:T* ptr_;};

手写c++的shared_ptr

template <typename T>class tiny_shared_ptr {public:tiny_shared_ptr(T* ptr = nullptr) : _ptr(ptr), _count(new size_t(1)) {    if (_ptr == nullptr) {        *_count = 0;    }}tiny_shared_ptr(const tiny_shared_ptr<T>& other) : _ptr(other._ptr), _count(other._count) {    if (_ptr) {        (*_count)++;    }}tiny_shared_ptr<T>& operator=(const tiny_shared_ptr<T>& other) {    if (this != &other) {        release_source();        _ptr = other._ptr;        _count = other._count;        if (_ptr) {            (*_count)++;        }    }    return *this;}T* operator->() const {    return _ptr;}int use_count() const {    return (_count ? *_count : 0);}~tiny_shared_ptr() {    release_source();}private:void release_source() {    if (_count) {        (*_count)--;        if (*_count == 0) {            delete _ptr;            delete _count;        }    }}T* _ptr;size_t* _count;};

手写c++的string

#include <iostream>#include <cstring>using namespace std;class MyString {public:MyString() : m_data(nullptr), m_size(0) {}MyString(const char* str) {    m_size = strlen(str);    m_data = new char[m_size + 1];    strcpy(m_data, str);}// 拷贝构造函数MyString(const MyString& other) {    m_size = other.m_size;    m_data = new char[m_size + 1];    strcpy(m_data, other.m_data);}// 移动构造函数MyString(MyString&& other) {    m_size = other.m_size;    m_data = other.m_data;    other.m_size = 0;    other.m_data = nullptr;}~MyString() {    if (m_data != nullptr) {        delete[] m_data;        m_data = nullptr;        m_size = 0;    }}MyString& operator=(const MyString& other) {    if (this != &other) {        if (m_data != nullptr) {            delete[] m_data;        }        m_size = other.m_size;        m_data = new char[m_size + 1];        strcpy(m_data, other.m_data);    }    return *this;}const char* c_str() const {    return m_data;}private:char* m_data;size_t m_size;};

手撕完美转发

/**   *  @brief  Forward an lvalue.   *  @return The parameter cast to the specified type.   *   *  This function is used to implement "perfect forwarding".   */template<typename _Tp>constexpr _Tp&&forward(typename std::remove_reference<_Tp>::type& __t) noexcept{ return static_cast<_Tp&&>(__t); }/**   *  @brief  Forward an rvalue.   *  @return The parameter cast to the specified type.   *   *  This function is used to implement "perfect forwarding".   */template<typename _Tp>constexpr _Tp&&forward(typename std::remove_reference<_Tp>::type&& __t) noexcept{    static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"    " substituting _Tp is an lvalue reference type");    return static_cast<_Tp&&>(__t);}

如何用c实现多态

定义基类的成员是函数指针，用于实现多态
派生类通过组合的方式（非继承）
派生类定义函数，构造时初始化对应函数到函数指针是上
通过同名的函数指针调用

#include <stdio.h>// 基类结构体struct Shape {void (*draw)(struct Shape *);  // 1. 成员是函数指针，用于实现多态};                                 // 派生类结构体 Circlestruct Circle {struct Shape base;  // 基类 2. 通过组合的方式int radius;};// 派生类结构体 Squarestruct Square {struct Shape base;  // 基类int side;};// 基类的 draw 函数实现void drawShape(struct Shape *shape) { printf("Drawing a shape\\n"); }// 派生类 Circle 的 draw 函数实现void drawCircle(struct Shape *shape) {    struct Circle *circle = (struct Circle *)shape;    printf("Drawing a circle with radius %d\\n", circle->radius);}// 派生类 Square 的 draw 函数实现void drawSquare(struct Shape *shape) {    struct Square *square = (struct Square *)shape;    printf("Drawing a square with side %d\\n", square->side);}int main() {    struct Circle circle = {{drawCircle}, 5};  // 3.定义并在类中初始化函数指针    struct Square square = {{drawSquare}, 4};    // 拿到各个结构体里的基类（作为一个成员变量）    struct Shape *shapes[] = {(struct Shape *)&circle,    (struct Shape *)&square};  // 4.通过指针调用    for (int i = 0; i < 2; i++) {        shapes[i]->draw(shapes[i]);    }    return 0;}

手撕vector

#include<bits/stdc++.h>using namespace std;template<typename T>class Allocator{public ://开辟释放内存T* allocate(int size){    return (T*)malloc(sizeof(T)*size);}T*deallocate(T* p){    free(p);}//构造析构void construct(T*p,const T &val){    new (p)T(val);//定位new}void destory(T*p){    p->~T();//调用析构函数}};template<typename T,typename Alloc=Allocator<T> >class vvecotr{public ://构造函数vvecotr(int size=20){//多少个元素。    alloc = new Allocator<T>();    _begin = alloc->allocate(size);//开辟多少个内存    _end = _begin+size;    _now = _begin; }//析构函数~vvecotr(){    free(_begin);    delete alloc;}//拷贝构造函数vvecotr(const vvecotr<T>&vec){//拷贝构造函数    alloc = new Allocator<T>();    int size = vec._end-vec._begin;    _begin = alloc->allocate(size);    _end = _begin+size;    _now=_begin;    T *p=vec._begin;    for(;p!=vec._now;p++,_now++){        alloc->construct(_now,*p);    }}//拷贝赋值构造函数vvecotr& operator=(const vvecotr<T>&vec){    if(this==&vec)return *this;    alloc->deallocate(_begin);    alloc = new Allocator<T>();    int size = vec._end-vec._begin;    _begin = alloc->allocate(size);    _end = _begin+size;    _now=_begin;    T *p=vec._begin;    for(;p!=vec._now;p++,_now++){        alloc->construct(_now,*p);    }    return *this;}vvecotr( vvecotr<T>&&vec){    cout<<"vvecotr( vvecotr<T>&&vec){"<<endl;    alloc = vec.alloc;    _begin=vec._begin;    _now = vec._now;    _end = vec._end;    vec._begin=vec._end=vec._now=nullptr;    vec.alloc=nullptr;}vvecotr & operator=( vvecotr<T>&&vec){    //不会出现自赋值    alloc = vec.alloc;    _begin=vec._begin;    _now = vec._now;    _end = vec._end;    vec._begin=vec._end=vec._now=nullptr;    vec.alloc=nullptr;    return *this;}void push_back(const T&val){    if(_now==_end){        resize();    }    alloc->construct(_now,val);    _now++;}void pop_back(){    if(_now != _begin){        alloc->destory(_now--);    }}T& operator[](int index){    return _begin[index];}bool empty(){    return _now==_begin;}int size(){    return _now-_begin;}void show(){    T*p =_begin;    while(p!=_now){        cout<< *p <<" ";        p++;    }    cout<<endl;}private:T* _begin ;T* _now;T* _end;Alloc *alloc;void resize(){    int size=_end-_begin;    T *p=alloc->allocate(size*2);    for(int i=0;i<size;i++){        p[i]=_begin[i];    }    alloc->deallocate(_begin);    _begin = p;    _now=p+size;    _end=p+size*2;}};vvecotr<int> get(){    vvecotr<int>vec(50);    for(int i=0;i<=5;i++)vec.push_back(i);    return vec;   }int main(){    vvecotr<int>vec(50);    for(int i=0;i<=15;i++)vec.push_back(i);    vec.show();           //测试右值拷贝构造    // vvecotr<int> a = std::move(vec);    // cout<<a.size()<<endl;    //测试右值拷贝赋值    // vvecotr<int>a;    // a=get();    // a.show();    return 0;}

手撕线程池

#include <iostream>#include <unistd.h>#include <queue>#include <vector>#include <thread>#include <mutex>#include <condition_variable>#include <functional>using namespace std;class ThreadPool {public:ThreadPool(size_t numThreads) : stop(false) {    for (size_t i = 0; i < numThreads; ++i) {        threads.emplace_back([this] {            while (true) {                std::function<void()> task;                {                    std::unique_lock<std::mutex> lock(queueMutex);  // lock                    condition.wait(lock, [this] { return stop || !tasks.empty(); });                    if (stop && tasks.empty()) {                        return;                    }                    task = std::move(tasks.front());                    tasks.pop();                }                task();            }        });    }}template <class F, class... Args>void enqueue(F&& f, Args&&... args) {    {        std::unique_lock<std::mutex> lock(queueMutex);        tasks.emplace([f, args...] { f(args...); });    }    condition.notify_one();  // wake up thread}~ThreadPool() {    {        std::unique_lock<std::mutex> lock(queueMutex);        stop = true;    }    condition.notify_all();    for (std::thread& thread : threads) {        thread.join();    }}private:std::vector<std::thread> threads;std::queue<std::function<void()>> tasks;std::mutex queueMutex;std::condition_variable condition;bool stop;};void printNumber(int num) {    sleep(5);  // ssimulate operational implementation    std::cout << num << std::endl;}int main() {    ThreadPool pool(4);    // submit tasks to thread pool    for (int i = 0; i < 10; ++i) {        pool.enqueue(printNumber, i);    }    // wait for all tasks to be completed    std::this_thread::sleep_for(std::chrono::seconds(1));    return 0;}