fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. namespace AVL
  4. {
  5. 	template<class T> class multiset
  6. 	{
  7.     	class node
  8.     	{
  9.         	friend class multiset; T key; size_t count, height; node *left, *right;
  10.  
  11.         	node(const T x) : key(x), count(1), height(1), left(nullptr), right(nullptr) {}
  12.  
  13.         	friend size_t Height(const node* t)
  14.         	{
  15.             	return t?t->height:0;
  16.         	}
  17.  
  18.         	node* update_height()
  19.         	{
  20.             	height = std::max(Height(left),Height(right))+1; return this;
  21.         	}
  22.  
  23.         	int Balance() const
  24.         	{
  25.             	return int(Height(left))-int(Height(right));
  26.         	}
  27.  
  28.         	friend node* rotate_right_aux(node* y)
  29.         	{
  30.             	node *x = y->left, *z = x->right;
  31.  
  32.             	x->right = y, y->left = z, y->update_height();
  33.  
  34.             	return x->update_height();
  35.         	}
  36.  
  37.         	friend node* rotate_left_aux(node* x)
  38.         	{
  39.             	node *y = x->right, *z = y->left;
  40.  
  41.             	y->left = x, x->right = z, x->update_height();
  42.  
  43.             	return y->update_height();
  44.         	}
  45.  
  46.         	node* rotate_right(const T x)
  47.         	{
  48.             	if (x < left->key)
  49.                 	return rotate_right_aux(this);
  50.  
  51.             	if (left->key < x)
  52.             	{
  53.                 	left = rotate_left_aux(left);
  54.  
  55.                 	return rotate_right_aux(this);
  56.             	}
  57.  
  58.             	return this;
  59.         	}
  60.  
  61.         	node* rotate_left(const T x)
  62.         	{
  63.             	if (right->key < x)
  64.                 	return rotate_left_aux(this);
  65.  
  66.             	if (x < right->key)
  67.             	{
  68.                 	right = rotate_right_aux(right);
  69.  
  70.                 	return rotate_left_aux(this);
  71.             	}
  72.  
  73.             	return this;
  74.         	}
  75.  
  76.         	friend node* insert_key(node* t, const T x)
  77.         	{
  78.             	return t? t->insert(x):new node(x);
  79.         	}
  80.  
  81.         	node* insert(const T x)
  82.         	{
  83.             	if (x < key)
  84.                 	left = insert_key(left,x);
  85.             	else if (key < x)
  86.                 	right = insert_key(right,x);
  87.             	else
  88.             	{
  89.                 	count++; return this;
  90.             	}
  91.  
  92.             	update_height(); int balance = Balance();
  93.  
  94.             	if (balance > 1)
  95.                 	return rotate_right(x);
  96.  
  97.             	if (balance < -1)
  98.                 	return rotate_left(x);
  99.  
  100.             	return this;
  101.         	}
  102.  
  103.         	template<class OutputIterator>
  104.         	OutputIterator copy_all(OutputIterator result, bool distinct) const
  105.         	{
  106.         		if(left)
  107.         			result = left->copy_all(result,distinct);
  108.  
  109.         		*result++ = key;
  110.  
  111.         		if(not distinct)
  112.                     for(size_t j = 1; j < count;++j)
  113.                         *result++ = key;
  114.  
  115.         		if(right)
  116.         			result = right->copy_all(result,distinct);
  117.  
  118.                 return result;
  119.         	}
  120.  
  121. 			friend std::ostream& operator << (std::ostream& out, const node* t)
  122. 			{
  123. 				if (t->left)
  124. 					out << t->left << ' ';
  125.  
  126. 				out << t->key;
  127.  
  128. 				for(int i = 1, n = t->count; i < n; i++)
  129. 					out << ' ' << t->key;
  130.  
  131. 				if (t->right)
  132. 					out << ' ' << t->right;
  133.  
  134. 				return out;
  135. 			}
  136.  
  137.     	} *root;
  138.  
  139. 	public:
  140.     	multiset() : root(nullptr) {}
  141.  
  142.     	void insert(T key)
  143.     	{
  144.         	root = insert_key(root,key);
  145.     	}
  146.  
  147. 		template<class InputIterator>
  148.     	void insert(InputIterator first, InputIterator last)
  149.     	{
  150.     	    while(first != last)
  151.                 root = insert_key(root,*first++);
  152.     	}
  153.  
  154.     	template<class OutputIterator>
  155.     	OutputIterator copy_all(OutputIterator result, bool distinct = false) const
  156.     	{
  157.     		if(root)
  158.     			result = root->copy_all(result,distinct);
  159.  
  160.             return result;
  161.     	}
  162.  
  163.     	friend std::ostream& operator << (std::ostream& out, const multiset& t)
  164.     	{
  165.     		if(t.root)
  166.     			out << t.root;
  167.  
  168.     		return out;
  169.     	}
  170. 	};
  171. }
  172.  
  173. namespace timer
  174. {
  175.     typedef std::chrono::high_resolution_clock     Clock_t;
  176.     typedef std::chrono::time_point<Clock_t>        Time_t;
  177.     typedef std::chrono::milliseconds         Time_scale_t;
  178.  
  179.     static Time_t present;
  180.  
  181.     inline void reset()
  182.     {
  183.         present = Clock_t::now();
  184.     }
  185.  
  186.     inline size_t elapsed_time()
  187.     {
  188.         auto past = present;
  189.  
  190.         reset();
  191.  
  192.         return std::chrono::duration_cast<Time_scale_t>(present-past).count();
  193.     }
  194. }
  195.  
  196. using namespace std;
  197.  
  198. inline void time_info(const string& info, size_t t)
  199. {
  200. 	cout << "time(" << info << ") = " << t << " msec" << endl;
  201. }
  202.  
  203.  
  204. const int m = 1e5, n = 2e6, N = 1e5; mt19937_64 Random;
  205.  
  206. vector<int> a1(n), x(n), a2(n), q(m), ans(m);
  207.  
  208. AVL::multiset<int> b1; multiset<int> b2;
  209.  
  210. int main()
  211. {
  212. 	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  213.  
  214. 	for_each(q.begin(),q.end(),[](int &key){key = Random()%N;}),
  215.     for_each(x.begin(),x.end(),[](int &key){key = 1+Random()%N;}),
  216.     timer::reset(),
  217.     b1.insert(x.begin(),x.end());
  218.  
  219. 	const auto u_search = [](int a)
  220. 	{
  221. 		return upper_bound(a1.begin(),a1.end(),a)-a1.begin();
  222. 	};
  223.  
  224. 	auto t_insert1 = timer::elapsed_time();
  225.  
  226. 	b2.insert(x.begin(),x.end());
  227.  
  228. 	auto t_insert2 = timer::elapsed_time();
  229.  
  230.     b1.copy_all(a1.begin());
  231.  
  232.     auto t_copy1 = timer::elapsed_time();
  233.  
  234.     copy(b2.begin(),b2.end(),a1.begin());
  235.  
  236.     auto t_copy2 = timer::elapsed_time();
  237.  
  238.     transform(q.begin(),q.end(),ans.begin(),u_search);
  239.  
  240.     auto t_upper_bound = timer::elapsed_time();
  241.  
  242.     cout << "Performance comparison using " << n << " items" << endl,
  243.     time_info("insert-AVL-multiset",t_insert1),
  244.     time_info("insert-std-multiset",t_insert2),
  245.     time_info("copy-AVL-multiset",t_copy1),
  246.     time_info("copy-std-multiset",t_copy2),
  247.     cout << "Performance of processing " << m << " queries" << endl,
  248.     time_info("upper-bound",t_upper_bound);
  249. }
  250.  
Success #stdin #stdout 2.32s 113728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Performance comparison using 2000000 items
time(insert-AVL-multiset) = 414 msec
time(insert-std-multiset) = 1502 msec
time(copy-AVL-multiset) = 8 msec
time(copy-std-multiset) = 190 msec
Performance of processing 100000 queries
time(upper-bound) = 19 msec
https://ideone.com/Fdupoh
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!