wordpress多城市子站优化生育政策

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

wordpress多城市子站,优化生育政策,爱站网反链查询,wordpress tag 别名提供了键值对的存储机制#xff0c;处理 具有唯一键的关联数据 1、特性 键值对存储#xff1a;std::map 通过键值对的形式 存储数据#xff0c;其中每个键 都是唯一的#xff0c;并且 与一个值相关联 自动排序#xff1a;std::map 内部 使用一种平衡二叉搜索树#xf…提供了键值对的存储机制处理 具有唯一键的关联数据 1、特性 键值对存储std::map 通过键值对的形式 存储数据其中每个键 都是唯一的并且 与一个值相关联 自动排序std::map 内部 使用一种平衡二叉搜索树通常是红黑树来存储元素这使得元素根据键自动排序 元素唯一性在 std::map 中键必须是唯一的。如果尝试 插入一个已存在的键插入操作将失败 直接访问可以使用键 直接访问 std::map 中的元素这提供了 高效的查找能力 灵活的元素操作std::map 提供了 丰富的元素操作包括 插入、删除、查找等 2、性能 插入操作插入操作的时间复杂度为 O(log n)其中 n 是 std::map 中元素的数量。这是因为需要在平衡二叉树中 找到合适的位置来插入新元素 查找操作查找操作的时间复杂度 也是 O(log n)由于 std::map 的有序性可以快速定位到任何键 删除操作删除操作的时间复杂度同样为 O(log n)需要找到要删除的元素 并在保持树平衡的同时移除它 遍历操作遍历 std::map 的时间复杂度为 O(n)因为 需要访问容器中的每个元素 3、标准库中基本用法 // 创建一个map键和值都是int类型std::mapint, int myMap;// 插入元素myMap.insert({1,100});myMap[2] 200; // 使用下标操作符直接插入或修改// 迭代遍历for (const auto pair : myMap) {std::cout pair.first pair.second std::endl;}// 查找元素auto search myMap.find(2); // 查找键为2的元素if (search ! myMap.end()) {std::cout Found element with key 2: search-second std::endl;} else {std::cout Element with key 2 not found. std::endl;}myMap.erase(2); // 删除键为2的元素4、实现 #include iostream #include sstream #include string #include iostream #include utility // For std::pairenum class Color { RED, BLACK };template typename Key, typename Value class RedBlackTree {class Node {public:Key key;Value value;Color color;Node *left;Node *right;Node *parent;// 构造函数Node(const Key k, const Value v, Color c, Node *p nullptr): key(k), value(v), color©, left(nullptr), right(nullptr), parent(p) {}Node(): color(Color::BLACK), left(nullptr), right(nullptr), parent(nullptr) {}};private:Node *root;size_t size;Node *Nil;// 查询某节点Node *lookUp(Key key) {Node *cmpNode root;while (cmpNode) {if (key cmpNode-key) {cmpNode cmpNode-left;} else if (key cmpNode-key) {cmpNode cmpNode-right;} else {return cmpNode;}}return cmpNode;}// 右旋函数void rightRotate(Node *node) {Node *l_son node-left; // 获取当前节点的左子节点// 当前节点的左子树变成左子节点的右子树node-left l_son-right;// 如果左子节点的右子树非空更新其父指针if (l_son-right) {l_son-right-parent node;}// 左子节点升为当前节点位置并处理父节点关系l_son-parent node-parent;// 如果当前节点是根节点更新根节点为左子节点if (!node-parent) {root l_son;// 如果当前节点是其父节点的左子节点更新父节点的左子节点为左子节点} else if (node node-parent-left) {node-parent-left l_son;// 如果当前节点是其父节点的右子节点更新父节点的右子节点为左子节点} else {node-parent-right l_son;}// 完成右旋转将当前节点成为左子节点的右子节点l_son-right node;// 更新当前节点的父节点为左子节点node-parent l_son;}// 左旋// 是右旋的对称情况, 逻辑和右旋是一样的void leftRotate(Node *node) {Node *r_son node-right;node-right r_son-left;if (r_son-left) {r_son-left-parent node;}r_son-parent node-parent;if (!node-parent) {root r_son;} else if (node node-parent-left) {node-parent-left r_son;} else {node-parent-right r_son;}r_son-left node;node-parent r_son;}// 插入修复函数void insertFixup(Node *target) {// 当目标节点的父节点存在且父节点的颜色是红色时需要修复while (target-parent target-parent-color Color::RED) {// 当目标节点的父节点是祖父节点的左子节点时if (target-parent target-parent-parent-left) {Node *uncle target-parent-parent-right; // 叔叔节点// 如果叔叔节点存在且为红色进行颜色调整if (uncle uncle-color Color::RED) {target-parent-color Color::BLACK; // 父节点设为黑色uncle-color Color::BLACK; // 叔叔节点设为黑色target-parent-parent-color Color::RED; // 祖父节点设为红色target target-parent-parent; // 将祖父节点设为下一个目标节点} else {// 如果目标节点是父节点的右子节点进行左旋转if (target target-parent-right) {target target-parent; // 更新目标节点为父节点leftRotate(target); // 对目标节点进行左旋}// 调整父节点和祖父节点的颜色并进行右旋转target-parent-color Color::BLACK;target-parent-parent-color Color::RED;rightRotate(target-parent-parent);}} else {// 当目标节点的父节点是祖父节点的右子节点时与上面对称Node *uncle target-parent-parent-left; // 叔叔节点if (uncle uncle-color Color::RED) {target-parent-color Color::BLACK;uncle-color Color::BLACK;target-parent-parent-color Color::RED;target target-parent-parent;} else {if (target target-parent-left) {target target-parent; // 更新目标节点为父节点rightRotate(target); // 对目标节点进行右旋}// 调整父节点和祖父节点的颜色并进行左旋转target-parent-color Color::BLACK;target-parent-parent-color Color::RED;leftRotate(target-parent-parent);}}}// 确保根节点始终为黑色root-color Color::BLACK;}// 插入节点函数void insertNode(const Key key, const Value value) {// 创建一个新节点节点的颜色初始化为红色Node *newNode new Node(key, value, Color::RED);Node *parent nullptr; // 新节点的父节点指针Node *cmpNode root; // 用于比较的节点初始为根节点// 遍历树找到新节点的正确位置while (cmpNode) {parent cmpNode; // 保留当前节点作为新节点的潜在父节点// 如果新节点的键小于当前比较节点的键则向左子树移动if (newNode-key cmpNode-key) {cmpNode cmpNode-left;// 如果新节点的键大于当前比较节点的键则向右子树移动} else if (newNode-key cmpNode-key) {cmpNode cmpNode-right;// 如果键相等则说明树中已有相同键的节点删除新节点并返回} else {delete newNode;return;}}// 树的大小增加size;// 将新节点的父节点设置为找到的父节点位置newNode-parent parent;// 如果父节点为空说明树是空的新节点成为根节点if (!parent) {root newNode;// 如果新节点的键小于父节点的键将新节点插入父节点的左子树} else if (newNode-key parent-key) {parent-left newNode;// 否则将新节点插入父节点的右子树} else {parent-right newNode;}// 插入新节点后调用insertFixup函数来修复可能破坏的红黑树性质insertFixup(newNode);}// 中序遍历void inorderTraversal(Node *node) const {if (node) {inorderTraversal(node-left);std::cout node-key ;std::cout node-value ;inorderTraversal(node-right);}}// 辅助函数用新节点替换旧节点void replaceNode(Node *targetNode, Node *newNode) {if (!targetNode-parent) {root newNode;} else if (targetNode targetNode-parent-left) {targetNode-parent-left newNode;} else {targetNode-parent-right newNode;}if (newNode) {newNode-parent targetNode-parent;}}// 寻找以某个节点为根节点的子树中的最小节点Node *findMinimumNode(Node *node) {while (node-left) {node node-left;}return node;}// removeFixup函数用于在删除节点后恢复红黑树的性质void removeFixup(Node *node) {// 如果节点为Nil并且没有父节点说明它是唯一的节点直接返回if (node Nil node-parent nullptr) {return;}// 当我们没有到达根节点时继续循环while (node ! root) {// 如果节点是其父节点的左子节点if (node node-parent-left) {// 兄弟节点是节点父亲的右子节点Node *sibling node-parent-right;// 情况1节点的兄弟节点是红色if (getColor(sibling) Color::RED) {// 重新着色兄弟节点和父节点并进行左旋setColor(sibling, Color::BLACK);setColor(node-parent, Color::RED);leftRotate(node-parent);// 旋转后更新兄弟节点sibling node-parent-right;}// 情况2兄弟节点的两个子节点都是黑色if (getColor(sibling-left) Color::BLACK getColor(sibling-right) Color::BLACK) {// 重新着色兄弟节点并向上移动setColor(sibling, Color::RED);node node-parent;// 如果父节点是红色将其改为黑色并结束if (node-color Color::RED) {node-color Color::BLACK;node root;}} else {// 情况3兄弟节点的右子节点是黑色左子节点是红色if (getColor(sibling-right) Color::BLACK) {// 重新着色兄弟节点和兄弟节点的左子节点并进行右旋setColor(sibling-left, Color::BLACK);setColor(sibling, Color::RED);rightRotate(sibling);// 旋转后更新兄弟节点sibling node-parent-right;}// 情况4兄弟节点的右子节点是红色setColor(sibling, getColor(node-parent));setColor(node-parent, Color::BLACK);setColor(sibling-right, Color::BLACK);leftRotate(node-parent);// 移动到根节点结束node root;}} else {// 当节点是其父节点的右子节点时对称的情况Node *sibling node-parent-left;if (getColor(sibling) Color::RED) {setColor(sibling, Color::BLACK);setColor(node-parent, Color::RED);rightRotate(node-parent);sibling node-parent-left;}if (getColor(sibling-right) Color::BLACK getColor(sibling-left) Color::BLACK) {setColor(sibling, Color::RED);node node-parent;if (node-color Color::RED) {node-color Color::BLACK;node root;}} else {if (getColor(sibling-left) Color::BLACK) {setColor(sibling-right, Color::BLACK);setColor(sibling, Color::RED);leftRotate(sibling);sibling node-parent-left;}setColor(sibling, getColor(node-parent));setColor(node-parent, Color::BLACK);setColor(sibling-left, Color::BLACK);rightRotate(node-parent);node root;}}}// 确保当前节点是黑色的以维持红黑树性质setColor(node, Color::BLACK);}// 获取颜色, 空指针为黑色Color getColor(Node *node) {if (node nullptr) {return Color::BLACK;}return node-color;}void setColor(Node *node, Color color) {if (node nullptr) {return;}node-color color;}// 取消Nil哨兵的连接void dieConnectNil() {if (Nil nullptr) {return;}if (Nil-parent ! nullptr) {if (Nil Nil-parent-left) {Nil-parent-left nullptr;} else {Nil-parent-right nullptr;}}}// 删除节点void deleteNode(Node *del) {Node *rep del; // rep替代节点初始指向要删除的节点Node *child nullptr; // 要删除节点的孩子节点Node *parentRP; // 替代节点的父节点Color origCol rep-color; // 保存要删除节点的原始颜色// 如果删除节点没有左孩子if (!del-left) {rep del-right; // 替代节点指向删除节点的右孩子parentRP del-parent; // 更新替代节点的父节点origCol getColor(rep); // 获取替代节点的颜色replaceNode(del, rep); // 用替代节点替换删除节点}// 如果删除节点没有右孩子else if (!del-right) {rep del-left; // 替代节点指向删除节点的左孩子parentRP del-parent; // 更新替代节点的父节点origCol getColor(rep); // 获取替代节点的颜色replaceNode(del, rep); // 用替代节点替换删除节点}// 如果删除节点有两个孩子else {rep findMinimumNode(del-right); // 找到删除节点右子树中的最小节点作为替代节点origCol rep-color; // 保存替代节点的原始颜色// 如果替代节点不是删除节点的直接右孩子if (rep ! del-right) {parentRP rep-parent; // 更新替代节点的父节点child rep-right; // 替代节点的右孩子变成要处理的孩子节点parentRP-left child; // 替代节点的父节点的左孩子指向替代节点的孩子因为替代节点是最小节点所以不可能有左孩子if (child ! nullptr) {child-parent parentRP; // 如果替代节点的孩子存在则更新其父节点}// 将替代节点放到删除节点的位置del-left-parent rep;del-right-parent rep;rep-left del-left;rep-right del-right;// 如果删除节点有父节点更新父节点的孩子指向if (del-parent ! nullptr) {if (del del-parent-left) {del-parent-left rep;rep-parent del-parent;} else {del-parent-right rep;rep-parent del-parent;}}// 如果删除节点没有父节点说明它是根节点else {root rep;root-parent nullptr;}}// 如果替代节点是删除节点的直接右孩子else {child rep-right; // 孩子节点指向替代节点的右孩子rep-left del-left; // 替代节点的左孩子指向删除节点的左孩子del-left-parent rep; // 更新左孩子的父节点// 更新删除节点父节点的孩子指向if (del-parent ! nullptr) {if (del del-parent-left) {del-parent-left rep;rep-parent del-parent;} else {del-parent-right rep;rep-parent del-parent;}}// 如果删除节点是根节点else {root rep;root-parent nullptr;}parentRP rep; // 更新替代节点的父节点}}// 如果替代节点存在更新其颜色为删除节点的颜色if (rep ! nullptr) {rep-color del-color;}// 如果替代节点不存在将删除节点的颜色赋给origCol变量else {origCol del-color;}// 如果原始颜色是黑色需要进行额外的修复操作因为黑色节点的删除可能会破坏红黑树的性质if (origCol Color::BLACK) {// 如果存在孩子节点进行修复操作if (child ! nullptr) {removeFixup(child);}// 如果不存在孩子节点将Nil节点代表空节点的父节点设置为替代节点的父节点else {Nil-parent parentRP;// 如果替代节点的父节点存在设置其对应的孩子指针为Nil节点if (parentRP ! nullptr) {if (parentRP-left nullptr) {parentRP-left Nil;} else {parentRP-right Nil;}}// 进行修复操作removeFixup(Nil);// 断开Nil节点与树的连接因为在红黑树中Nil节点通常是单独存在的dieConnectNil();}}// 删除节点delete del;}public:// 构造函数RedBlackTree() : root(nullptr), size(0), Nil(new Node()) {Nil-color Color::BLACK;}// 插入void insert(const Key key, const Value value) { insertNode(key, value); }// 删除void remove(const Key key) {Node *nodeToBeRemoved lookUp(key);if (nodeToBeRemoved ! nullptr) {deleteNode(nodeToBeRemoved);size–;}}Value *at(const Key key) {auto ans lookUp(key);if (ans ! nullptr) {return ans-value;}return nullptr;}int getSize() { return size; }bool empty() { return size 0; }// 中序遍历打印void print() {inorderTraversal(root);std::cout std::endl;}void clear() {deleteNode(root);size 0;}// 析构函数~RedBlackTree() {// 释放节点内存deleteTree(root);}private:// 递归释放节点内存void deleteTree(Node *node) {if (node) {deleteTree(node-left);deleteTree(node-right);delete node;}} };// 此处开始为 map 的实现 template typename Key, typename Value class Map { public:Map() : rbTree() {}// 操作都是针对键值keyvoid insert(const Key key, const Value value) {rbTree.insert(key, value);}void erase(const Key key) {rbTree.remove(key);}size_t size() {return rbTree.getSize();}bool empty() {return rbTree.empty();}bool contains(const Key key) {return rbTree.at(key) ! nullptr;}// at没找到抛出错误Value at(const Key key) {Value *foundVal rbTree.at(key);if (foundVal) {return *foundVal;}else {throw std::out_of_range(Key not found);}}// []没找到直接插入并返回新插入的值的引用具体值不确定Value operator {Value *foundVal rbTree.at(key);if (foundVal) {return *foundVal;}else {Value tmp;rbTree.insert(key, tmp);return tmp;}} private:RedBlackTreeKey, Value rbTree; };int main() {Mapint, int myMap;int N;std::cin N;getchar();while (N–) {std::string line;std::getline(std::cin, line);std::istringstream iss(line);std::string command;iss command;int key;int value;if (command insert) {iss key value; // 可以连着写myMap.insert(key, value);}else if (command erase) {iss key;myMap.erase(key);}else if (command empty) {bool b myMap.empty();if (b true) {std::cout true std::endl;}else {std::cout false std::endl;}}else if (command size) {std::cout myMap.size() std::endl;}else if (command at) {// 对于抛出标准错误的处理iss key;try {std::cout myMap.at(key) std::endl;} catch(const std::out_of_range e) {std::cout not exist std::endl;}}else if (command contains) {iss key;bool b myMap.contains(key);if (b true) {std::cout true std::endl;}else {std::cout false std::endl;}}}return 0; } 1、返回值设为 Value 是为了避免不必要的值拷贝同时确保返回的是引用而不是副本 原因 Value operator1避免值拷贝如果返回类型是 Value 而不是 Value那么在返回时 会产生一次值的拷贝而这可能会 导致性能上的开销尤其当 Value 类型是一个较大的对象时。通过返回引用函数可以直接 返回原来的对象避免了拷贝操作 2允许对返回的值 进行修改如果函数返回 Value那么调用者可以 对返回的对象进行修改而不会影响到 其它地方的代码。特别是 如果 希望通过下标操作符修改 rbTree 中的值比如 obj[key] newValue需要返回对值的引用 当 operator[] 返回引用时任何对返回值的修改都会立即反映在容器中 obj[key] newValue; 等同于 Value ref obj[key]; // 获取引用 ref newValue; // 通过引用修改实际存储的值如果 operator[] 只返回值的副本修改不会持久保存因为只是副本被修改原始的值保持不变 如果 newKey 在 rbTree 中不存在operator[] 会 先创建并插入一个默认构造的 Value然后通过 返回对该 Value 的引用将其修改为 newValue完整的修改 是两个步骤。这种行为 依赖于 引用返回使得在没有键时 自动插入新元素成为可能并且 可以立即修改这个新元素 3保持一致性既然这个函数是 一个类似于 字典或映射的 operator[]在标准容器如 std::map的 operator[] 也会返回一个引用。因此使用引用作为返回类型 符合这种操作符的常见行为并确保 该操作符合预期访问或修改键所对应的值 2、写 iss key value; 这样的代码时操作的顺序如下 第一步执行 iss key;从 iss 流中提取数据并存储到 key 中操作结束后返回 iss 本身的引用 第二步由于 iss key 返回 iss 的引用因此接着 可以对 iss 再执行 value这时会从流中 提取下一个数据并存储到 value 中 3、和 C 标准库中的 std::map 的区别 1功能完备性 上述代码 仅实现了基本的插入、查找和删除功能并未考虑 std::map 中的所有功能如迭代器、比较器、异常安全性等。 std::map 还提供了一系列其他功能例如 lower_bound、upper_bound、equal_range 等 lower_bound 返回的是 一个指向第一个 不小于 给定键的元素的迭代器 upper_bound 返回的是 一个指向第一个 大于 给定键的元素的迭代器 equal_range 返回一个 std::pair包含两个迭代器分别表示 lower_bound 和 upper_bound 的结果 equal_range(2) 返回了 std::multimap 中所有键为 2 的元素的范围遍历这个范围 就能访问所有与键 2 相关的值 #include iostream #include mapint main() {std::multimapint, std::string mmap {{1, one}, {2, two}, {2, deux}, {3, three}};// 查找 key 为 2 的所有元素auto range mmap.equal_range(2);for (auto it range.first; it ! range.second; it) {std::cout it-first : it-second std::endl;}return 0; } 输出 2: two 2: deux2、性能和优化 如 节点分配 和 管理的内存池、迭代器优化等。 3、异常安全性 4、模板元编程和元编程技巧 使用了复杂的 模板元编程 技巧以 支持通用性、泛型编程和性能优化 5、常见面试题 1、std::map和std::unordered_map有什么区别 内部实现std::map 内部 基于红黑树实现因此它的元素是 自动排序的。而 std::unordered_map 基于哈希表实现元素是无序的 性能对于 std::map查找、插入和删除操作的时间复杂度 通常是 O(log n)。对于 std::unordered_map这些操作的平均时间复杂度是 O(1)但最坏情况下是 O(n) 内存消耗由于哈希表的开销std::unordered_map 可能会比 std::map 消耗更多内存 元素排序std::map 中的元素 按照键自动排序而 std::unordered_map 中的元素没有特定的顺序 2、std::map 的迭代器失效的情况有哪些 删除当前迭代器指向的元素 会使该迭代器失效但其他迭代器 仍然有效 插入操作 不会使现有迭代器失效 std::map 的迭代器是 双向迭代器对树的结构修改如插入或删除不会影响其他迭代器除了 指向被删除元素的迭代器 std::map 的迭代器是 双向迭代器这意味着它允许 前向遍历使用 it 可以向前移动迭代器 后向遍历使用 –it 可以向后移动迭代器 双向迭代器 不像 随机访问迭代器例如 std::vector 的迭代器那样支持 it n 等操作但它能灵活地 在有序数据结构如 std::map中来回移动 当 插入或删除元素时树可能会 做出一定的自我平衡调整例如旋转、重染色等操作以保持树的平衡。但尽管 底层树结构可能发生变化除了 指向被删除元素的迭代器以外其他迭代器 不会失效 std::mapint, std::string myMap {{1, one}, {3, three}, {4, four}}; auto it myMap.find(3); // 找到key为3的迭代器 myMap.erase(1); // 删除key为1的元素// 删除key为1的元素后原来指向key为3的迭代器仍然有效 std::cout it-first : it-second std::endl; // 输出 3: threemyMap.erase(3); // 删除key为3的元素 // 现在指向key为3的迭代器失效访问它会导致未定义行为3、如果 std::map 的键类型是 自定义类型需要怎么做 如果键类型是 自定义类型则需要 定义比较函数 或 重载 运算符以便 std::map 能够对键进行排序。可以通过 在自定义类型中 重载 运算符 或 提供自定义比较函数 作为 std::map 的第三个模板参数来实现 struct MyKey {int key;bool operator(const MyKey other) const {return key other.key;} }; std::mapMyKey, int myMap;或者 struct MyCompare {bool operator()(const MyKey lhs, const MyKey rhs) const {return lhs.key rhs.key;} }; std::mapMyKey, int, MyCompare myMap;4、解释 std::map::emplace 和 std::map::insert 的区别 emplace 方法会在 map 中直接构造元素避免了 额外的复制或移动操作。它接受构造元素所需的参数并且尝试在容器中构造元素 insert 方法 用于将已经构造好的元素 插入到 map 中。如果提供了键值对insert 可能会导致 一次或两次额外的复制 或 移动构造首先是 创建临时键值对对象然后是 将其复制或移动之后 插入到容器中 emplace更高效因为它直接在容器内部构造元素减少了 不必要的复制或移动操作。然而选择使用 emplace 还是 insert 取决于具体情况有时 为了代码的清晰可读使用 insert 可能更合适 使用 emplace 时容器内部会根据提供的参数直接在容器中构造对象insert 方法通常需要一个已经构造好的对象将其复制或移动到容器中 myMap.insert(std::make_pair(1, one)); // 首先创建一个临时的 std::pairint, std::string 对象然后 insert 会将该对象复制后插入到 map 中。这种方式涉及到一次额外的构造和复制或移动 myMap.emplace(1, one);std::map 和 std::unordered_map 中的 insert 函数 不会替换已经存在的键值对。换句话说当 试图插入一个键已经存在的元素时insert 不会插入新的值或替换已有的值而是保持已有的元素不变和 emplace 一样 https://kamacoder.com/ 手写简单版本STL内容在此基础上整理补充