3 * \file RandomAccessList.h
4 * This file is part of LyX, the document processor.
5 * Licence details can be found in the file COPYING.
7 * \author Abdelrazak Younes
9 * Full author contact details are available in file CREDITS.
13 #ifndef RANDOM_ACESS_LIST_H
14 #define RANDOM_ACESS_LIST_H
18 #include <boost/utility.hpp>
24 #define USE_OLD_ITERATOR 1
26 /// Random Access List.
28 This templatized class provide a std::vector like interface to a
29 standard std::list underneath. An important property is that it
30 keeps the std::list::iterator interface. A typical use would be:
32 typedef RandomAccessList<some_class> MyContainer;
34 Then you can use MyContainer as if it was a standard
35 std::vector<some_class> for operator[] access and as if it was a
36 standard std::list for iterator access. The main difference with
37 std::vector is that insertion of elements is much less costly. Compared
38 to a standard list alone, there is of course a small overhead because
39 the class always keeps its internal vector of iterator (it_vector_) up
43 class RandomAccessList {
46 typedef std::list<T> Container;
47 typedef typename Container::reference reference;
48 typedef typename Container::const_reference const_reference;
51 typedef typename Container::iterator iterator;
52 // const_iterator (below)
53 typedef typename Container::const_iterator const_iterator;
57 typedef typename Container::size_type size_type;
58 typedef typename Container::difference_type difference_type;
59 typedef typename Container::value_type value_type;
60 typedef typename Container::allocator_type allocator_type;
61 typedef typename Container::pointer pointer;
62 typedef typename Container::const_pointer const_pointer;
64 // const_reverse_iterator
66 typedef std::vector<typename Container::iterator> IterCont;
68 // construct/copy/destroy
73 // RandomAccessList(size_type n T const & value = T())
75 template<class InputIterator>
76 RandomAccessList(InputIterator first, InputIterator last)
83 RandomAccessList(RandomAccessList const & x)
85 assign(x.begin(), x.end());
88 // ~RandomAccessList()
91 RandomAccessList & operator=(RandomAccessList const & x)
93 assign(x.begin(), x.end());
97 template<class InputIterator>
98 void assign(InputIterator first, InputIterator last)
100 container_.assign(first, last);
105 // void assign(size_type n, T const & u);
111 return container_.begin();
114 const_iterator begin() const
116 return container_.begin();
121 return container_.end();
124 const_iterator end() const
126 return container_.end();
129 // reverse_iterator rbegin();
130 // const_reverse_iterator rbegin() const;
131 // reverse_iterator rend();
132 // const_reverse_iterator rend() const;
135 size_type size() const
137 return iterCont_.size();
140 size_type max_size() const
142 return iterCont_.max_size();
145 // void resize(size_type sz, T c = T());
147 size_type capacity() const
149 return iterCont_.capacity();
154 return container_.empty();
157 // void reserve(size_type n);
161 reference operator[](size_type pos)
163 return *iterCont_[pos];
167 const_reference operator[](size_type pos) const
169 return *iterCont_[pos];
172 reference at(size_type pos)
174 return *iterCont_.at(pos);
177 const_reference at(size_type pos) const
179 return *iterCont_.at(pos);
184 return container_.front();
187 const_reference front() const
189 return container_.front();
194 return container_.back();
197 const_reference back() const
199 return container_.back();
204 void push_back(T const & x)
206 typename Container::iterator it =
207 container_.insert(container_.end(), x);
208 iterCont_.push_back(it);
213 container_.pop_back();
214 iterCont_.pop_back();
217 iterator insert(iterator position, T const & x)
219 typename Container::iterator it =
220 container_.insert(position, x);
225 // void insert(iterator position, size_type n, T const & x);
227 template<class InputIterator>
228 void insert(iterator position,
229 InputIterator first, InputIterator last)
231 container_.insert(position, first, last);
235 iterator erase(iterator position)
237 typename Container::iterator it =
238 container_.erase(position);
243 iterator erase(iterator first, iterator last)
245 typename Container::iterator it =
246 container_.erase(first, last);
251 void swap(RandomAccessList & x)
253 std::swap(container_, x.container_);
254 std::swap(iterCont_, x.iterCont_);
264 void recreateVector()
267 typename Container::iterator beg = container_.begin();
268 typename Container::iterator end = container_.end();
269 for (; beg != end; ++beg)
270 iterCont_.push_back(beg);
274 Container container_;
275 /// Our container of iterators.