fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3.  
  4. template<typename T>
  5. struct Link
  6. {
  7.     T val;
  8.     Link* prev;
  9.     Link* succ;
  10.  
  11.     Link(const T& value, Link* p = nullptr, Link* s = nullptr)
  12.         :val{value},prev {p}, succ{ s } {}
  13.  
  14.     Link* add_ordered_(Link* link)
  15.     {
  16.         if (link == nullptr) {
  17.             return this;   
  18.         }
  19.         auto p = find_neighbor(*link);
  20.         link->insert_between(p.first, p.second);
  21.         if (prev) {
  22.             return prev; // == link
  23.         }
  24.         return this;
  25.     }
  26.  
  27. private:
  28.     std::pair<Link*, Link*> find_neighbor(const Link& link) {
  29.         Link* left = nullptr;
  30.         Link* right = this;
  31.  
  32.         while (right && right->val < link.val) {
  33.             left = right;
  34.             right = right->succ;
  35.         }
  36.         return {left, right};
  37.     }
  38.  
  39.     void insert_between(Link* left, Link* right)
  40.     {
  41.         prev = left;
  42.         succ = right;
  43.         if (left) {
  44.             left->succ = this;   
  45.         }
  46.         if (right) {
  47.             right->prev = this;   
  48.         }
  49.     }
  50. };
  51.  
  52. template<typename T>
  53. void print_link(Link<T>* x)
  54. {
  55.     while (x)
  56.     {
  57.         std::cout << x->val << std::endl;
  58.         x = x->succ;
  59.     }
  60. }
  61.  
  62. int main()
  63. {
  64.     Link<int> number5{5};
  65.     Link<int> numbers[]{{7}, {3}, {25}, {19}, {22}, {16}, {44}, {11}, {37}};
  66.  
  67.     auto* list = &number5;
  68.  
  69.     for (auto& number : numbers) {
  70.         list = list->add_ordered_(&number);
  71.     }
  72.     print_link(list);
  73.     std::cout << std::endl;
  74. }
  75.  
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
5
7
11
16
19
22
25
37
44
https://ideone.com/OEEC0P
language:
C++14 (gcc 8.3)
created:
7 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!