Open In App

Map Policy Based Data Structure in g++

Last Updated : 04 Sep, 2021
Improve
Improve
Like Article
Like
Save
Share
Report

There are some data structures that are supported by g++ compiler and are not a part of the C++ standard library. One of these is: Policy-Based Data Structure, which is used for high-performance, flexibility, semantic safety, and conformance to the corresponding containers in std. 
This can also be used as a map, to store key and a value (pair) in a sorted order. 
So to use this Data Structure, the following lines must be added to the code:
 

CPP




#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
 
using namespace __gnu_pbds;
 






                        










Following is the code showing policy-based data structure as a map, it can add/remove pairs of elements, can find the number of pairs less than (x, y), kth smallest pair etc. in O(log N) time. The specialty of this map is that we have access to the indices that the pair of elements would have in a sorted 2D array. If the pair does not appear in the map, we get the position that the pair would have in the map.
 




CPP














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















// Program showing a Policy Based Data Structure as a map


#include <ext/pb_ds/assoc_container.hpp>


#include <ext/pb_ds/tree_policy.hpp>


#include <functional>


#include <iostream>


using namespace __gnu_pbds;


using namespace std;


 


// A new data structure is defined


// Please refer https : // goo.gl/WVDL6g


typedef tree<pair<int, int>, null_type, less<pair<int, int> >,


             rb_tree_tag, tree_order_statistics_node_update>


    ordered_map;


 


// Driver code


int main()


{


    ordered_map om;


 


    om.insert({ 23, 20 });


    om.insert({ 23, 10 });


    om.insert({ 23, 30 });


    om.insert({ 12, 35 });


    om.insert({ 12, 22 });


 


    // Another method to insert pair


    // om.insert(make_pair(23, 20));


 


    // Print the contents of the map


    cout << "Contents of map:\n";


    cout << "KEY\tELEMENT\n";


    for (auto itr = om.begin(); itr != om.end(); ++itr) {


        cout << itr->first << "\t" << itr->second << "\n";


    }


 


    // value at 3rd index in sorted array.


    cout << "The value at 3rd index is "


         << "{" << om.find_by_order(3)->first << ", "


         << om.find_by_order(3)->second << "}\n";


 


    // Index of pair {23, 30}


    cout << "The index of pair {23, 30} is "


         << om.order_of_key({ 23, 30 }) << endl;


 


    // Pair {23, 40} is not in the map but it will show the


    // index number if it was there in sorted array


    cout << "The index of pair {23, 40} is "


         << om.order_of_key({ 23, 40 }) << endl;


 


    return 0;


}



















                        







                        










Output: 


Contents of map:
KEY    ELEMENT
12    22
12    35
23    10
23    20
23    30
The value at 3rd index is {23, 20}
The index of pair {23, 30} is 4
The index of pair {23, 40} is 5


 




                                    


                                                                        

                                        

                                            

                                                

                                                    
N

        

            
        

        

                                                

                                                

                                                    NikhilRathor                                                

                                            

                                            

            
                                        

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                            
 
                                

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Which data structure is used by Map?
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Merge Sort Tree with point update using Policy Based Data Structure

                
A Merge Sort Tree (MST) is a data structure that allows for efficient querying of the number of elements less than or equal to a certain value in a range of an array. It is built using a divide-and-conquer approach similar to the merge sort algorithm, where the array is recursively divided into two halves and a tree is constructed to represent the

            

            
            

                
                7 min read
            

        
    
        
            

                
Inversion Count using Policy Based Data Structure

                
Pre-requisite: Policy based data structure Given an array arr[], the task is to find the number of inversions for each element of the array. Inversion Count: for an array indicates – how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If the array is sorted in the reverse order then the i

            

            
            

                
                7 min read
            

        
    
        
            

                
Static Data Structure vs Dynamic Data Structure

                
Data structure is a way of storing and organizing data efficiently such that the required operations on them can be performed be efficient with respect to time as well as memory. Simply, Data Structure are used to reduce complexity (mostly the time complexity) of the code. Data structures can be two types : 1. Static Data Structure 2. Dynamic Data

            

            
            

                
                4 min read
            

        
    
        
            

                
Which data structure is used by Map?

                
What is a Map? Before learning the data structure used by a map, let us have an overlook of map. Map is the part of the STL library that stores key value pairs in it and no two values have the same keys but the different keys can store similar values. The map stores keys in sorted order. These are some functions which map uses with their Time Compl

            

            
            

                
                2 min read
            

        
    
        
            

                
Remove duplicates from unsorted array using Map data structure

                
Given an unsorted array of integers, print the array after removing the duplicate elements from it. We need to print distinct array elements according to their first occurrence. Examples: Input : arr[] = { 1, 2, 5, 1, 7, 2, 4, 2} Output : 1 2 5 7 4 Explanation : {1, 2} appear more than one time. Approach : Take a hash map, which will store all the

            

            
            

                
                4 min read
            

        
    
        
            

                
Sort a 2D vector diagonally using Map Data Structure

                
Given a 2D vector mat[][] of integers. The task is to sort the elements of the vectors diagonally from top-left to bottom-right in increasing order.Examples: Input: mat[][] = {{9, 4, 2}, {7, 4, 6}, {2, 3, 3}} Output: 3 4 2 3 4 6 2 7 9 Explanation: There are 5 diagonals in this matrix: 1. {2} - No need to sort 2. {7, 3} - Sort - {3, 7} 3. {9, 4, 3}

            

            
            

                
                8 min read
            

        
    
        
            

                
Implementation on Map or Dictionary Data Structure in C

                
C programming language does not provide any direct implementation of Map or Dictionary Data structure. However, it doesn't mean we cannot implement one. In C, a simple way to implement a map is to use arrays and store the key-value pairs as elements of the array. How to implement Map in C? One approach is to use two arrays, one for the keys and one

            

            
            

                
                3 min read
            

        
    
        
            

                
Searching in a map using std::map functions in C++

                
Usually, main purpose of using map stl container is for efficient search operations and sorted order retrieval. As map stores key-value pair, all the search operations take "O(log(n))" time (n is size of map). Different types of search functions exists in C++ language, each having different functions. In the context of competitive programming, this

            

            
            

                
                7 min read
            

        
    
        
            

                
Decrypt Map Coordinates from given pair of strings based on given rules

                
Given a pair of lowercase strings string1[] and string2[] of size M and N, the task is to decrypt these strings according to the following rules. The last character of encrypted string denotes the direction latitude string(only two [n-North, s-South]) longitude string(other two [e-East, w-West]). Except for the last character the string denotes an

            

            
            

                
                8 min read
            

        
    
        
            

                
Array-Based Queues vs List-Based Queues

                
Queues:A queue is a linear data structure in which elements are inserted from one end called the rear end and deleted from another end called the front end. It follows FIFO (First In First Out) technique.Insertion in the queue is called enqueue and deletion in the queue is called dequeue.Queues can be implemented in two ways: Array-based queues and

            

            
            

                
                3 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox