如何在C++中存储有序集中的重复元素

如何在C++中存储有序集中的重复元素

有序集包含按照元素值排序的唯一元素,就像set一样。当处理带有重复元素的有序集时,在int的地方使用pair数据类型,其中第一个值存储元素,第二个值将存储对应的索引。这样,有序集中的每个对将是唯一的,可以轻松地存储数组的重复元素。

操作:

1.order_of_key(): 接受一个元素作为参数,并返回小于键的元素数量。在实现它时,我们需要将一对作为参数传递,其中第一个值需要是我们要为其获得结果的数字,第二个值将包含一个负值,例如,-1,因为有序集中插入的对将具有大于等于0的值,因为它表示数组的索引。

2.find_by_order(): 它接受一个索引作为参数,并返回排序顺序中的第i个元素(对)的迭代器。

例子:

假设有一个带有重复元素的有序集对mySet = { 4, 7, 2, 4, 5, 8, 4, 1, 3, 5 }。

这里:

  • 有序集对有重复元素。
  • 将所有元素插入到ordered_set_pair之后,
  • mySet.order_of_key({5,-1}): 它将给出小于5的元素数,即6。
  • mySet.find_by_order(8): 它将返回排序集中的第8个元素(对)的迭代器,即7。

下面是实现上述方法的C++程序:

// C++ program to store duplicate 
// elements in ordered set
#include <bits/stdc++.h>
using namespace std;
  
// Header files to implement ordered set
// Common file
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
  
// namespace necessary for GNU based 
// policy based data structures
using namespace __gnu_pbds;
  
  
// Declaring ordered_set for pair<int,int>
typedef tree<pair<int,int>, null_type, 
        less<pair<int,int>>, rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set_pair;
  
// Driver code
int main()
{
      int arr[10] = {4, 7, 2, 4, 5, 
                   8, 4, 1, 3, 5};
      ordered_set_pair mySet;
    
      // Inserting elements to 
    // ordered_set_pair
      for(int i = 0; i < 10; i++)
    {
          mySet.insert({arr[i], i});
    }
  
    // count of elements less than 5
    cout << "Count of elements less than 5: " << 
             mySet.order_of_key({5, -1}) << endl;
  
    // Print 8th element in the ordered set
    // iterator to a pair
      auto itr = mySet.find_by_order(8); 
      cout << "The 8th element in the ordered set is: " << 
             (*itr).first << endl;
    return 0;
}  

输出

Count of elements less than 5: 6
The 8th element in the ordered set is: 7

对于范围查询,例如位于L和R之间(包括L和R)的元素数量,可以使用以下方式进行查找:

mySet.order_of_key({R+1,-1}) – myset.order_of_key({L,-1})

find_by_order()和order_of_key()的时间复杂度均为O(log(n))。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程