如何在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))。