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

【数据结构】红黑树封装map和set（下）

2023-10-11 100
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】红黑树封装map和set（下）

3. 迭代器


map和set的迭代器都是通过调用RBTree的迭代器来实现的，所以我们首先就要实现RBTree的迭代器


3.1 RBTree的迭代器

对于RBTree的迭代器，可以类比成list的迭代器的实现方式，由于原生指针不能很好的支持迭代器行为，所以需要实现一个迭代器类__RBTreeIteraotr。

和list的迭代器一样，这里为了支持const版本的迭代器，所以类模板有三个，如果对此有问题的话，可以去移步到【C++】list的模拟实现看详细的讲解。

所以迭代器类的框架如下

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __RBTreeIterator<T, Ref, Ptr> Self;
    typedef __RBTreeIterator<T, T&, T*> iterator;
    __RBTreeIterator(Node* node)
        :_node(node)
    {}
    Ref operator*();
    Ptr operator->();
    Self& operator++();
    Self& operator--();
    Self operator++(int);
    Self operator--(int);
    bool operator==(const Self& s) const;
    bool operator!=(const Self& s) const;
    Node* _node;
};


这里实现的重点就是++和–的运算符重载

1. 迭代器++的逻辑：

1113d276d1fc446fbb7944db401b6270.png

我们对照上面这个例子来说，如果要让迭代器按照中序的方式遍历这棵树的话，就是要走左子树-根-右子树的顺序，那么，对于任意一个节点，就把它当作一个子树的根节点来看，如果他的右子树不为空，就去访问它右子树的左子树，即右子树的最小节点，如果他的右子树为空，就表示此子树已经访问完毕，要找到下一个根节点，所以就要向上迭代，直到父节点是当前节点的右为止，然后访问父节点的父节点即可。代码如下:

Self& operator--()
{
    if(_node->_left)
    {
        Node* max = _node->_left;
        while(max->_right)
        {
            max = max->_right;
        }
        _node = max;
    }
    else
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while(parent && cur == parent->_right)
        {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    return *this;
}

2. 迭代器- -的逻辑：

迭代器–和++的处理方式是类似的，只是把逻辑对称过来即可，所以代码如下

Self& operator--()
{
    if(_node->_left)
    {
        Node* max = _node->_left;
        while(max->_right)
        {
            max = max->_right;
        }
        _node = max;
    }
    else
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while(parent && cur == parent->_right)
        {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    return *this;
}


所以迭代器类的实现就显而易见了：

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
    typedef RBTreeNode<T> Node;//重定义Node节点
    typedef __RBTreeIterator<T, Ref, Ptr> Self;//
    __RBTreeIterator(Node* node)//构造函数
        :_node(node)
    {}
    Ref operator*()
    {
        return _node->_data;//*的运算符重载，返回的是_data的值
    }
    Ptr operator->()//->的运算符重载，返回operator*的返回值的地址即可
    {
        return &_node->_data;
    }
    Self& operator++()
    {
        if(_node->_right)
        {
            Node* min = _node->_right;
            while(min->_left)
            {
                min = min->_left;
            }
            _node = min;
        }
        else
        {
            Node* cur = _node;
            Node* parent = _node->_parent;
            while(parent && cur == parent->_right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
    Self& operator--()
    {
        if(_node->_left)
        {
            Node* max = _node->_left;
            while(max->_right)
            {
                max = max->_right;
            }
            _node = max;
        }
        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++(int)//后置++和operator++()类似
    {
        Node* tmp = _node;
        if(_node->_right)
        {
            Node* min = _node->_right;
            while(min->_left)
            {
                min = min->_left;
            }
            _node = min;
        }
        else
        {
            Node* cur = _node;
            Node* parent = _node->_parent;
            while(parent && cur == parent->_right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return tmp;
    }
    Self operator--(int)//后置--和operator--()类似
    {
        Node* tmp = _node;
        if(_node->_left)
        {
            Node* max = _node->_left;
            while(max->_right)
            {
                max = max->_right;
            }
            _node = max;
        }
        else
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while(parent && cur == parent->_right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return tmp;
    }
    bool operator==(const Self& s) const
    {
        return _node == s._node;
    }
    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }
    Node* _node;//成员变量
};


3. RBTree的迭代器封装

对于RBTree，其begin就是最左节点，end是最右节点的下一个位置，这里为了简化，就给成nullptr即可

所以，迭代器的封装如下：

typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
    Node* left = _root;
    while(left && left->_left)
    {
        left = left->_left;
    }
    return iterator(left);
}
iterator end()
{
    return iterator(nullptr);
}
const_iterator begin() const
{
    Node* left = _root;
    while(left && left->_left)
    {
        left = left->_left;
    }
    return const_iterator(left);
}
const_iterator end() const 
{
    return const_iterator(nullptr);
}


3.2 map和set的迭代器封装

1. map的迭代器封装

//这里对于没有实例化的类RBTree<K, pair<const K, V>, MapKeyOfT>中的iterator需要使用typename来告诉编译器这里的iterator是类型名，不是静态变量（静态变量的使用方式也是这样的）
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
    return _t.begin();
}
iterator end()
{
    return _t.end();
}
const_iterator begin() const
{
    return _t.begin();
}
const_iterator end() const
{
    return _t.end();
}


2.set的迭代器封装

和map一样直接调用RBTree的迭代器即可。但是由于set的key是不允许修改的，所以这里不管是iterator还是const_iterator都可以直接使用RBTree中的const_iterator来重命名。

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
    return _t.begin();
}
iterator end() const
{
    return _t.end();
}


4. 插入的改写和operatorp[]的重载


4.1 insert的改写

之前的insert的返回值类型是bool，用于表示是否插入成功，但是STL库中的insert的返回值是一个pair类型，其中第一个成员变量是一个迭代器类型，指向插入的值得位置，第二个成员变量是bool类型，表示插入的位置，所以需要在RBTree层上改写一下insert的返回值

//RBTree
pair<iterator, bool> Insert(const T& data)
{
    if(_root == nullptr)
    {
        _root = new Node(data);
        _root->_col = BLACK;
        return make_pair(iterator(_root), true);//构造一个pair返回
    }
    KeyOfT kot;
    Node* cur = _root;
    Node* parent = nullptr;
    while(cur)
    {
        if(kot(cur->_data) < kot(data))
        {
            parent = cur;
            cur = cur->_right;
        }
        else if(kot(cur->_data) > kot(data))
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return make_pair(iterator(cur), false);//构造一个pair返回
        }
    }
    cur = new Node(data);
    Node* newnode = cur;
    cur->_col = RED;
    cur->_parent = parent;
    if(kot(parent->_data) > kot(cur->_data))
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    while(parent && cur->_parent->_col == RED)
    {
        Node* grandfather = parent->_parent;
        if(parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;
            if(uncle && uncle->_col == RED)
            {
                grandfather->_col = RED;
                uncle->_col = parent->_col = BLACK;
                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if(parent->_left == cur)
                {
                    RotateR(grandfather);
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                }
                else
                {
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
        else
        {
            Node* uncle = grandfather->_left;
            if(uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if(parent->_right == cur)
                {
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                }
                else
                {
                    RotateR(parent);
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    cur->_col = BLACK;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);//构造一个pair返回
}


map层的改写：

//map
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
    return _t.Insert(kv);
}


set层的改写：

//set
pair<iterator, bool> insert(const K& key)
{
    pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);//底层红黑树的iterator是普通迭代器
    return pair<iterator, bool>(ret.first, ret.second);//用普通迭代器构造const迭代器
}


4.2 map::operator[]重载的实现

在上面map的insert改写的基础上，就可以很方便的实现operator[]的重载

V& operator[](const K& key)
{
    pair<iterator, bool> ret = insert(make_pair(key, V()));//调用insert
    return ret.first->second;//ret的first是key对应的节点的迭代器，通过ret.first的second可以拿到对应的值second
}


5. 完整代码


5.1 RBTree的代码

#pragma once
#include <iostream>
enum Color{ RED, BLACK };
//这里使用T来封装
template<class T>
struct RBTreeNode
{
    T _data;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Color _col;
    RBTreeNode(const T data)
        :_data(data)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_col(RED)
    {}
};
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __RBTreeIterator<T, Ref, Ptr> Self;
    typedef __RBTreeIterator<T, T&, T*> iterator;
    __RBTreeIterator(Node* node)
        :_node(node)
    {}
    __RBTreeIterator(const iterator& s)
        :_node(s._node)
    {}
    Ref operator*()
    {
        return _node->_data;
    }
    Ptr operator->()
    {
        return &_node->_data;
    }
    Self& operator++()
    {
        if(_node->_right)
        {
            Node* min = _node->_right;
            while(min->_left)
            {
                min = min->_left;
            }
            _node = min;
        }
        else
        {
            Node* cur = _node;
            Node* parent = _node->_parent;
            while(parent && cur == parent->_right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
    Self& operator--()
    {
        if(_node->_left)
        {
            Node* max = _node->_left;
            while(max->_right)
            {
                max = max->_right;
            }
            _node = max;
        }
        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++(int)
    {
        Node* tmp = _node;
        if(_node->_right)
        {
            Node* min = _node->_right;
            while(min->_left)
            {
                min = min->_left;
            }
            _node = min;
        }
        else
        {
            Node* cur = _node;
            Node* parent = _node->_parent;
            while(parent && cur == parent->_right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return tmp;
    }
    Self operator--(int)
    {
        Node* tmp = _node;
        if(_node->_left)
        {
            Node* max = _node->_left;
            while(max->_right)
            {
                max = max->_right;
            }
            _node = max;
        }
        else
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while(parent && cur == parent->_right)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return tmp;
    }
    bool operator==(const Self& s) const
    {
        return _node == s._node;
    }
    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }
    Node* _node;
};
template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef __RBTreeIterator<T, T&, T*> iterator;
    typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
        Node* left = _root;
        while(left && left->_left)
        {
            left = left->_left;
        }
        return iterator(left);
    }
    iterator end()
    {
        return iterator(nullptr);
    }
    const_iterator begin() const
    {
        Node* left = _root;
        while(left && left->_left)
        {
            left = left->_left;
        }
        return const_iterator(left);
    }
    const_iterator end() const 
    {
        return const_iterator(nullptr);
    }
    pair<iterator, bool> Insert(const T& data)
    {
        if(_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root), true);
        }
        KeyOfT kot;
        Node* cur = _root;
        Node* parent = nullptr;
        //找到插入位置
        while(cur)
        {
            if(kot(cur->_data) < kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kot(cur->_data) > kot(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return make_pair(iterator(cur), false);
            }
        }
        cur = new Node(data);
        Node* newnode = cur;
        cur->_col = RED;
        //连接上
        cur->_parent = parent;
        if(kot(parent->_data) > kot(cur->_data))
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        //判断颜色是否合法
        while(parent && cur->_parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            if(parent == grandfather->_left)//当parent是grandfather左节点
            {
                Node* uncle = grandfather->_right;
                //情况一：uncle存在且为红
                if(uncle && uncle->_col == RED)
                {
                    grandfather->_col = RED;
                    uncle->_col = parent->_col = BLACK;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                //出现下面的情况就说明树的结构出现问题，需要对结构进行调整（旋转）
                else//uncle不存，或者在且为黑
                {
                    //情况二：grandfather、parent、cur在一条直线上
                    if(parent->_left == cur)
                    {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    //情况二：grandfather、parent、cur在一条折线上
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else//当parent是grandfather右节点
            {
                Node* uncle = grandfather->_left;
                //情况一：uncle存在且为红
                if(uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//uncle不存在，或者存在且为黑
                {
                    //情况二：grandfather、parent、cur在一条直线上
                    if(parent->_right == cur)
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    //情况二：grandfather、parent、cur在一条折线上
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return make_pair(iterator(newnode), true);
    }
    void RotateL(Node* parent)//左单旋
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* ppNode = parent->_parent;
        //处理subRL的部分
        parent->_right = subRL;
        if(subRL)
            subRL->_parent = parent;
        //处理parent和subR之间的关系
        subR->_left = parent;
        parent->_parent = subR;
        //处理subR的parent
        if(ppNode)//parent不是根节点的时候，需要处理parent的父亲节点
        {
            subR->_parent = ppNode;
            if(ppNode->_left == parent)//parent是左节点
            {
                ppNode->_left = subR;
            }
            else//parent是右节点
            {
                ppNode->_right = subR;
            }
        }
        else//parent是根节点的时候
        {
            _root = subR;
            subR->_parent = nullptr;
        }
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        Node* ppNode = parent->_parent;
        if(subLR)
            subLR->_parent = parent;
        parent->_left = subLR;
        subL->_right = parent;
        parent->_parent = subL;
        if(ppNode)
        {
            subL->_parent = ppNode;
            if(ppNode->_left == parent)
                ppNode->_left = subL;
            else
                ppNode->_right = subL;
        }
        else
        {
            _root = subL;
            subL->_parent = nullptr;
        }
    }
private:
    Node* _root = nullptr;
};


5.2 map的代码

#pragma once
#include "RBTree.hpp"
namespace zht
{
    template<class K, class V>
    class map
    {
        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>::const_iterator const_iterator;
    public:
        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }
        const_iterator begin() const
        {
            return _t.begin();
        }
        const_iterator end() const
        {
            return _t.end();
        }
        pair<iterator, bool> insert(const pair<const 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;
    };
};


5.3 set的代码

#pragma once
#include "RBTree.hpp"
namespace zht
{
    template<class K>
    class set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
        typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
        typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
    public:
        iterator begin() const
        {
            return _t.begin();
        }
        iterator end() const
        {
            return _t.end();
        }
        pair<iterator, bool> insert(const K& key)
        {
            pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
            return pair<iterator, bool>(ret.first, ret.second);
        }
    private:
        RBTree<K, K, SetKeyOfT> _t;
    };
}


5.4 测试代码

#include <iostream>
#include "RBTree.h"
#include "map.h"
#include "set.h"
#include <string>
using namespace std;
void set_test1() {
  int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  thj::set<int> s;
  for (auto e : a)
    s.insert(e);
  thj::set<int>::iterator it = s.begin();
  while (it != s.end()) {
    //*it = 10;
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}
void map_test1() {
  int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  thj::map<int, int> m;
  for (auto e : a)
    m.insert(std::make_pair(e, e));
  thj::map<int, int>::iterator it = m.begin();
  while (it != m.end()) {
    //it->first++;
    it->second++;
    cout << it->first << ":" << it->second << " ";
    ++it;
  }
  cout << endl;
}
void map_test2() {
  string arr[] = { "苹果", "西瓜", "芒果", "西瓜", "苹果", "梨子", "西瓜","苹果", "香蕉", "西瓜", "香蕉" };
  thj::map<string, int> countMap;
  for (auto& str : arr)
    countMap[str]++;
  for (auto& kv : countMap)
    cout << kv.first << ":" << kv.second << " ";
  cout << endl;
}
void map_test3() {
  srand((size_t)time(0));
  thj::map<int, int> m;
  int N = 1000;
  for (int i = 0; i < N; i++) {
    m.insert(make_pair(rand(), rand()));
  }
  auto it = m.begin();
  while (it != m.end()) {
    cout << it->first << endl;
    ++it;
  }
}
int main() {
  //set_test1();
  //map_test1();
  map_test2();
  //map_test3();
  return 0;
}


本节完

文章标签：
C++
关键词：
map Set
数据结构红黑树
数据结构set
数据结构map set
数据结构map
小张在努力写代码
目录
相关文章
东方睿赢
|
2月前
|
存储 Java
告别混乱！用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中，随着项目复杂度增加，数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案，帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例，展示了Map在商品管理、用户管理和订单管理中的具体应用，有效提升了代码质量和维护性。
东方睿赢
97 2
刘大猫.
|
20天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
55 18
你对Collection中Set、List、Map理解？
软件求生
|
14天前
|
存储 缓存 安全
只会“有序无序”？面试官嫌弃的List、Set、Map回答！
小米，一位热衷于技术分享的程序员，通过与朋友小林的对话，详细解析了Java面试中常见的List、Set、Map三者之间的区别，不仅涵盖了它们的基本特性，还深入探讨了各自的实现原理及应用场景，帮助面试者更好地准备相关问题。
软件求生
51 20
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
30 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
22 5
大树营养快线
|
1月前
|
开发者
除了交集运算，Set 类型还可以用于哪些数据结构的操作？
【10月更文挑战第30天】`Set`类型在数据结构操作方面提供了丰富的功能和便利，能够帮助开发者更高效地处理各种数据集合相关的任务，提高代码的简洁性和性能。
大树营养快线
35 6
东方睿赢
|
2月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构，使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中，随着项目复杂度的增加，数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构，使代码更加清晰、高效。本文通过在线购物平台的案例，展示了Map在商品管理、用户管理和订单管理中的具体应用，帮助开发者告别混乱，提升代码质量。
东方睿赢
34 1
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
208 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
35 1
龙大吉
|
27天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
53 5