Download code

Jump to: navigation, search

Back to Unrolled_linked_list_(C_Plus_Plus)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

list_test_output.txt

1 1 2 3 4 
2 1 2 42 3 4 
3 1 2 42 4
4 10 2 42 4
5 
6 1 2 3 4 
7 42 42 42 42 


build.log

 1 In file included from /tmp/litprog7460995/unrolled_list.h:203:0,
 2                  from /tmp/litprog7460995/performance.cpp:18:
 3 /tmp/litprog7460995/unrolled_list.hpp:189:3: error: stray '@' in program
 4 /tmp/litprog7460995/unrolled_list.hpp:196:3: error: stray '@' in program
 5 In file included from /tmp/litprog7460995/performance.cpp:18:0:
 6 /tmp/litprog7460995/unrolled_list.h:52:10: error: 'ptrdiff_t' does not name a type
 7 In file included from /tmp/litprog7460995/unrolled_list.h:203:0,
 8                  from /tmp/litprog7460995/performance.cpp:18:
 9 /tmp/litprog7460995/unrolled_list.hpp: In constructor 'unrolled_list<T, NODE_SIZE>::unrolled_list()':
10 /tmp/litprog7460995/unrolled_list.hpp:189:37: error: expected '{' before 'text'
11 /tmp/litprog7460995/unrolled_list.hpp: At global scope:
12 /tmp/litprog7460995/unrolled_list.hpp:189:37: error: 'text' does not name a type
13 /tmp/litprog7460995/unrolled_list.hpp: In copy constructor 'unrolled_list<T, NODE_SIZE>::unrolled_list(const unrolled_list<T, NODE_SIZE>&)':
14 /tmp/litprog7460995/unrolled_list.hpp:196:37: error: expected '{' before 'text'
15 /tmp/litprog7460995/unrolled_list.hpp: At global scope:
16 /tmp/litprog7460995/unrolled_list.hpp:196:37: error: 'text' does not name a type
17 /tmp/litprog7460995/performance.cpp: In function 'clock_t test_iteration(TElement)':
18 /tmp/litprog7460995/performance.cpp:54:30: error: there are no arguments to 'printf' that depend on a template parameter, so a declaration of 'printf' must be available [-fpermissive]
19 /tmp/litprog7460995/performance.cpp:54:30: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
20 /tmp/litprog7460995/performance.cpp: In function 'void time_test_push_back()':
21 /tmp/litprog7460995/performance.cpp:66:98: error: 'printf' was not declared in this scope
22 /tmp/litprog7460995/performance.cpp: In function 'void time_test_push_front()':
23 /tmp/litprog7460995/performance.cpp:87:99: error: 'printf' was not declared in this scope
24 /tmp/litprog7460995/performance.cpp: In function 'void time_test_iteration()':
25 /tmp/litprog7460995/performance.cpp:107:98: error: 'printf' was not declared in this scope
26 /tmp/litprog7460995/performance.cpp: In function 'clock_t test_iteration(TElement) [with TList = std::list<int>, TElement = int, clock_t = long int]':
27 /tmp/litprog7460995/performance.cpp:106:47:   instantiated from here
28 /tmp/litprog7460995/performance.cpp:54:13: error: 'printf' was not declared in this scope
29 /tmp/litprog7460995/performance.cpp: In function 'clock_t test_iteration(TElement) [with TList = std::vector<int>, TElement = int, clock_t = long int]':
30 /tmp/litprog7460995/performance.cpp:109:49:   instantiated from here
31 /tmp/litprog7460995/performance.cpp:54:13: error: 'printf' was not declared in this scope
32 /tmp/litprog7460995/performance.cpp: In function 'clock_t test_iteration(TElement) [with TList = unrolled_list<int, 1024>, TElement = int, clock_t = long int]':
33 /tmp/litprog7460995/performance.cpp:112:56:   instantiated from here
34 /tmp/litprog7460995/performance.cpp:54:13: error: 'printf' was not declared in this scope
35 /tmp/litprog7460995/performance.cpp: In function 'clock_t test_iteration(TElement) [with TList = unrolled_list<int, 128>, TElement = int, clock_t = long int]':
36 /tmp/litprog7460995/performance.cpp:115:55:   instantiated from here
37 /tmp/litprog7460995/performance.cpp:54:13: error: 'printf' was not declared in this scope
38 In file included from /tmp/litprog7460995/unrolled_list.h:203:0,
39                  from /tmp/litprog7460995/list_test.cpp:18:
40 /tmp/litprog7460995/unrolled_list.hpp:204:3: error: stray '@' in program
41 /tmp/litprog7460995/unrolled_list.hpp:211:3: error: stray '@' in program
42 In file included from /tmp/litprog7460995/list_test.cpp:18:0:
43 /tmp/litprog7460995/unrolled_list.h:52:10: error: 'ptrdiff_t' does not name a type
44 In file included from /tmp/litprog7460995/unrolled_list.h:203:0,
45                  from /tmp/litprog7460995/list_test.cpp:18:
46 /tmp/litprog7460995/unrolled_list.hpp: In constructor 'unrolled_list<T, NODE_SIZE>::unrolled_list()':
47 /tmp/litprog7460995/unrolled_list.hpp:204:37: error: expected '{' before 'text'
48 /tmp/litprog7460995/unrolled_list.hpp: At global scope:
49 /tmp/litprog7460995/unrolled_list.hpp:204:37: error: 'text' does not name a type
50 /tmp/litprog7460995/unrolled_list.hpp: In copy constructor 'unrolled_list<T, NODE_SIZE>::unrolled_list(const unrolled_list<T, NODE_SIZE>&)':
51 /tmp/litprog7460995/unrolled_list.hpp:211:37: error: expected '{' before 'text'
52 /tmp/litprog7460995/unrolled_list.hpp: At global scope:
53 /tmp/litprog7460995/unrolled_list.hpp:211:37: error: 'text' does not name a type


hijacker
hijacker
hijacker
hijacker

unrolled_list.h

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Unrolled_linked_list_(C_Plus_Plus)?oldid=19226
 14 */
 15 
 16 #include <iterator>
 17 
 18 template <typename T, int NODE_SIZE>
 19 class unrolled_list
 20 {
 21   private:
 22     struct node
 23     {
 24         static const int values_size_lb =
 25 	    (NODE_SIZE - 2*sizeof(node*) - sizeof(int))/sizeof(T);
 26 	static const int values_size =
 27 	    values_size_lb == 0 ? 1 : values_size_lb;
 28 
 29         node()
 30           : next(NULL), prev(NULL), count(0)
 31         {}
 32 
 33         node* next;
 34         node* prev;
 35         int   count;
 36         T values[values_size];
 37     };
 38 
 39     node* _head;
 40     node* _tail;
 41     int _size;
 42     void merge_node_with_next(node* node);
 43 
 44 
 45   public:
 46     class const_iterator
 47       : public std::iterator<std::forward_iterator_tag, T, size_t, T const*, T const&>
 48     {
 49       public:
 50         typedef std::bidirectional_iterator_tag iterator_category;
 51 	typedef T         value_type;
 52 	typedef ptrdiff_t difference_type;
 53 	typedef T const*  pointer;
 54 	typedef T const&  reference;
 55 	const_iterator(node* cur_node = NULL, int cur_index = 0)
 56 	  : _curnode(cur_node), _curindex(cur_index)
 57 	{}
 58 	reference operator*()
 59 	{
 60 	    return _curnode->values[_curindex];
 61 	}
 62 
 63 	pointer operator ->()
 64 	{
 65 	    return &(**this);
 66 	}
 67 
 68 	// The lack of arguments indicates that this is prefix ++
 69 	const_iterator& operator++()
 70 	{
 71 	    _curindex++;
 72 	    if (_curindex >= _curnode->count &&
 73 	        _curnode->next != NULL)
 74 	    {
 75 	        _curnode = _curnode->next;
 76 	        _curindex = 0;
 77 	    }
 78 	    return *this;
 79 	}
 80 
 81 	// The lack of arguments indicates that this is prefix --
 82 	const_iterator& operator--()
 83 	{
 84 	    _curindex--;
 85 	    if (_curindex < 0)
 86 	    {
 87 	        _curnode = _curnode->prev;
 88 	        _curindex = _curnode->count - 1;
 89 	    }
 90 	    return *this;
 91 	}
 92 
 93 	// The dummy argument indicates that this is the postfix ++
 94 	const_iterator operator++(int)
 95 	{
 96 	    const_iterator old_it = *this;
 97 	    ++(*this);
 98 	    return old_it;
 99 	}
100 
101 	// The dummy argument indicates that this is the postfix --
102 	const_iterator operator--(int)
103 	{
104 	    const_iterator old_it = *this;
105 	    --(*this);
106 	    return old_it;
107 	}
108 
109 	bool operator ==(const_iterator const& rhs)
110 	{
111 	    return _curnode == rhs._curnode &&
112 	           _curindex == rhs._curindex;
113 	}
114 
115 	bool operator !=(const_iterator const& rhs)
116 	{
117 	  return !(*this == rhs);
118 	}
119       protected:
120         node* _curnode;
121         int _curindex;
122     };
123 
124     class iterator
125       : public const_iterator
126     {
127       public:
128         iterator(node* iter_node = NULL, int iter_index = 0)
129 	  : const_iterator(iter_node, iter_index)
130 	{}
131 
132 	typedef std::bidirectional_iterator_tag iterator_category;
133 	typedef T      value_type;
134 	typedef size_t difference_type;
135 	typedef T*     pointer;
136 	typedef T&     reference;
137 
138 	using const_iterator::_curnode;
139 	using const_iterator::_curindex;
140 
141 	reference operator*()
142 	{
143 	    return _curnode->values[_curindex];
144 	}
145 
146 	pointer operator ->()
147 	{
148 	    return &(**this);
149 	}
150 
151 	// The lack of arguments indicates that this is prefix ++
152 	iterator& operator++()
153 	{
154 	    const_iterator::operator++();
155 	    return *this;
156 	}
157 
158 	// The lack of arguments indicates that this is prefix --
159 	iterator& operator--()
160 	{
161 	    const_iterator::operator--();
162 	    return *this;
163 	}
164 
165 	// The dummy argument indicates that this is the postfix ++
166 	iterator operator++(int)
167 	{
168 	    iterator old_it = *this;
169 	    ++(*this);
170 	    return old_it;
171 	}
172 
173 	// The dummy argument indicates that this is the postfix --
174 	iterator operator--(int)
175 	{
176 	    iterator old_it = *this;
177 	    --(*this);
178 	    return old_it;
179 	}
180     };
181 
182     unrolled_list();
183     unrolled_list(unrolled_list<T,NODE_SIZE> const& rhs);
184     ~unrolled_list();
185     iterator begin();
186     iterator end();
187     const_iterator begin() const;
188     const_iterator end() const;
189     void push_front(T const& elt);
190     void push_back(T const& elt);
191     iterator insert(iterator where, T const& elt);
192     iterator erase(iterator where);
193     void pop_front();
194     void pop_back();
195     void clear();
196     unrolled_list& operator =(unrolled_list<T,NODE_SIZE> const& rhs);
197 
198     size_t size() const;
199     bool empty() const;
200     friend class unrolled_list<T,NODE_SIZE>::iterator;
201 };
202 
203 #include "unrolled_list.hpp"
204 


hijacker
hijacker
hijacker
hijacker

performance.cpp

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Unrolled_linked_list_(C_Plus_Plus)?oldid=19226
 14 */
 15 
 16 #include <vector>
 17 #include <list>
 18 #include "unrolled_list.h"
 19 
 20 
 21 template <typename TList, typename TElement>
 22 void test_push_back(TElement value)
 23 {
 24     TList lst;
 25     for (int i=0; i<50000000; i++)
 26     {
 27         lst.push_back(value);
 28     }
 29 }
 30 template <typename TList, typename TElement>
 31 void test_push_front(TElement value)
 32 {
 33     TList lst;
 34     for (int i=0; i<500000; i++)
 35     {
 36         lst.insert(lst.begin(), value);
 37     }
 38 }
 39 
 40 template <typename TList, typename TElement>
 41 clock_t test_iteration(TElement value)
 42 {
 43     TList lst;
 44     for (int i=0; i<50000000; i++)
 45     {
 46         lst.push_back(value);
 47     }
 48     clock_t start = clock();
 49     typename TList::iterator it;
 50     for (it = lst.begin(); it != lst.end(); it++)
 51     {
 52         if (*it != value)
 53         {
 54             printf("Error!\n");
 55         }
 56     }
 57     return start;
 58 }
 59 
 60 void time_test_push_back()
 61 {
 62     clock_t start;
 63 
 64     start = clock();
 65     test_push_back< std::list<int> >(0);
 66     printf("test_push_back< std::list<int> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 67 
 68     start = clock();
 69     test_push_back< std::vector<int> >(0);
 70     printf("test_push_back< std::vector<int> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 71 
 72     start = clock();
 73     test_push_back< unrolled_list<int,1024> >(0);
 74     printf("test_push_back< unrolled_list<int,1024> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 75 
 76     start = clock();
 77     test_push_back< unrolled_list<int,128> >(0);
 78     printf("test_push_back< unrolled_list<int,128> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 79 }
 80 
 81 void time_test_push_front()
 82 {
 83     clock_t start;
 84 
 85     start = clock();
 86     test_push_front< std::list<int> >(0);
 87     printf("test_push_front< std::list<int> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 88 
 89     start = clock();
 90     test_push_front< std::vector<int> >(0);
 91     printf("test_push_front< std::vector<int> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 92 
 93     start = clock();
 94     test_push_front< unrolled_list<int,1024> >(0);
 95     printf("test_push_front< unrolled_list<int,1024> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
 96 
 97     start = clock();
 98     test_push_front< unrolled_list<int,128> >(0);
 99     printf("test_push_front< unrolled_list<int,128> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
100 }
101 
102 void time_test_iteration()
103 {
104     clock_t start;
105 
106     start = test_iteration< std::list<int> >(0);
107     printf("test_iteration< std::list<int> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
108 
109     start = test_iteration< std::vector<int> >(0);
110     printf("test_iteration< std::vector<int> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
111 
112     start = test_iteration< unrolled_list<int,1024> >(0);
113     printf("test_iteration< unrolled_list<int,1024> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
114 
115     start = test_iteration< unrolled_list<int,128> >(0);
116     printf("test_iteration< unrolled_list<int,128> >: %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC);
117 }
118 
119 
120 int main()
121 {
122     time_test_push_back();
123     time_test_push_front();
124     time_test_iteration();
125     return 0;
126 }


hijacker
hijacker
hijacker
hijacker

unrolled_list.hpp

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Unrolled_linked_list_(C_Plus_Plus)?oldid=19226
 14 */
 15 
 16 template <typename T, int NODE_SIZE>
 17 inline typename unrolled_list<T,NODE_SIZE>::iterator unrolled_list<T,NODE_SIZE>::begin()
 18 {
 19     return iterator(_head, 0);
 20 }
 21 
 22 template <typename T, int NODE_SIZE>
 23 inline typename unrolled_list<T,NODE_SIZE>::iterator unrolled_list<T,NODE_SIZE>::end()
 24 {
 25     return iterator(_tail, _tail->count);
 26 }
 27 template <typename T, int NODE_SIZE>
 28 inline typename unrolled_list<T,NODE_SIZE>::const_iterator unrolled_list<T,NODE_SIZE>::begin() const
 29 {
 30     return const_iterator(_head, 0);
 31 }
 32 
 33 template <typename T, int NODE_SIZE>
 34 inline typename unrolled_list<T,NODE_SIZE>::const_iterator unrolled_list<T,NODE_SIZE>::end() const
 35 {
 36     return const_iterator(_tail, _tail->count);
 37 }
 38 template <typename T, int NODE_SIZE>
 39 inline typename unrolled_list<T,NODE_SIZE>::iterator
 40     unrolled_list<T,NODE_SIZE>::insert(
 41         typename unrolled_list<T,NODE_SIZE>::iterator where, T const& elt)
 42 {
 43     const int num_values = unrolled_list<T,NODE_SIZE>::node::values_size;
 44     if (where._curnode->count == num_values) // if node is full
 45     {
 46         node* n = new node;
 47         
 48         if (where._curindex != where._curnode->count)
 49         {
 50             for(int i=0; i < (num_values+1)/2; i++)
 51 	    {
 52 	        n->values[i] = where._curnode->values[i + num_values/2];
 53 	    }
 54 	    where._curnode->count = num_values/2;
 55 	    n->count = (num_values+1)/2;
 56         }
 57 
 58         n->next = where._curnode->next;
 59 	n->prev = where._curnode;
 60 	if (where._curnode->next != NULL)
 61 	{
 62 	    where._curnode->next->prev = n;
 63 	}
 64 	where._curnode->next = n;
 65 	if (n->next == NULL)
 66 	{
 67 	    _tail = n;
 68 	}
 69         if (where._curindex >= where._curnode->count)
 70 	{
 71 	    where._curindex -= where._curnode->count;
 72 	    where._curnode = n;
 73 	}
 74     }
 75     for(int i=where._curnode->count; i > where._curindex; i--)
 76     {
 77         where._curnode->values[i] = where._curnode->values[i-1];
 78     }
 79     where._curnode->values[where._curindex] = elt;
 80     where._curnode->count++;
 81     _size++;
 82     return where;
 83 }
 84 template <typename T, int NODE_SIZE>
 85 inline void unrolled_list<T,NODE_SIZE>::push_front(T const& elt)
 86 {
 87     insert(begin(), elt);
 88 }
 89 
 90 template <typename T, int NODE_SIZE>
 91 inline void unrolled_list<T,NODE_SIZE>::push_back(T const& elt)
 92 {
 93     insert(end(), elt);
 94 }
 95 template <typename T, int NODE_SIZE>
 96 inline typename unrolled_list<T,NODE_SIZE>::iterator
 97   unrolled_list<T,NODE_SIZE>::erase(
 98     typename unrolled_list<T,NODE_SIZE>::iterator where)
 99 {
100     for(int i=where._curindex; i < where._curnode->count - 1; i++)
101     {
102         where._curnode->values[i] = where._curnode->values[i+1];
103     }
104     where._curnode->count--;
105     _size--;
106     const int num_values = unrolled_list<T,NODE_SIZE>::node::values_size;
107     const int threshold = num_values >= 5 ? num_values*4/5 : num_values - 1;
108     if (where._curnode->prev != NULL &&
109         (where._curnode->count == 0 ||
110          where._curnode->count + where._curnode->prev->count <= threshold))
111     {
112         where._curnode = where._curnode->prev;
113         where._curindex += where._curnode->count;
114         merge_node_with_next(where._curnode);
115     }
116     else if (where._curnode->next != NULL &&
117              (where._curnode->count == 0 ||
118               where._curnode->count + where._curnode->next->count <= threshold))
119     {
120         merge_node_with_next(where._curnode);
121     }
122     if (where._curindex >= where._curnode->count &&
123         where._curnode->next != NULL)
124     {
125         where._curindex -= where._curnode->count;
126         where._curnode = where._curnode->next;
127     }
128     return where;
129 }
130 template <typename T, int NODE_SIZE>
131 inline void unrolled_list<T,NODE_SIZE>::merge_node_with_next(
132   typename unrolled_list<T,NODE_SIZE>::node* node)
133 {
134     typename unrolled_list<T,NODE_SIZE>::node* next = node->next;
135     const int count = node->count;
136     for(int i=0; i<next->count; i++)
137     {
138         node->values[i + count] = next->values[i];
139     }
140     node->count += next->count;
141     node->next = node->next->next;
142     if (node->next == NULL)
143     {
144         _tail = node;
145     }
146     delete next;
147 }
148 template <typename T, int NODE_SIZE>
149 inline void unrolled_list<T,NODE_SIZE>::pop_front()
150 {
151     erase(begin());
152 }
153 
154 template <typename T, int NODE_SIZE>
155 inline void unrolled_list<T,NODE_SIZE>::pop_back()
156 {
157     erase(--(end()));
158 }
159 /* Same effect as:
160    while(begin() != end())
161    {
162        pop_back();
163    }
164 */
165 template <typename T, int NODE_SIZE>
166 inline void unrolled_list<T,NODE_SIZE>::clear()
167 {
168     typename unrolled_list<T,NODE_SIZE>::node *n, *n_next;
169     for (n = _head->next; n != NULL; n = n_next)
170     {
171         n_next = n->next;
172         delete n;
173     }
174     _head->count = 0;
175     _head->next = NULL;
176     _tail = _head;
177 }
178 template <typename T, int NODE_SIZE>
179 unrolled_list<T,NODE_SIZE>& unrolled_list<T,NODE_SIZE>::operator =(unrolled_list<T,NODE_SIZE> const& rhs)
180 {
181     clear();
182 
183     const_iterator rhs_it = rhs.begin();
184     for (rhs_it = rhs.begin(); rhs_it != rhs.end(); ++rhs_it)
185     {
186         push_back(*rhs_it);
187     }
188 
189     return *this;
190 }
191 template <typename T, int NODE_SIZE>
192 inline size_t unrolled_list<T,NODE_SIZE>::size() const
193 {
194   return _size;
195 }
196 
197 template <typename T, int NODE_SIZE>
198 inline bool unrolled_list<T,NODE_SIZE>::empty() const
199 {
200   return _size == 0;
201 }
202 template <typename T, int NODE_SIZE>
203 inline unrolled_list<T,NODE_SIZE>::unrolled_list()
204   : _head(new node), _tail(_head) @ text
205 
206     , _size(0)
207 {}
208 
209 template <typename T, int NODE_SIZE>
210 inline unrolled_list<T,NODE_SIZE>::unrolled_list(unrolled_list<T,NODE_SIZE> const& rhs)
211   : _head(new node), _tail(_head) @ text
212 
213     , _size(0)
214 {
215     *this = rhs;
216 }
217 
218 template <typename T, int NODE_SIZE>
219 inline unrolled_list<T,NODE_SIZE>::~unrolled_list()
220 {
221     clear();
222 }


hijacker
hijacker
hijacker
hijacker

list_test.cpp

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Unrolled_linked_list_(C_Plus_Plus)?oldid=19226
14 */
15 
16 #include <iostream>
17 
18 #include "unrolled_list.h"
19 
20 template <typename T, int NODE_SIZE>
21 void print_list(unrolled_list<T,NODE_SIZE> const& lst)
22 {
23   typename unrolled_list<T,NODE_SIZE>::const_iterator it;
24   for (it = lst.begin(); it != lst.end(); ++it)
25     std::cout << *it << " ";
26   std::cout << std::endl;
27 }
28 
29 int main()
30 {
31   unrolled_list<int,20> lst;
32   lst.push_back(2);
33   lst.push_back(3);
34   lst.push_front(1);
35   lst.push_back(4);
36   unrolled_list<int,20> list2;
37   list2 = lst;
38   print_list(lst);
39   unrolled_list<int,20>::iterator it;
40   it = lst.begin();
41   it++;
42   ++it;
43   it = lst.insert(it, 42);
44   print_list(lst);
45   ++it;
46   it = lst.erase(it);
47   print_list(lst);
48   it = lst.begin();
49   *it = 10;
50   print_list(lst);
51   lst.clear();
52   print_list(lst);
53   print_list(list2);
54   std::fill(list2.begin(), list2.end(), 42);
55   print_list(list2);
56   return 0;
57 }


hijacker
hijacker
hijacker
hijacker