blob: 300bd7438357e15993ba55466484904350a7b6ff (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
// Template for sorted list
// Author: U.Breymann / H.P.Weber
// Date: 05.05.05
#ifndef SORTEDLIST_H
#define SORTEDLIST_H
#include <list>
#include <algorithm> // find
#include "compare.h"
template< class T >
class SortedList
{
public:
typedef std::list< T >::iterator Iterator;
typedef std::list< T >::const_iterator ConstIterator;
SortedList( const Compare< T >& cmp = Compare< T >() ) : comp( cmp ) { }
virtual ~SortedList() { }
bool empty() const { return myList.empty(); }
int size() const { return myList.size(); }
// take first or last element
void pop_front() { myList.pop_front(); }
void pop_back() { myList.pop_back(); }
// read first or last element
T& front() { return myList.front(); }
const T& front() const { return myList.front(); }
T& back() { return myList.back(); }
const T& back() const { return myList.back(); }
Iterator begin() { return myList.begin(); }
ConstIterator begin() const { return myList.begin(); }
Iterator end() { return myList.end(); }
ConstIterator end() const { return myList.end(); }
void erase( Iterator& pos ) { myList.erase( pos ); }
// find element
Iterator find( const T& value )
{
return std::find( myList.begin(), myList.end(), value );
}
// sorted insert
Iterator insert( const T& value )
{
// find place to insert
Iterator temp( begin() );
while( temp != end() && comp( *temp, value ) ) ++temp;
return myList.insert( temp, value );
}
private:
std::list< T > myList;
Compare< T > comp;
};
#endif
|
