C++数据结构设计题（持续更新中，欢迎勘误）
1. 生产者消费者模型
#include <bits/stdc++.h>
using namespace std;
mutex mtx;
condition_variable can_produce, can_cunsume;
queue<int> resource;
const int max_size = 20;
void consumer() {
while (true) {
unique_lock<mutex> ul(mtx);
while (resource.size() == 0) {
can_cunsume.wait(ul);
}
int cur_resource = resource.front();
cout << "consumer " << this_thread::get_id() << " consume resource: " << cur_resource << ",size: " << resource.size() << endl;
resource.pop();
can_produce.notify_all();
}
}
void producer() {
while (true) {
unique_lock<mutex> ul(mtx);
while (resource.size() == max_size)
can_produce.wait(ul);
int cur_resource = rand();
cout << "producer " << this_thread::get_id() << " produce resource: " << cur_resource << ",size: " << resource.size() << endl;
resource.push(cur_resource);
can_cunsume.notify_all();
}
}
int main() {
vector<thread> consumers(5), producers(5);
for (int i = 0; i < 5; i++) {
consumers[i] = thread(consumer);
producers[i] = thread(producer);
}
for (int i = 0; i < 5; i++) {
consumers[i].join();
producers[i].join();
}
} 2. 位图
class Bitmap {
public:
Bitmap(int range) {
v.resize(range / 32 + 1);
}
~Bitmap() {}
void set(int value) {
int index = value / 32;
int offset = value % 32;
v[index] |= (1 << offset);
}
void reset(int value) {
int index = value / 32;
int offset = value % 32;
v[index] &= ~(1 << offset);
}
bool contains(int value) {
int index = value / 32;
int offset = value % 32;
return v[index] & (1 << offset);
}
private:
vector<int> v;
};
int main() {
Bitmap bit_map(20);
for (int i = 0; i < 20; i += 2)
bit_map.set(i);
for (int i = 0; i < 20; i++)
if (bit_map.contains(i)) {
cout << i << " :exist!" << endl;
bit_map.reset(i);
}
else
cout << i << " :not exist!" << endl;
cout << "reset_result: "<< endl;
for (int i = 0; i < 20; i++)
if (bit_map.contains(i))
cout << i << " :exist!" << endl;
else
cout << i << " :not exist!" << endl;
return 0;
} 3. 排序算法
冒泡排序
void bubbleSort(vector<int>& nums) { int n = nums.size(); if (n < 2) return; for (int i = 0; i < n; i++) for (int j = 0; j < n - i - 1; j++) { if (nums[j] > nums[j + 1]) swap(nums[j], nums[j + 1]); } }插入排序
void insertSort(vector<int>& nums) { int n = nums.size(); if (n < 2) return; for (int i = 1; i < n; i++) { int curNum = nums[i]; int pre = i - 1; while (pre >= 0 && nums[pre] > curNum) { nums[pre + 1] = nums[pre]; pre--; } nums[pre + 1] = curNum; } }选择排序
void selectSort(vector<int>& nums) { int n = nums.size(); if (n < 2) return; for (int i = 0; i < n; i++) { int minIndex = i; int minNum = nums[i]; for (int j = i + 1; j < n; j++) { if (nums[j] < minNum) { minIndex = j; minNum = nums[j]; } } swap(nums[i], nums[minIndex]); } }归并排序
void merge(vector<int>& nums, int lo, int mid, int hi) { int i = lo, j = mid + 1; vector<int> temp; while (i <= mid && j <= hi) temp.push_back(nums[i] <= nums[j] ? nums[i++] : nums[j++]); while (i <= mid) temp.push_back(nums[i++]); while (j <= hi) temp.push_back(nums[j++]); for (int k = lo; k <= hi; k++) nums[k] = temp[k - lo]; } void merge_sort(vector<int>& nums, int lo, int hi) { if (lo < hi) { int mid = (hi - lo) / 2 + lo; merge_sort(nums, lo, mid); merge_sort(nums, mid + 1, hi); merge(nums, lo, mid, hi); } }堆排序
void build_heap(vector<int>& nums, int start, int end) { int father = start; int son = father * 2 + 1; while (son <= end) { if (son + 1 <= end && nums[son + 1] > nums[son]) son = son + 1; if (nums[father] > nums[son]) return; else { swap(nums[father], nums[son]); father = son; son = 2 * father + 1; } } } void heap_sort(vector<int>& nums) { int size = nums.size(); for (int i = size / 2 - 1; i >= 0; i--) build_heap(nums, i, size - 1); for (int i = size - 1; i > 0; i--) { swap(nums[0], nums[i]); build_heap(nums, 0, i - 1); } }快速排序
void quicksort(vector<int>& nums, int left, int right) { if (left >= right) return; // int randIndex = left + rand() % (right - left + 1); // swap(nums, left, randIndex); int i = left, j = right; int base = nums[left]; while (i < j) { while (nums[j] >= base && i < j)//等于号 j--; while (nums[i] <= base && i < j) i++; if (i < j) swap(nums[i], nums[j]); } swap(nums[left], nums[i]); quicksort(nums, left, i - 1); quicksort(nums, i + 1, right); }BFPRT
#include <iostream> #include <algorithm> #include <vector> using namespace std; //主函数 int BFPRT(vector<int>& nums, int left, int right, int k); //获取主元所在下标 int getPivotIndex(vector<int>& nums, int left, int right); //Partition函数 int partition(vector<int>& nums, int left, int right, int pivotIndex); //插入排序获取中位数下标 int getMedianByInsertionSort(vector<int>& nums, int left, int right); int main(){ vector<int> array{13,14,15,12,10,9,8,7,11,1,5,2,3,4,6}; int length= array.size(); printf("原始数组为：\n"); for(int i=0; i<length; i++) { cout<<array[i]<<" "; } for (int k = 1; k <= length; k++) { printf("第%d小的数是：%d", k, array[BFPRT(array, 0, length - 1, k)]); printf("此时的数组为：\n"); for(int i = 0; i < length; i++) cout<<array[i]<<" "; cout << endl << "-----------------------------------------------------" <<endl; } return 0; } int BFPRT(vector<int>& nums, int left, int right, int k) { int pivotIndex = getPivotIndex(nums, left, right); int index = partition(nums, left, right, pivotIndex); if (left == right) return left; int count = index-left+1; if(count == k) return index; else if(count > k) return BFPRT(nums, left, index-1, k); else return BFPRT(nums, index+1, right, k-count); } int getPivotIndex(vector<int>& nums, int left, int right) { if (right - left + 1 <= 5) return getMedianByInsertionSort(nums, left, right); int pos = left; for (int i = left; i + 4 < right; i += 5) { int index = getMedianByInsertionSort(nums, i, i + 4); swap(nums[pos++], nums[index]); } return BFPRT(nums, left, pos, (pos - left) / 2 + left + 1); } int partition(vector<int>& nums, int left, int right, int pivotIndex) { int i = left, j = right; int key = nums[pivotIndex]; swap(nums[left], nums[pivotIndex]); while (i < j) { while (nums[j] >= key && i < j) j--; while (nums[i] <= key && i < j) i++; if (i < j) swap(nums[i], nums[j]); } swap(nums[i], nums[left]); return i; } int getMedianByInsertionSort(vector<int>& nums, int left, int right) { for (int j = left + 1; j <= right; j++) { int i = j - 1; int curNum = nums[j]; while (i >= left && curNum < nums[i]) { nums[i + 1] = nums[i]; i--; } nums[i + 1] = curNum; } return (right - left) / 2 + left; }
4. 类大小测试
class A {
};
class B {
int a;
char* p;
};
class C {
public:
C(){}
virtual ~C(){}
private:
int a;
char* p;
};
class CChild : C {
public:
CChild(){}
virtual ~CChild(){}
private:
int c;
};
class D {
virtual void funA(){}
virtual void funB(){}
};
int main () {
A* a1 = new A();
A* a2 = new A();
cout << sizeof A() << endl; // 1 大小为1方便地址分配 栈向下增长，堆向上
cout << &a1 << "," << &a2 << endl; // 0x7ffef12ba0b8,0x7ffef12ba0b0
cout << a1 << "," << a2 << endl; // 0x2170c20,0x2170c40
cout << sizeof B() << endl; // 16 字节对齐
cout << sizeof C() << endl; // 24 字节对齐 + 虚指针
cout << sizeof CChild() << endl; // 24 父类 + 子类成员（字节对齐）
cout << sizeof D() << endl; // 8 多个虚函数等于一个虚函数
} 5. 宏定义MAX函数
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
6. LRU
#include <iostream>
#include <unordered_map>
using namespace std;
struct Dlist
{
Dlist* prev;
Dlist* next;
int key, value;
Dlist() : key(0), value(0), prev(nullptr), next(nullptr) {};
Dlist(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {};
};
class LRUCache {
public:
LRUCache(int capacity) : m_capicity(capacity) {
m_head = new Dlist();
m_tail = new Dlist();
m_head->next = m_tail;
m_tail->prev = m_head;
m_position.clear();
}
int get(int key) {
if (m_position.count(key) == 0)
return -1;
Dlist* curNode = m_position[key];
remove(curNode);
insert(curNode);
return curNode->value;
}
void put(int key, int value) {
if (m_position.count(key) == 0)
{
Dlist* newNode = new Dlist(key, value);
insert(newNode);
m_position[key] = newNode;
if (m_position.size() > m_capicity)
{
//淘汰旧的
Dlist* last = m_tail->prev;
remove(last);
m_position.erase(last->key);
delete last;
last = nullptr;
}
}
else
{
Dlist* targetNode = m_position[key];
remove(targetNode);
targetNode->value = value;
insert(targetNode);
}
}
private:
Dlist* m_head;
Dlist* m_tail;
unordered_map<int, Dlist*> m_position;
int m_capicity;
void insert(Dlist* node)
{
node->prev = m_head;
node->next = m_head->next;
m_head->next->prev = node;
m_head->next = node;
}
void remove(Dlist* node)
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
}; 7. 自定义string
#include <iostream>
#include <assert.h>
using namespace std;
int my_strlen(const char* p)
{
int count = 0;
assert(p);
while (*p != '\0')
{
p++;
count++;
}
return count;
}
char* my_strcopy(char* dest, char* source)
{
assert(!dest);
assert(!source);
char* res = dest;
while ((*dest++ = *source) != '\0');
return res;
}
char* my_memcopy(char* dest, const char* source, int count)
{
assert(!dest);
assert(!source);
char* res = dest;
if (dest >= source && dest <= source + count - 1)//高地址开始复制
{
dest += count - 1;
source += count - 1;
while (count--)
*dest-- = *source--;
}
else
while (count--)
*dest++ = *source++;
return res;
}
char* my_strcopy_mem(char* dest, const char* source)
{
assert(!dest);
assert(!source);
char* res = dest;
my_memcopy(dest, source, my_strlen(source) + 1);
return res;
}
class myString
{
private:
char* p;
int* count;
public:
myString(const char* str = "") {
if (str == nullptr)
{
p = new char[1];
*p = '\0';
}
else
{
p = new char[my_strlen(p) + 1];
my_strcopy_mem(p, str);
}
*count = 1;
}
~myString() {
if (p != nullptr && --(*count) == 0)
{
delete[] p;
p = nullptr;
delete[] count;
count = nullptr;
}
}
myString(const myString& str) : p(str.p), count(str.count) {
(*count)++;
}
myString& operator=(const myString& str) {
if (this != &str)
{
if (p != nullptr && --(*count) == 0)
{
delete[] p;
delete[] count;
}
p = str.p;
count = str.count;
*(count)++;
}
return *this;
}
};
int main() {
auto a = new int[5];
cout << sizeof *((int*)a - 2) << endl;
} 8. 自定义vector
#include <bits/stdc++.h>
using namespace std;
class Vector {
private:
int* head;
int* tail;
int* end;
public:
Vector() : head(nullptr), tail(nullptr), end(nullptr) {}
~Vector() {
if (head != nullptr) {
delete[] head;
head = tail = end = nullptr;
}
}
size_t size() {
return tail - head;
}
size_t capacity() {
return end - head;
}
void expand(size_t new_cpt) {
if (new_cpt <= capacity())
return;
cout << "expand" << endl;
int* new_head = new int[new_cpt];
int* new_tail = new_head;
int* new_end = new_head + new_cpt;
int* cur = head;
while (cur < end) {
*new_tail++ = *cur++;
}
delete[] head;
head = new_head;
tail = new_tail;
end = new_end;
}
void push_back(int value) {
if (tail == end) {
size_t new_capacity = (end == nullptr ? 3 : capacity() * 2);
expand(new_capacity);
}
*tail++ = value;
}
void pop_back() {
if (tail != head && tail != nullptr) {
--tail;
}
}
int& operator[](int index) {
return *(head + index);
}
};
int main() {
Vector v;
for (int i = 0; i < 20; i++)
v.push_back(i);
for (int i = 0; i < 20; i++)
cout << v[i] << endl;
} 9. 版本号哈希（o1时间设置所有value）
#include <bits/stdc++.h>
using namespace std;
class NewHashMap {
private:
unordered_map<int, pair<int, int>> ump;
int all_value;
unsigned int old_version;
unsigned int max_version;
public:
NewHashMap() : all_value(0), old_version(0), max_version(0) {}
~NewHashMap() {}
int Get(int key) {
if (ump.count(key) != 0) {
if (ump[key].second > old_version)
return ump[key].first;
else
return all_value;
} else return -1;
}
void Set(int key, int value) {
max_version++;
ump[key] = make_pair(value, max_version);
}
void SetAll(int value) {
max_version++;
old_version = max_version;
all_value = value;
}
};
int main() {
NewHashMap temp;
for (int i = 0; i < 10; i++)
temp.Set(i, i * i);
for (int i = 0; i < 10; i++)
cout << temp.Get(i) << ",";
cout << endl;
temp.SetAll(500);
for (int i = 0; i < 10; i++)
cout << temp.Get(i) << ",";
cout << endl;
temp.Set(1, 100);
for (int i = 0; i < 10; i++)
cout << temp.Get(i) << ",";
}
10. shared_ptr
template <typename T>
class Shared_ptr {
private:
int* count;
T* px;
public:
explicit Shared_ptr(T* p = nullptr) : px(p) {
count = new int(1);
}
~Shared_ptr() {
if (-- * count == 0) {
delete px;
delete count;
}
}
Shared_ptr(const Shared_ptr& s) : px(s.px), count(s.count) {
++* count;
}
Shared_ptr& operator = (const Shared_ptr& s) {
if (this != &s) {
px = s.px;
count = s.count;
++* count;
}
return *this;
}
}; 11. 单例模式
#include <iostream>
using namespace std;
class singleton
{
private:
singleton(){};
singleton (const singleton& temp) = delete;
singleton& operator = (const singleton& temp) = delete;
public:
~singleton(){};
static singleton* getInstance()
{
static singleton instance;
return &instance;
}
/*
static singleton& getInstance()
{
static singleton instance;
return instance;
}
*/
};
#include <mutex>
class singleton1
{
private:
singleton1(){};
singleton1 (const singleton1& temp) = delete;
singleton1& operator = (const singleton1& temp) = delete;
public:
~singleton1(){};
static singleton1* m_Instance;
static mutex mtx;
static singleton1* getInstance()
{
if (m_Instance == nullptr)
{
unique_lock<mutex> ul(mtx);
if (m_Instance == nullptr)
m_Instance = new singleton1();
}
return m_Instance;
}
};
singleton1* singleton1::m_Instance = new singleton1();
mutex singleton1::mtx; 12. 自旋锁实现
#include <atomic>
using namespace std;
class spin_lock {
private:
atomic<bool> flag{false}; //false不加锁、true加锁
public:
spin_lock() = default;
spin_lock(const spin_lock&) = delete;
spin_lock& operator=(const spin_lock&) = delete;
void lock() {
bool expected = false;
while (!flag.compare_exchange_strong(expected, true))
expected = false;
}
void unlock() {
flag.store(false);
}
}; 13. 线程安全队列
#include <iostream>
#include <queue>
#include <mutex>
#include <condition_variable>
using namespace std;
template<typename T>
class thread_safe_queue {
public:
thread_safe_queue() {};
~thread_safe_queue() {};
void push(T temp) {
unique_lock<mutex> ul(m_mtx);
m_queue.push(move(temp));
cout << "push!" << endl;
m_not_empty_cv.notify_one();
}
void wait_and_pop() {
unique_lock<mutex> ul(m_mtx);
m_not_empty_cv.wait(ul, [this](){
cout << "waiting until not empty" << endl;
return !this->m_queue.empty();
});
m_queue.pop();
cout << "pop!" << endl;
}
bool try_pop() {
unique_lock<mutex> ul(m_mtx);
if (m_queue.empty())
return false;
m_queue.pop();
return true;
}
bool is_empty() {
unique_lock<mutex> ul(m_mtx);
return m_queue.empty();
}
private:
queue<T> m_queue;
mutex m_mtx;
condition_variable m_not_empty_cv;
}; 14. 线程池
#include <functional>
#include <future>
#include <vector>
#include <mutex>
#include <queue>
#include <thread>
#include <utility> //move forward pair等等
#include "thread_safe_queue.cc"
using namespace std;
class threadpool {
private:
class thread_worker {
private:
int m_id;
threadpool* m_pool;
public:
thread_worker(threadpool* pool, const int id)
: m_pool(pool), m_id(id) {
}
void operator() () {
function<void()> func;
bool deququed;
while (!m_pool->m_shutdown) {
unique_lock<mutex> ul(m_pool->m_mtx);
if (m_pool->m_queue.is_empty()) {
m_pool->m_cv.wait(ul);
}
m_pool->m_queue.push(func);
func();
}
}
};
bool m_shutdown;
thread_safe_queue<function<void()>> m_queue;
vector<thread> m_threads;
mutex m_mtx;
condition_variable m_cv;
public:
threadpool(const int thread_num) : m_threads(vector<thread>(thread_num)), m_shutdown(false) {}
threadpool(const threadpool&) = delete;
threadpool(threadpool&&) = delete;
threadpool& operator = (const threadpool&) = delete;
threadpool& operator = (threadpool&&) = delete;
//init
void init() {
for (int i = 0; i < m_threads.size(); i++)
m_threads[i] = thread(thread_worker(this, i));
}
void shutdown() {
m_shutdown = true;
m_cv.notify_all();
for (int i = 0; i < m_threads.size(); i++) {
if (m_threads[i].joinable())
m_threads[i].join();
}
}
template<typename T, typename...Args>
auto submit(T&& t, Args&&... args) -> future<decltype(t(args...))> {
function<decltype(t(args...))()> func = bind(forward<T>(t), forward<Args...>(args)...);
auto task_ptr = make_shared<packaged_task<decltype(f(args...))()>>(func);
function<void()> wrapper_func = [task_ptr]() {
(*task_ptr);
};
m_queue.push(wrapper_func);
m_cv.notify_one();
return task_ptr->get_future();
}
};
15. 并查集
#include <iostream>
#include <vector>
using namespace std;
class unionFind
{
private:
int count;
vector<int> parent;
vector<int> weight;
public:
unionFind(int num)
{
count = num;
for (int i = 0; i < num; i++)
{
weight[i] = 1;
parent[i] = i;
}
};
~unionFind() {};
int find(int x)
{
while (parent[x] != x)
{
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void unionNode(int p, int q) {
int root_p = find(p);
int root_q = find(q);
if (root_q == root_p)
return;
if (weight[root_p] > weight[root_q])
{
parent[root_q] = root_p;
weight[root_p] += weight[root_q];
}
else
{
parent[root_p] = root_q;
weight[root_q] += weight[root_p];
}
count--;
}
bool isConnected(int p, int q) {
return find(p) == find(q);
}
}; 16. unique_ptr
template <typename T>
class Unique_ptr {
private:
T* mPtr;
public:
explicit Unique_ptr(T* p = nullptr) : mPtr(p) {}
~Unique_ptr() {
if (mPtr)
delete mPtr;
}
Unique_ptr(const Unique_ptr& up) = delete;
Unique_ptr& operator = (const Unique_ptr& up) = delete;
Unique_ptr(const Unique_ptr&& up) noexcept mPtr(p.mPtr){
p.mPtr = nullptr;
}
Unique_ptr& operator = (const Unique_ptr&& up) noexcept {
if (this != &up) {
if (mPtr)
delete mPtr;
mPtr = up.mPtr;
up.mPtr = nullptr;
}
return *this;
}
}; 17. 无锁队列实现
#ifndef _UNLOCK_QUEUE_H
#define _UNLOCK_QUEUE_H
class unlock_queue
{
private:
unsigned char* m_pBuffer;
unsigned int m_Size;
unsigned int m_In;
unsigned int m_Out;
inline bool is_power_of_2(unsigned int num) {return (num != 0 && num & (num - 1) == 0);}
unsigned long roundup_power_of_2(unsigned long num);
public:
unlock_queue(int size);
virtual ~unlock_queue();
bool initialize();
unsigned int put(const unsigned char* pBuffer, unsigned int len);
unsigned int get(const unsigned char* pBuffer, unsigned int len);
inline void clean() {m_In = m_Out = 0;}
inline unsigned int get_data_length() const {return m_Out - m_In;}
};
#endif
//cpp
#include <algorithm>
#include "unlock_queue.h"
unlock_queue::unlock_queue(int size) : m_pBuffer(nullptr), m_Size(si***(0), m_Out(0)
{
if (!is_power_of_2(size))
{
m_Size = roundup_power_of_2(size);
}
}
unlock_queue::~unlock_queue()
{
if (m_pBuffer != nullptr)
{
delete[] m_pBuffer;
m_pBuffer = nullptr;
}
}
bool unlock_queue::initialize()
{
m_pBuffer = new unsigned char[m_Size];
if (!m_pBuffer)
return false;
m_In = m_Out = 0;
return true;
}
unsigned long unlock_queue::roundup_power_of_2(unsigned long num)
{
if (num & (num - 1) == 0)
return num;
unsigned long temp = (unsigned long)((unsigned long)~0);
unsigned long andv = ~(temp & (temp >> 1));
while ((andv & num) == 0)
andv = andv >> 1;
return andv << 1;
}
unsigned int unlock_queue::put(const unsigned char* pBuffer, unsigned int len)
{
unsigned int l;
len = std::min(len, m_Si*** + m_Out);
// 内存屏障
__sync_synchronize();
l = std::min(len, m_Si*** & (m_Size - 1)));
memcpy(m_pBuffer + (m_In & (m_In & (m_Size - 1)), pBuffer, l));
memcpy(m_pBuffer, pBuffer + l, len - l);
__sync_synchroni*** += len;
return len;
}
unsigned int unlock_queue::get(const unsigned char* pBuffer, unsigned int len)
{
unsigned int l;
len = std::min(len, m_In - m_Out);
// 内存屏障
__sync_synchronize();
l = std::min(len, m_Size - (m_Out & (m_Size - 1)));
memcpy(pBuffer, m_pBuffer + (m_In & (m_Out & (m_Size - 1)), l));
memcpy(pBuffer + l, m_pBuffer, len - l);
__sync_synchronize();
m_Out += len;
return len;
} 18. 字典树（前缀树）
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));
}
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = this;
for (char c : word) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return node->isEnd;
}
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c-'a'];
if (node == NULL) {
return false;
}
}
return true;
}
}; 19. 树状数组
class F_Tree
{
private:
vector<int> tree;
int len;
//lowbit函数
int lowbit(int x)
{
return x & (-x);
}
public:
F_Tree(int n) : len(n)
{
tree.resize(n + 1, 0);
}
~F_Tree(){}
//单点更新、由下至上
void add(int index, int value)
{
while (index <= len)
{
tree[index] += value;
index += lowbit(index);
}
}
//查询前缀和
int query(int index)
{
int res = 0;
while (index > 0)
{
res += tree[index];
index -=lowbit(index);
}
return res;
}
}; 20. 环形队列
循环数组
class RingBuffer { private: int* m_buffer; int m_length; int m_size; int head; int tail; public: RingBuffer(int size) : m_size(size) { m_buffer = new int(size); m_length = 0; head = 0; tail = 0; } ~RingBuffer() { delete[] m_buffer; m_buffer = 0; } void clear() { m_length = 0; head = 0; tail = 0; } bool isFull() { return m_length == m_size; } bool isEmpty() { return m_length == 0; } int get_length() { return m_length; } void push(int value) { assert (!isFull()); m_buffer[tail] = value; tail = (tail + 1) % m_size; m_length++; } void pop() { assert(!isEmpty()); head = (head + 1) % m_size; m_length--; } int& operator[] (int index) { assert (index < m_length); return m_buffer[(head + index) % m_size]; } };环形缓存
class RingBuffer2 { private: char* buffer; int head; int tail; int size; int capacity; public: RingBuffer2(int cp) : capacity(cp) { buffer = new char[cp]; head = 0; tail = 0; size = 0; } ~RingBuffer2() { delete[] buffer; buffer = nullptr; } bool full() { return capacity == size; } bool empty() { return size == 0; } int get_size() { return size; } int write(char* src, int len) { int cur_len = 0; for (int i = 0; i < len; i++) { if (full()) break; buffer[tail] = src[i]; tail = (tail + 1) % capacity; size++; cur_len++; } return cur_len; } int read(char* src, int len) { int cur_len = min(len, size); for (int i = 0; i < cur_len; i++) { src[i] = buffer[head]; head = (head + 1) % capacity; size--; } return cur_len; } char& operator[] (int index) { return buffer[(head + index) % capacity]; } };
查看30道真题和解析