当前位置： 首页 > news >正文

网站怎么做流量统计百度广告联盟app

news 2025/7/21 11:07:14
网站怎么做流量统计,百度广告联盟app,济阳做网站公司,天津制作网站首页1.6 STL 模板 模板底层实现：编译器会对函数模板进行两次编译， 在声明的地方对模板代码本身进行编译， 在调用的地方对参数替换后的代码进行编译。 模板传参分析 模板重载 vector 是动态空间， 随着元素的加入， 它的内…

1.6 STL

模板

        

模板底层实现：编译器会对函数模板进行两次编译， 在声明的地方对模板代码本身进行编译， 在调用的地方对参数替换后的代码进行编译。

模板传参分析

模板重载 

vector

是动态空间， 随着元素的加入， 它的内部机制会自行扩充空间以容纳新元素 。vector 的数据结构其实就 是三个迭代器构成的， 一个指向目前使用的空间头， 一个指向目前使用空间尾， 一个指向目前可用的空  间尾 。当有新元素插入时， 如果目前容量够用则直接插入； 若不够则容量扩充至两倍， 依次类推 。扩充  的过程是重新申请一块连续空间， 将原有数据拷贝到新空间， 再释放原有空间， 扩充后原有的迭代器会

失效。

remove() 的实现原理：在遍历容器中的元素时， 一旦遇到目标元素， 就做上标记， 然后继续遍历， 直    到找到一个非目标元素， 即用此元素将最先做标记的位置覆盖掉， 同时将此非目标元素所在的位置也做  上标记， 等待找到新的非目标元素将其覆盖 。remove() 不会改变其容量大小， 而 erase() 可以改变其容 量大小， 通常将 remove() 返回的迭代器传入 erase() 中清除后续无用元素。

注意事项：

●    插入和删除 元素后， 如果由于内存重分配则会导致迭代器全部失效；没有重分配则插入和删除之后 的迭代器失效 。

●    清空 vector 数据时， 如果保存的数据项是指针类型， 需要逐项 delete， 否则会造成 内存泄漏

●    频繁调用 push_back 影响： 向vector 的尾部添加元素， 很有可能引起整个对象存储空间的重新分 配， 这个过程是耗时耗力的 。C++11之后， 新增 emplace_back 方法， 都是添加元素， 但是该方法 效率更高 。emplace_back 在内存优化方面和运行效率方面有改进， 内存优化方面主要体现在就地 构造（ 直接在容器内构造对象， 不用拷贝 一个再使用） +强制类型转换， 在运行效率方面， 由于省  去了拷贝构造， 因此有提高。

list

STL中的 list 是一个双向循环链表， 相比双向链表结构的好处是在构建 list 容器时， 只需借助一个指针 即可轻松表示 list 容器的首尾元素。

deque

支持从头尾两端进行元素的插入和删除操作， 没有容量的概念， 因为它是动态地以 分段连续空间 组合 而成， 随时可以增加一段新的空间并连接起来， 但是拥有复杂的迭代器结构 。deque 采用 一块所谓的  map 作为主控， 这里的 map 实际就是一块大小连续的空间， 其中每一个元素称为节点 node， 都指向 了另一段连续线性空间， 该空间是 deque 真正的存储空间。

deque 实现原理

1. 送代器是一个类， 其中迭代器中的 node 变量指向 map 的一个单元， 而 map 中的每个单元指向当 前迭代器对应的数据（ 缓冲区）， 如下图所示 。map 的实现为 vector。

2. 当某个数据缓冲区头部或尾部已满时， 将回到 map 中定位到相邻的数据缓冲区 。内部 分段连续 实 现。

3. 当插入元素时， 当前位置位于首部或尾部时， 直接插入； 否则比较当前元素距离首部近还是尾部近， 距离哪边近则将当前位置那段的元素整体移动， 再插入当前元素。

4. 堆 和 栈 的实现原理

​

priority_queue 

优先队列（ STL为大顶堆）， 每个节点大于其子节点， 采用 vector 实现

map 和 set

STL 原理解析： https://www.bilibili.com/video/BV1NB4y1W7Uf?

spm_id_from=333.999.list.card_archive.click&vd_source=de7529d9789e1cd154061dd03f6490

20

map 和 set 都是C++的关联容器， 其底层实现都是红黑树。

set 、multiset 使用红黑树的迭代器是 const 类型的。

map 、multimap 使用红黑树的迭代器不是 const 类型的。

（key 、val在内部是存储在一个元素中， 因此set 、map底层实现一样）

红黑树（ 平衡二叉搜索树）

​

红黑树定义：

●    每个节点不是红色就是黑色

●    根节点必须是黑色， 相邻节点颜色不一样

●    从根节点到叶子节点的黑色节点个数是一样的

实现：有个虚拟头结点， 左右指针分别指向红黑树最左侧和最右侧节点， 便于最大最小值查找 。每个节点都有左右指针 、父节点指针和K-V值（ 还有颜色值）为什么采用红黑树实现：

●    二叉树在某些情况下可能会退化为 O(N) 的时间复杂度；

●    AVL树左右子树高度差最大为1， 红黑树不遵循高度差条件， 为的是减少旋转的次数

 hashtable

STL 原理解析： https://www.bilibili.com/video/BV1NB4y1W7Uf?

spm_id_from=333.999.list.card_archive.click&vd_source=de7529d9789e1cd154061dd03f6490

20

hash 转换：

1. 整数值直接作为 hash 值

2. 字符串各字符处理（ 只要够乱就可） 作为 hash 值

哈希表扩充： 当元素个数大于 buckets 大小时， 将会进行哈希表扩充（ 约2倍数扩充）， 并重新分配所 有元素。

碰撞处理： 同一位置用链表存储

实现： unordered_set 、unordered_map。

STL 底层实现

●    只有一个链表的头结点

●    每个桶指向上一个有效桶的最后一个节点（ 即上一个节点）

1.7 算法

memcpy 实现

        

void mymemcpy(void* dst, const void* src, size_t num) {assert((dst != nullptr) && (src != nullptr));const char* psrc = (const char*)src; //因为void*是⽆法完成 '++' 或 '--'
的char* pdst = (char*)dst;if (pdst > psrc && pdst < psrc + num) {for (size_t i = num - 1; i >= 0 && i < num; --i) {pdst[i] = psrc[i];}} else {for (size_t i = 0; i < num; ++i) {pdst[i] = psrc[i];}}
}

 读写锁

        

class ReadWriteLock {
private:
std::mutex write;
std::shared_mutex read; // C++14
int readCnt;
public:
ReadWriteLock(): readCnt(0) {}
void readLock() {
read.lock();
if (++ readCnt == 1) {
write.lock();
}
read.unlock();
}
void unreadLock() {
read.lock();
if (-- readCnt == 0) {
write.unlock();
}
read.unlock();
}
void writeLock() {
write.lock();
}
void unwriteLock() {
write.unlock();
}
};

死锁复现代码

        

#include <iostream>
#include <thread>
#include <mutex>
#include <unistd.h>
using namespace std;
int data = 1;
mutex mt1,mt2;
void a2() {
mt2.lock();
sleep(1);
data = data * data;
mt1.lock(); //此时a1已经对mt1上锁，所以要等待
cout<<data<<endl;
mt1.unlock();
mt2.unlock();
}
void a1() {
mt1.lock();
sleep(1);
data = data+1;
mt2.lock(); //此时a2已经对mt2上锁，所以要等待
cout<<data<<endl;
mt2.unlock();
mt1.unlock();
}
int main() {
thread t2(a2);
thread t1(a1);
t1.join();
t2.join();
cout<<"main here"<<endl; //要t1线程、t2线程都执⾏完毕后才会执⾏
return 0;
}
⼆叉树序列号与反序列化
         
// 序列化
void serializeSub(TreeNode* node, string &res) {if (!node) {res += "NULL,";}else {res += to_string(node->val) + ",";serializeSub(node->left, res);serializeSub(node->right, res);}
}
string serialize(TreeNode* root) {string res = "";serializeSub(root, res);return res;
}
// 反序列化
TreeNode* deserializeSub(queue<string> &q) {string cur = q.front();q.pop();if (cur == "NULL") {return nullptr;}else {TreeNode *node = new TreeNode(stoi(cur));node->left = deserializeSub(q);node->right = deserializeSub(q);return node;}
}
TreeNode* deserialize(string data) {queue<string> q;string cur = "";for (char c: data) {if (c != ',') {cur += c;}else {q.push(cur);cur.clear();}}
return deserializeSub(q);
}
⽣产者消费者模式
         
#include <iostream>
#include <thread>
#include <vector>
#include <queue>
#include <mutex>
#include <condition_variable>
using namespace std;
#define PRODUCT_SIZE 2
#define CUSTUM_SIZE 2
#define POOL_SIZE 3
mutex m;
condition_variable cv;
queue<int> que;
int num = 0;
void producter() {
while (true) {
std::unique_lock<std::mutex> lck(m);
while (que.size() >= POOL_SIZE) {
cv.wait(lck);
}
int data = num ++;
que.push(data);
cout << this_thread::get_id() << "⽣产了" << data << endl;
cv.notify_all();
}
}
void customer() {
while (true) {
std::unique_lock<std::mutex> lck(m);
while (que.empty()) {
cv.wait(lck);
}
cout << this_thread::get_id() << "消费了" << que.front() << endl;
que.pop();
cv.notify_all();
}
}
int main() {
vector<thread> pools;
for (int i = 0; i < PRODUCT_SIZE; ++ i) {
pools.push_back(thread(producter));
}
for (int i = 0; i < CUSTUM_SIZE; ++ i) {
pools.push_back(thread(customer));
}
for (int i = 0; i < PRODUCT_SIZE + CUSTUM_SIZE; ++ i) {
pools[i].join();
}
return 0;
}
⼆叉树-前中后迭代算法模板
         
vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<pair<TreeNode*, bool>> st;st.push({root, false}); // root 节点未被访问while (!st.empty()) {auto tmp = st.top();st.pop();if (!tmp.first) continue;if (!tmp.second) {TreeNode* node = tmp.first;// 对于其他顺序遍历，仅改变下⾯三⾏代码即可（遍历逆序）st.push({node->right, false});st.push({node, true});st.push({node->left, false});}else {res.emplace_back(tmp.first->val);}}return res;
}
⼿写智能指针
         
#include <iostream>
#include <cstdlib> // 智能指针头⽂件
#include <utility> // 智能指针头⽂件
#include <memory> // 智能指针头⽂件
template<typename T>
class SmartPtr {
private:
size_t* _count;
T* _ptr;
public:
// 构造函数
SmartPtr(T* ptr=nullptr): _ptr(ptr) {
if (ptr) {
_count = new size_t(1);
}
else {
_count = new size_t(0);
}
}// 析构函数
~SmartPtr() {
if ((*_count) > 0) {
-- (*_count);
}
if ((*_count) == 0) {
delete _ptr;
delete _count;
_ptr = nullptr;
_count = nullptr;
}
}// 拷⻉构造函数
SmartPtr(const SmartPtr& ptr) {
if (this == &ptr) {
return ;
}
_ptr = ptr._ptr;
_count = ptr._count;
(*_count) ++;
}// 拷⻉赋值运算符
SmartPtr& operator=(const SmartPtr& ptr) {
if (_ptr == ptr._ptr) {
return *this;
}
_ptr = ptr._ptr;
_count = ptr._count;
(*_count) ++;
return *this;
}T& operator*() const { return *_ptr; }
T* operator->() const { return _ptr; }
operator bool() const { return _ptr; }
size_t use_count() const { return *_count; }
};
int main() {
std::shared_ptr<int> p1(new int(3));
std::cout << p1.use_count() << std::endl; // 1
std::shared_ptr<int> p2(p1);
std::cout << p1.use_count() << std::endl; // 2
std::cout << p2.use_count() << std::endl; // 2
std::shared_ptr<int> p3;
std::cout << p3.use_count() << std::endl; // 0
p3 = p2;
std::cout << p2.use_count() << std::endl; // 3
std::cout << p3.use_count() << std::endl; // 3
std::shared_ptr<int> p4 = p3;
std::cout << p3.use_count() << std::endl; // 4
std::cout << p4.use_count() << std::endl; // 4
std::cout << std::endl << std::endl;
///
SmartPtr<int> sp1(new int(3));
std::cout << sp1.use_count() << std::endl; // 1
SmartPtr<int> sp2(sp1);
std::cout << sp1.use_count() << std::endl; // 2
std::cout << sp2.use_count() << std::endl; // 2
SmartPtr<int> sp3;
std::cout << sp3.use_count() << std::endl; // 0
sp3 = sp2;
std::cout << sp2.use_count() << std::endl; // 3
std::cout << sp3.use_count() << std::endl; // 3
SmartPtr<int> sp4 = sp3;
std::cout << sp3.use_count() << std::endl; // 4
std::cout << sp4.use_count() << std::endl; // 4
return 0;
}
⼗⼤排序算法（升序实现）
稳定排序：冒泡排序、插⼊排序、归并排序

冒泡排序：N个数需要进⾏N-1次冒泡，每次冒泡确定⼀个最⼤值位置。元素交换次数为原数组逆序度。

        

void bubbleSort(std::vector<int>& nums, int n) {
for (int i = 1; i < n; ++ i) { // 冒泡次数
bool is_swap = false;
for (int j = 1; j < n - i + 1; ++ j) {
if (nums[j] < nums[j - 1]) {
std::swap(nums[j], nums[j - 1]);
is_swap = true;
}
}
if (!is_swap) break;
}
}

 

插⼊排序：分为已排序和未排序，初始化已排序区间只有数组第⼀个元素。遍历未排序的每⼀个元素， 倒序⽐较与已排序区间的⼤⼩关系，确定当前未排序元素的位置。元素交换次数为原数组逆序度。
         
void insertSort(std::vector<int>& nums, int n) {
for (int i = 1; i < n; ++ i) {
for (int j = i; j > 0 && nums[j] < nums[j - 1]; -- j) {
std::swap(nums[j], nums[j - 1]);
}
}
}
选择排序：从头开始遍历数组，然后将该元素与其后⾯的区间进⾏⽐较，选择最⼩的元素并交换 
void selectSort(std::vector<int>& nums, int n) {
for (int i = 0; i < n - 1; ++ i) {
int k = i;
for (int j = i + 1; j < n; ++ j) {
if (nums[j] < nums[k]) {
k = j;
}
}
std::swap(nums[k], nums[i]);
}
}
快速排序：先找到⼀个枢纽，然后在当前数组中把⽐这个枢纽⼩的元素放左边，⼤的元素放右边，两部分数据依次递归排序下去直到有序。 
void quickSort(std::vector<int>& nums, int l, int r) {
if (l >= r) return;
int left = l, right = r, key = nums[l];
while (left < right) {
while (left < right && nums[right] >= key) -- right;
while (left < right && nums[left] <= key) ++ left;
if (left < right) {
std::swap(nums[left], nums[right]);
}
}
std::swap(nums[left], nums[l]);
quickSort(nums, l, left - 1);
quickSort(nums, left + 1, r);
}
归并排序：⾸先将数组等分递归排序，然后通过⼀个临时数组，⽐较两个数组的⼤⼩从⽽合并两个数组。
         
void mergeSort(std::vector<int>& nums, int l, int r) {
if (l < r) {
int mid = l + (r - l ) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);vector<int> tmp(r - l + 1);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r) {if (nums[i] < nums[j]) {tmp[k ++] = nums[i ++];}else {tmp[k ++] = nums[j ++];}}while (i <= mid) { tmp[k ++] = nums[i ++]; }while (j <= r) { tmp[k ++] = nums[j ++]; }for (int p = 0; p < k; ++ p) {nums[l + p] = tmp[p];}
}
}
堆排序：从最后⼀个⽗节点逆序构建最⼤堆（根节点/0下标值为最⼤），然后循环N-1次，不断将0下标与最后下标数交换，并调整堆（其中堆越来越⼩）
         
void heapify(vector<int>& nums, int f, int n) {
int left = f * 2 + 1;int right = left + 1;
while (left < n) {
int index = f;
if (nums[index] < nums[left]) index = left;
if (right < n && nums[index] < nums[right]) index = right;
if (index == f) {
break;
}
else {
swap(nums[f], nums[index]);
f = index;
left = f * 2 + 1;right = left + 1;
}
}
}
void heapSort(std::vector<int>& nums, int n) {
if (n < 2) return ;
// 从最后⼀个⽗节点调整为最⼤堆
for (int i = n / 2 - 1; i >= 0; -- i) {
heapify(nums, i, n);
}
// 最⼤值放最后，将剩下调整为堆
for (int i = n - 1; i > 0; -- i) {
std::swap(nums[0], nums[i]);
heapify(nums, 0, i);
}
}
桶排序：将数据分到有限数量的桶⾥，然后每个桶分别排序（可能使⽤其他排序算法），最后每个桶内数据合并
计数排序：获取数组最⼤manV和最⼩值mixV，然后⽣成manV-mixV+1⼤⼩的数组，分别计数对应值的次数，然后再恢复数值输出结果
基数排序：针对正整数排序，对每⼀个数补⻬最⻓位数，然后从低位开始排序，排序的过程类似于多次桶排序
希尔排序：从 len/2 步⻓开始排序，每次步⻓取半，直到最后成为插⼊排序
http://www.dinnco.com/news/64641.html

相关文章：

  • 佛山建设网站公司互联网营销培训课程
  • 企业建设银行网站登录不了百度收录关键词
  • 淘宝网站都是怎么做的吗成都seo的方法
  • 南京网站开发南京乐识权威新媒体运营主要做什么
  • 个体工商户可以申请网站建设吗站长工具排行榜
  • 营销网站建设大概费用网站的推广
  • 无锡网站制作百度知道网址
  • cdr做网站分辨率搜索引擎优化代理
  • 公众号设置下载wordpress网站优化 seo和sem
  • 张家港做外贸网站广告公司网站
  • 安徽政府网站建设安卓优化大师历史版本
  • 本人已履行网站备案信息大金seo
  • 南京网站设计平台搜索引擎seo如何赚钱
  • 福建省建设局实名制网站网络营销推广的方式
  • 网站部署到终端机怎么做推广软件app
  • 怎么做网站里的悬浮窗口可以搜索国外网站的搜索引擎
  • 旅游网的网站建设优质的seo网站排名优化软件
  • 杭州网站建设外包成都seo公司
  • 南宁建站官网南昌seo招聘信息
  • linux系统上的wordpressseo优化方案总结
  • 成都市建网站公司seo优化推广技巧
  • 商丘做网站哪家好seo服务如何收费
  • 上海简站商贸有限公司软文模板300字
  • 斗鱼类的直播网站开发营销宣传方式有哪些
  • 福安做网站最好seo网站关键词优化工具
  • 南宁软件优化网站建设营销策略有哪些方面
  • 做网站怎么排版护肤品营销策划方案
  • 免费开源网站系统有哪些线上拓客渠道有哪些
  • 自建个人网站平台长春seo结算
  • 怎么建设门户网站网站友情链接的好处