【C++】map 和 set 在高并发环境下的性能优化秘籍，深入探讨如何利用多线程编程、锁机制优化以及数据预分配等高级技术手段，有效避免数据冲突，提高并发处理能力，实现性能的质的飞跃的专业解决

template < class T,                   // set::key_type/value_type
     class Compare = less<T>,         // set::key_compare/value_compare仿函数
     class Alloc = allocator<T>       // set::allocator_type
     > class set;

// empty (1) ⽆参默认构造 
explicit set (const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造 
template <class InputIterator>
 set (InputIterator first, InputIterator last,
 const key_compare& comp = key_compare(),
 const allocator_type& = allocator_type());

// copy (3) 拷⻉构造 
set (const set& x);

// initializer list (5) initializer 列表构造 
set (initializer_list<value_type> il,
 const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());

// 迭代器是⼀个双向迭代器 
iterator -> a bidirectional iterator to const value_type

// 正向迭代器 
iterator begin();
iterator end();
// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)

// 单个数据插⼊，如果已经存在则插⼊失败 
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找val，返回val所在的迭代器，没有找到返回end() 
iterator find (const value_type& val);
// 查找val，返回Val的个数 
size_type count (const value_type& val) const;

// 算法库的查找 O(N) 
 auto pos1 = find(s.begin(), s.end(), x); 
 // set⾃⾝实现的查找 O(logN) 
 auto pos2 = s.find(x); 

class Solution {
public:
    // 函数用于找到两个数组的交集，结果中的元素是唯一的
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 使用 set 来存储 nums1 和 nums2 中的唯一元素
        set<int> s1(nums1.begin(), nums1.end()); // 将 nums1 转换为 set s1，自动去重
        set<int> s2(nums2.begin(), nums2.end()); // 将 nums2 转换为 set s2，自动去重

        vector<int> tab; // 用于存储交集结果

        // 使用两个迭代器分别遍历 set s1 和 set s2
        auto add1 = s1.begin();
        auto add2 = s2.begin();

        // 当两个迭代器都没有到达各自 set 的末尾时继续循环
        while (add1 != s1.end() && add2 != s2.end()) {
            if (*add1 < *add2) {
                // 如果当前 s1 中的元素小于 s2 中的元素，移动 s1 的迭代器
                add1++;
            }
            else if (*add2 < *add1) {
                // 如果当前 s2 中的元素小于 s1 中的元素，移动 s2 的迭代器
                add2++;
            }
            else {
                // 如果两个元素相等，说明是交集的一部分，添加到结果 vector 中
                tab.push_back(*add1);
                // 移动两个迭代器以继续查找下一个可能的交集元素
                add1++;
                add2++;
            }
        }

        // 返回包含交集结果的 vector
        return tab;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //创建一个 set 用于存储已经访问过的节点
        set<ListNode*> s;
        //从第一个节点开始遍历
        ListNode* cur = head;
        //遍历链表直到当前节点为空
        while(cur)
        {
            //当前节点存在set存在，说明是带环链表
            if(s.count(cur))
            {
                //返回当前节点
                return cur;
            }
            else
            {
                //set没有这个数值，那就插入这个数值
                s.insert(cur);
            }
            cur = cur->next;
        }
        //链表无环，则返回 null
        return NULL;
    } 
};

template < class Key,                          // map::key_type
 class T,                                      // map::mapped_type
 class Compare = less<Key>,                    // map::key_compare-仿函数
 class Alloc = allocator<pair<const Key,T> >   // map::allocator_type
> class map;

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;

    //数值元素
	T1 first;
	T2 second;

	pair() : first(T1()), second(T2())
	{}

	pair(const T1& a, const T2& b) : first(a), second(b)
	{}

	template<class U, class V>
	pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
	{}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

// "left"已经存在，插⼊失败 
 dict.insert({ "left", "左边，剩余" });

// empty (1) ⽆参默认构造 
explicit map(const key_compare& comp = key_compare(),
	const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造 
template <class InputIterator>
map(InputIterator first, InputIterator last,
	const key_compare& comp = key_compare(),
	const allocator_type & = allocator_type());

// copy (3) 拷⻉构造 
map(const map& x);

// initializer list (5) initializer 列表构造 
map(initializer_list<value_type> il,
	const key_compare& comp = key_compare(),
	const allocator_type& alloc = allocator_type());

// 迭代器是⼀个双向迭代器 
iterator->a bidirectional iterator to const value_type

// 正向迭代器 
iterator begin();
iterator end();

// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
pair<iterator,bool> insert (const value_type& val);

// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert (initializer_list<value_type> il);

// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找k，返回k所在的迭代器，没有找到返回end() 
iterator find (const key_type& k);
// 查找k，返回k的个数 
size_type count (const key_type& k) const;

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的
mapped_type值 
iterator find (const key_type& k);

// ⽂档中对insert返回值的说明 
// The single element versions (1) return a pair, with its member pair::first 
set to an iterator pointing to either the newly inserted element or to the 
element with an equivalent key in the map. The pair::second element in the pair
 is set to true if a new element was inserted or false if an equivalent key 
already existed.

pair<iterator,bool> insert (const value_type& val);

mapped_type& operator[] (const key_type& k);

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 创建一个哈希表，用于存储原节点与复制节点之间的映射关系
        map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr; // 复制链表的头指针
        Node* copytail = nullptr; // 复制链表的尾指针

        Node* cur = head; // 指针指向当前遍历的原节点

        // 遍历原链表，复制每个节点并建立映射关系
        while(cur)
        {
            // 如果复制链表为空，初始化复制链表的头尾指针
            if(copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                // 将新节点添加到复制链表的尾部
                copytail->next = new Node(cur->val);
                copytail = copytail->next; // 更新尾指针
            }
        
            // 在哈希表中存储原节点与复制节点的映射
            nodeMap[cur] = copytail;
            cur = cur->next; // 移动到下一个原节点
        }

        // 再次遍历原链表，处理random指针
        cur = head; // 重置指针到原链表的头部
        Node* copy = copyhead; // 指针指向当前遍历的复制节点

        while(cur)
        {
            if(cur->random == nullptr)
            {
                // 如果原节点的random指针为空，复制节点的random指针也设置为空
                copy->random = nullptr;
            }
            else
            {
                // 通过哈希表找到对应的复制节点，并设置复制节点的random指针
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;       // 移动到下一个原节点
            copy = copy->next;     // 移动到下一个复制节点
        }
        return copyhead; // 返回复制链表的头指针
    }
};

class Solution {
public:
    // 定义一个仿函数，用于比较两个 pair<string, int> 的大小
    struct con {
        bool operator()(const pair<string, int>& v1, const pair<string, int>& v2) {
            // 如果第二个元素的频率不同，按照频率从大到小排序
            if (v1.second != v2.second) {
                return v1.second > v2.second;
            }
            // 如果频率相同，按照字典序从小到大排序
            return v1.first < v2.first;
        }
    };

    // 函数：返回 words 中出现频率前 k 高的单词
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 创建一个 map 来统计每个单词出现的频率
        map<string, int> frequencyMap;
        for (const auto& word : words) {
            frequencyMap[word]++; // 统计每个单词的出现次数
        }

        // 将 map 中的元素转换为 vector<pair<string, int>> 以便排序
        vector<pair<string, int>> v(frequencyMap.begin(), frequencyMap.end());

        // 使用 stable_sort 按照频率和字典序对 vector 进行排序
        stable_sort(v.begin(), v.end(), con());

        // 创建一个 vector 来存储结果
        vector<string> result;
        for (int i = 0; i < k; i++) {
            result.push_back(v[i].first); // 将前 k 个高频单词加入结果中
        }

        return result; // 返回结果
    }
};