AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

C++ 第九节——map/set(用法+底层原理+模拟实现)

2022-12-10 840
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 们需要知道的是，Map和Set的底层都是红黑树。

有了前面红黑树的底子，我们这一节的任务就比较轻松了。


关于Map和Set是什么东西，我们来借助网络文献进行解释。


首先，我们需要知道的是，Map和Set的底层都是红黑树。


即是一种平衡的二叉搜索树，也就是二叉平衡搜索树。


而set就是我们前面说到的Key模型，而map就是模型。


我们接下来将一边对比，一边介绍。


set和map的介绍

先来看set:


通过查阅文档有关set的声明，我们可以发现：

image.png



这里的T就是我们所说的Key，就是key_type或者说是value_type，即比较大小，比较的就是这些东西。


而后的Compare，就是比较的方式。其是一个仿函数，就是告诉set，我的比较方式是怎样的。这里可参照链表的有关叙述，这里就不再赘述。


紧接着，就着下面的接口模型，我们可以简单地创建一个set然后遍历它。

image.png



这里的都是一些成员函数，没有什么好说的了。


image.png


像这些函数，我们早就已经用烂掉了。类比着前面的一些容器，我们在这里也就略过，具体我们可以看下面的用法实例。


我们再来看一下find函数吧：

image.png



它的意思已经很明确了也。

就是说，找到了那个位置，就返回那个位置的迭代器。否则，就返回set::end()。

void test_set()
{
  set<int> s;       //创建
  s.insert(3); 
  s.insert(4);
  s.insert(8);
  s.insert(10);
  s.insert(1);
  s.insert(26);
  s.insert(7);
  s.insert(2);
  s.insert(3);      //插入
  set<int>::iterator is = s.begin();  //定义迭代器
  while (is != s.end())
  {
  cout << *is << " ";             //循环打印
  is++;
  }
  cout << endl;
  for (auto e : s)                    //另外一种打印方式——用范围for打印
  {
  cout << e << " ";
  }
  //排序+去重
}
void test_set1()
{
  set<string> ss;
  ss.insert("hello");                 //不断插入字符串
  ss.insert("map");
  ss.insert("set");
  ss.insert("string");
  ss.insert("wrong");
  set<string>::iterator it = ss.find("wron");  //查找，找到了则返回相应位置的迭代器，找不到 
                                                 //就返回ss.end()
  if (it == ss.end())
  {
  cout << "没有找到" << endl;
  }
  else
  {
  cout << "找到了" << endl;
  }
}
int main()
{
  test_set();
    test_set1();
  return 0;
}

打印出来的结果如上图。



同样的道理，我们再来看看map


map和set其实已经非常像了，它就是多了一个参数。（就是我们上面说烂掉的K,V模型，在存储着key的值的时候，每一个Key的值后面还跟着一个Value）

image.png



如上图所示，其在后面跟着的实际还有着一个T。也就是我们所说的value。


它的用法与set略有一点不同的是，我们需要用pair来进行插入。而关于pair是什么，我们在上一节就已经提到过，在这里，我们再来说一遍：

image.png


就是说，pair本质上也是一个类，它存储着两个类型的值，它的用处和好处就是当返回一个pair的时候，就相当于返回了两个值。


所以pair就相当于了一个打包的功能。我将两个值打包在一块，然后一块返回。（不过它本质上还是一个类）


当然，我们也可以用make_pair来去实现


make_pair本质上是对pair类型的一个再封装。

image.png


可以看到，一个make_pair的返回值，实际上就是一个pair。


下面的代码蕴藏了很多东西，其中包括很多内容的不同写法。各位可以细细品味一下。

void test_map1()
{
  map<int, double> m;  //K V模型
  m.insert(pair<int, double>(1, 1.1));//调用pair的构造函数，构造一个匿名对象
  m.insert(pair<int, double>(2, 2.1));
  m.insert(pair<int, double>(5, 3.4));
  m.insert(make_pair(2, 2.2));       //调用函数模板，构造对象，好处是不需要声明pair的参数， 
                                       //让函数去自己推演，用起来更方便
//  key相同就会插入失败
  map<int, double>::iterator it = m.begin();
  while (it != m.end())
  {
  cout << (*it).first<<":"<<(*it).second << endl;
  cout << it->first << ":" << it -> second << endl;
  it++;
  }
  cout << endl;
}
void test_map2()
{
  typedef map<string, string> DICT;
  typedef pair<string, string> D_KV;
  DICT dict;
  dict.insert(D_KV("hello", "你好"));
  dict.insert(D_KV("fine", "我好"));
  dict.insert(D_KV("nice", "很好"));
  dict.insert(D_KV("no", "不好"));
  dict.insert(D_KV("OK", "好"));
  DICT::iterator it = dict.find("hello");
  if (it != dict.end())
  {
  cout << it->second << endl;
  string& str = it->second;
  str.insert(0, "{");
  str += "}";
  cout << str << endl;
  }
}
void test_map3()
{
  //也可以从文件当中去读！！文件操作！！！
  string arr[] = { "苹果","苹果" ,"苹果", "西瓜","梨子","西瓜","榴莲","香蕉","香蕉","苹果" };
  map<string, int> mp;
  /*for (const auto& str : arr)
  {
  map<string, int>::iterator it = mp.find(str);
  if (it != mp.end())
  {
    it->second++;
  }
  else
  {
    mp.insert(pair<string, int>(str, 1));
  }
  }*/
  //统计次数的方式1
  /*for (const auto& e : arr)
  {
  pair<map<string, int>::iterator, bool> ret = mp.insert(pair<string, int>(e, 1));
  if (ret.second == false)
  {
    ret.first->second++;
  }
  }*/
  //统计方式2
//  下面是统计方式3
  for (const auto& e : arr)
  {
  mp[e]++;   //[]的返回值为mapped_value，第一个返回值为一个iterator的迭代器，第二个为一个bool类型的值。
  }
  for (const auto& e : mp)
  {
  cout << e.first << ":" << e.second << endl;
  }
  map<string, string> dic;
  dic.insert(make_pair("insert", "插入"));
  dic["left"];        //插入
  dic["left"] = "左边";  //修改
  dic["right"] = "右边"; //插入+修改
  dic["left"] = "左边、剩余";
  //mapped_value& operator[](const key_value& K)
  //{ return (this->insert(make_pair(K,mapped_value())).first).second}
}
void test_map4()
{
  string arr[] = { "苹果","苹果" ,"苹果", "西瓜","梨子","西瓜","榴莲","香蕉","香蕉","苹果" };
  map<string, int> mp;
  for (const auto& e : arr)
  {
  mp[e]++;   //[]的返回值为mapped_value，第一个返回值为一个iterator的迭代器，第二个为一个bool类型的值。
  }
  //假设需要对水果次序排序
  vector<map<string, int>::iterator> vp;            //我们用迭代器的目的，就是为了减少拷贝，深拷贝很浪费时间
  map<string, int>::iterator it = mp.begin();
  while (it != mp.end())
  {
  vp.push_back(it);
  it++;
  }
  sort(vp.begin(), vp.end(), Comp());
  //也可以直接利用map排序        存在拷贝问题   拷贝了pair数据
  map<int, string,greater<int>> mmp;
  for (const auto& e : mp)
  {
  mmp.insert(make_pair(e.second, e.first));
  }
  set<map<string, int>::iterator, Comp> SortSet;  //也可以利用set去排
  while (it != mp.end())
  {
  SortSet.insert(it);
  it++;
  }
  typedef map<string, int>::iterator M_IT;
  priority_queue<M_IT, vector<M_IT>, Comp> pq;
  while (it != mp.end())
  {
  pq.push(it);
  it++;
  }
}
void test_map5()
{
  map<string, string> dict;
  dict.insert(make_pair("left", "左边"));
  dict.insert(make_pair("left", "还是左边"));
  multimap<string, string> mdict;
  mdict.insert(make_pair("left", "左边"));    //允许键值冗余；不存在[]
  mdict.insert(make_pair("left", "还是左边"));
}


关于map的实际应用价值，其中有一个就是用来字典查找。


就如上面的例子所示，通过Key的值来去查找，如果找到了的话，我们就可以将其pair->second打印出来。


有关map和set的用法的内容，就暂时到这里了。还是比较简单的


我们下面来看其模拟实现：


set和map的模拟实现：

我们用一个红黑树同时实现map和set两种容器的封装。


我们这次重点来关注其是怎么实现这样的封装以及有关迭代器的实现的知识。关于红黑树的一些知识，本节就已经不再是重点关注的对象了。


废话少说，我们直接上代码。还是那句话，一切尽在代码中。实际上，这里的迭代器的模拟和链表还是非常的像的。


BRTree.h（我们复用上一节的红黑树的代码）

#pragma once
#include<iostream>
using namespace std;
enum Colour
{
  RED,
  BLACK,
};
template<class T>              //这里的模板统一改成T,即要么是K，要么是pair<K,V>
struct RBTreeNode
{
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  T _data;
  Colour _col;              //给出个参考颜色（用于标识红或者黑）
  RBTreeNode(const T& x)  //红黑树结点的构造函数
  :_left(nullptr)
  ,_right(nullptr)
  ,_parent(nullptr)
  ,_data(x)
  ,_col(RED)
  {}
};
template<class T, class Ref, class Ptr>   //T T& T*
struct __TreeIterator
{
  typedef Ref reference;
  typedef Ptr pointer;
  typedef RBTreeNode<T> Node;
  typedef __TreeIterator<T, Ref, Ptr> Self;
  Node* _node;
  __TreeIterator(Node* node)
  :_node(node)
  {}
  Ref operator*()
  {
  return _node->_data;
  }
  Ptr operator->()
  {
  return &_node->_data;
  }
  bool operator != (const Self& s) const
  {
  return _node != s._node;
  }
  bool operator==(const Self& s) const
  {
  return !(_node != s._node);
  }
  Self operator++()                  //前置++
  {
  if (_node->_right)
  {
    Node* left = _node->_right;
    while (left->_left)
    {
    left = left->_left;
    }
    _node = left;
  }
  else
  {
    Node* cur = _node;
    Node* parent = cur->_parent;
    while (parent && cur == parent->_right)
    {
    cur = cur->_parent;
    parent = parent->_parent;
    }
    _node = parent;
  }
  return *this;
  }
  Self operator--()
  {
  if (_node->_left)//根结点的左子树不为空
  {
    Node* right = _node->_left;//那么就去找左子树的最右结点
    while (right->_right)
    {
    right = right->_right;
    }
    _node = right;
  }
  else
  {
    Node* cur = _node;
    Node* parent = cur->_parent;
    while (parent && cur == parent->_left)
    {
    cur = cur->_parent;
    parent = parent->_parent;
    }
    _node = parent;
  }
  return *this;
  }
};
//迭代器适配器
template <class Iterator>
struct ReverseIterator
{
  typedef typename Iterator::reference Ref;
  typedef typename Iterator::pointer Ptr;
  typedef ReverseIterator<Iterator> Self;
  //迭代器萃取?
  ReverseIterator(Iterator it)
  :_it(it)
  {}
  Ref operator*()
  {
  return *_it;
  }
  Ptr operator->()
  {
  return _it.operator->();//?
  }
  Self& operator--()
  {
  ++_it;
  return *this;
  }
  Self& operator++()
  {
  --_it;
  return *this;
  }
  bool operator !=(const Self& s) const
  {
  return !(_it == s._it);
  }
  Iterator _it;
};
template<class K, class T ,class KeyOfT>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef __TreeIterator<T, T&, T*> iterator;
  typedef __TreeIterator<T, const T&, const T*> const_iterator;
  typedef ReverseIterator<iterator> reverse_iterator;
  reverse_iterator rbegin()
  {
  Node* right = _root;
  while (right && right->_right)
  {
    right = right->_right;
  }
  return reverse_iterator(iterator(right));
  }
  reverse_iterator rend()
  {
  return  reverse_iterator(iterator(nullptr));
  }
  iterator begin()
  {
  Node* left = _root;
  while (left && left->_left)
  {
    left = left->_left;
  }
  return iterator(left);
  }
  iterator end()
  {
  return iterator(nullptr);
  }
  RBTree()
  :_root(nullptr)      //构造函数初始化
  {}
  //拷贝构造和operator自己实现
  void Destroy(Node* root)//销毁函数
  {
  if (root == nullptr)
    return;
  Destroy(root->_left);  //通过不断递归来去实现，类比二叉搜索树
  Destroy(root->_right);
  delete root;
  }
  ~RBTree()            //析构函数——去调用销毁函数
  {
  Destroy(_root);
  }
  Node* Find(const K& key)  //查找（类比搜索二叉树）
  {
  KeyOfT oft;
  Node* cur = _root;
  while (cur)
  {
    if (oft(cur->_data) > key)
    {
    cur = cur->_left;
    }
    else if (oft(cur->_data) < key)
    {
    cur = cur->_right;
    }
    else
    {
    return cur;
    }
  }
  return nullptr;
  }
  pair<iterator ,bool> insert(const T& data)//插入
  {
  KeyOfT oft;
  if (_root == nullptr)           
  {
    _root = new Node(data);
    _root->_col = BLACK;
    return make_pair(_root, true);
  }
  Node* parent = nullptr;
  Node* cur = _root;
  while (cur)
  {
    if (oft(cur->_data) < oft(data))//如果要实现mutimap 和 mutiset ，那就是(oft(cur->_data) <= oft(data))
    {
    parent = cur;
    cur = cur->_right;
    }
    else if(oft(cur->_data) > oft(data))
    {
    parent = cur;
    cur = cur->_left;
    }
    else
    {
    return make_pair(iterator(_root), false);
    }
  }
  Node* newnode = new Node(data);
  newnode->_col = RED;               //标记为红
  if (oft(parent->_data) < oft(data))
  {
    parent->_right = newnode;
    newnode->_parent = parent;
  }
  else
  {
    parent->_left = newnode;
    newnode->_parent = parent;
  }
  cur = newnode;                         //前面的和搜索二叉树的插入完全一样，就标记了一下颜色。这里不再过多赘述
  while (parent && parent->_col == RED)  //如果父亲存在，且颜色为红色就要处理
  {
    //关键看叔叔
    Node* grandfather = parent->_parent;//并且祖父一定存在
    if (parent == grandfather ->  _left)   //如果父亲是祖父的左孩子
    {
    Node* uncle = grandfather->_right;    //那么叔叔就是祖父的右孩子
    if (uncle && uncle->_col == RED)      //如果叔叔存在且为红（情况一）
    {
      parent->_col = uncle->_col = BLACK;//把父亲和叔叔变成黑
      grandfather->_col = RED;    //祖父变成红
      //继续往上处理
      cur = grandfather;         //将祖父的位置给孙子
      parent = cur->_parent;     //父亲变为祖父的父亲
    }
    else  //情况2+3：叔叔不存在或者叔叔存在且为黑
    {
      //情况2：单旋
      if (cur == parent->_left)   //如果孩子是父亲的左孩子
      {
      RotateR(grandfather);  //右单旋
      grandfather->_col = RED;  //再变色
      parent->_col = BLACK;
      }
      else//情况3：双旋
      {
      RotateL(parent);
      RotateR(grandfather);
      cur->_col = BLACK;         //最终变的还是祖父的颜色和父亲的颜色
      grandfather->_col = RED;    //祖父的颜色变成红，父亲的颜色变成黑
      }
      break;
    }
    }
    else  //parent == grandparent -> _right   情况是相同的
    {
    Node* uncle = grandfather->_left;
    if (uncle && uncle->_col == RED)//情况1
    {
      uncle->_col = BLACK;
      grandfather->_col = RED;
      cur = grandfather;
      parent = cur->_parent;
    }
    else//情况2+3
    {
      if (cur == parent->_right)
      {
      RotateL(grandfather);
      parent->_col = BLACK;
      grandfather->_col = RED;
      }
      else //cur为父亲的左
      {
      //双旋
      RotateR(parent);
      RotateL(grandfather);
      cur->_col = BLACK;
      grandfather->_col = RED;
      }
      //插入结束
      break;
    }
    }
  }
  _root->_col = BLACK;
  return make_pair(iterator(newnode), true);
  }
  //剩余的就不解释了，和搜索二叉树、AVLTree都是一样的道理
  //只不过这里的旋转就不需要再调节平衡因子了。
  void RotateLR(Node* parent)
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  RotateL(parent->_left);
  RotateR(parent);
  }
  void RotateRL(Node* parent)
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  RotateR(parent->_right);
  RotateL(parent);
  }
  void RotateL(Node* parent)    //左单旋
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  Node* parentparent = parent->_parent;
  parent->_right = subRL;
  if (subRL)
  {
    subRL->_parent = parent;
  }   //两个一组
  subR->_left = parent;
  parent->_parent = subR;//两个一组
  //连接主体，找到组织
  if (parent == _root)
  {
    _root = subR;
    subR->_parent = nullptr;
  }
  else
  {
    if (parentparent->_left == parent)
    {
    parentparent->_left = subR;
    }
    else
    {
    parentparent->_right = subR;
    }
    subR->_parent = parentparent;
  }
  }
  void RotateR(Node* parent) //右单旋
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  parent->_left = subLR;
  if (subLR)
  {
    subLR->_parent = parent;
  }
  subL->_right = parent;
  Node* parentparent = parent->_parent;
  parent->_parent = subL;
  if (parent == _root)
  {
    _root = subL;
    _root->_parent = nullptr;
  }
  else
  {
    if (parentparent->_left == parent)
    {
    parentparent->_left = subL;
    }
    else
    {
    parentparent->_right = subL;
    }
    subL->_parent = parentparent;
  }
  }
  bool _CheckBlance(Node* root, int blackNum, int count)
  {
  if (root == nullptr)
  {
    if (count != blackNum)
    {
    cout << "黑色节点数量不等" << endl;
    }
    return true;
  }
  if (root->_col == RED && root->_parent->_col == RED)
  {
    cout << "存在连续的红色结点" << endl;
    return false;
  }
  if (root->_col == BLACK)
  {
    count++;
  }
  return _CheckBlance(root->_left,blackNum ,count)
    && _CheckBlance(root->_right, blackNum, count);
  }
  bool CheckBlance()
  {
  if (_root == nullptr)
  {
    return true;
  }
  if (_root->_col == RED)
  {
    cout << "根结点是红色的"<<endl;
    return false;
  }
  //找最左路径做黑色结点的参考值
  int blackNum = 0;
  Node* left = _root;
  while (left)
  {
    if (left->_col == BLACK)
    {
    blackNum++;
    }
    left = left->_left;
  }
  int count = 0;
  return _CheckBlance(_root, blackNum, count);
  }
private:
  Node* _root;
};
map.h
#pragma once
#include"BRTree.h"
namespace jxwd
{
  template<class K, class V>
  class map
  {
  public:
  struct MapKeyOfT
  {
    const K& operator()(const pair<const K, V>& kv)
    {
    return kv.first;
    }
  };
  typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
  typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;
  iterator begin()
  {
    return _t.begin();
  }
  iterator end()
  {
    return _t.end();
  }
  reverse_iterator rbegin()
  {
    return _t.rbegin();
  }
  reverse_iterator rend()
  {
    return _t.rend();
  }
  pair<iterator, bool> insert(const pair<const K, V>& kv)
  {
    return  _t.insert(kv);
  }
  pair<iterator, bool> insert(const pair<K, V>& kv)
  {
    return _t.insert(kv);
  }
  V& operator[](const K& key)
  {
    pair<iterator, bool> ret = insert(make_pair(key, V()));
    return ret.first->second;
  }
  private:
  RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  };
}
set.h
#pragma once
#include "BRTree.h"
namespace jxwd
{
  template<class K>
  class set
  {
  struct SetKeyOfT
  {
    const K& operator()(const K& key)
    {
    return key;
    }
  };
  public:
  typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
  typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;
  reverse_iterator rbegin()
  {
    return _t.rbegin();
  }
  reverse_iterator rend()
  {
    return _t.rend();
  }
  bool insert(const K& k)
  {
    _t.insert(k);
    return true;
  }
  iterator end()
  {
    return _t.end();
  }
  iterator begin()
  {
    return _t.begin();
  }
  private:
  RBTree<K, K ,SetKeyOfT> _t;
  };
}
test.cpp
#include"set.h"
#include"map.h"
int main()
{
  jxwd::map<int, int> t;
  t.insert(make_pair(3, 3));
  t.insert(make_pair(2, 2));
  t.insert(make_pair(1, 1));
  t.insert(make_pair(0, 7));
  t.insert(make_pair(6, 2));
  t[2] = 7;
  jxwd::map<int, int>::reverse_iterator it = t.rbegin();
  while (it != t.rend())
  {
  cout << (*it).first << ":" << (*it).second << endl;
  cout << it->first<< ":" << it->second << endl;
  ++it;
  }
  jxwd::set<int> tt;
  tt.insert(3);
  tt.insert(1);
  tt.insert(2);
  tt.insert(4);
  jxwd::set<int>::reverse_iterator sit = tt.rbegin();
  while (sit != tt.rend())
  {
  cout << *sit << endl;
  ++sit;
  }
  cout << endl;;
  return 0;
}


最后的代码运行截图：



真的是懒得打字了😀，一切尽在代码中。


相信大家都能看懂😀。


文章标签：
C++
容器
存储
关键词：
C++用法
Map set用法
map Set
C++ set用法
C++ set
刘健祥
目录
相关文章
oioihoii
|
13天前
|
存储 安全 编译器
第二问：C++中const用法详解
`const` 是 C++ 中用于定义常量的关键字，主要作用是防止值被修改。它可以修饰变量、指针、函数参数、返回值、类成员等，确保数据的不可变性。`const` 的常见用法包括：
oioihoii
55 0
刘大猫.
|
25天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
57 18
你对Collection中Set、List、Map理解？
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
33 3
【C++】map、set基本用法
chian-ocean
|
1月前
|
存储 算法 C++
【C++】unordered_map（set）
C++中的`unordered`容器（如`std::unordered_set`、`std::unordered_map`）基于哈希表实现，提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中，每个桶可存储一个或多个元素，以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列，以及迭代器。哈希函数用于计算元素的哈希值，冲突通过开链法解决，负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1)，但在冲突较多时可能退化为O(n)。
chian-ocean
24 5
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】map的模拟实现
C++中的`map`是STL中的一种关联容器，存储键值对且键唯一。`map`基于红黑树实现，自动按键排序，支持动态调整、复杂数据类型、丰富的成员函数及双向迭代器。插入、查找等操作保证了对数时间复杂度，适用于需要快速查找和有序存储的场景。
chian-ocean
24 3
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】set模拟实现
C++中的`set`是STL提供的一种关联容器，用于存储唯一元素并自动按特定顺序（默认升序）排序。其内部通过红黑树实现，保证了高效的插入、删除和查找操作，时间复杂度均为O(log n)。`set`支持迭代器遍历，提供了良好的数据访问接口。
chian-ocean
40 3
oioihoii
|
13天前
|
C++
第十三问：C++中静态变量的用法有哪些？
本文介绍了 C++ 中静态变量和函数的用法及原理。静态变量包括函数内的静态局部变量和类中的静态成员变量，前者在函数调用间保持值，后者属于类而非对象。静态函数不能访问非静态成员，但可以通过类名直接调用。静态链接使变量或函数仅在定义文件内可见，避免命名冲突。
oioihoii
29 0
ephemerals__
|
1月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
53 2
ephemerals__
|
1月前
|
存储 编译器 C++
【c++】类和对象（下）（取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象）
本文介绍了C++中类和对象的高级特性，包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项，帮助读者深入了解C++面向对象编程的核心机制。
ephemerals__
109 5
ephemerals__
|
1月前
|
存储 编译器 C++
【c++】类和对象（中）（构造函数、析构函数、拷贝构造、赋值重载）
本文深入探讨了C++类的默认成员函数，包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化，析构函数用于对象销毁时的资源清理，拷贝构造函数用于对象的拷贝，赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项，并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
ephemerals__
103 4