blob: 1884b4bb925f6522357d1532bb1b477c2a1cebdd (
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
#define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
#include <algorithm>
#include <iterator>
#include <list>
#include <set>
#include "base/logging.h"
#include "base/memory/scoped_ptr.h"
//
// A container class that provides fast containment test (like a set)
// but maintains insertion order for iteration (like list).
//
// Member types of value (primitives and objects by value), raw pointers
// and scoped_refptr<> are supported.
//
template <typename T>
class list_set {
public:
list_set() {}
list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {}
list_set& operator=(const list_set<T>& other) {
list_ = other.list_;
set_ = other.set_;
return *this;
}
void insert(const T& elem) {
if (set_.find(elem) != set_.end())
return;
set_.insert(elem);
list_.push_back(elem);
}
void erase(const T& elem) {
if (set_.find(elem) == set_.end())
return;
set_.erase(elem);
typename std::list<T>::iterator it =
std::find(list_.begin(), list_.end(), elem);
DCHECK(it != list_.end());
list_.erase(it);
}
bool has(const T& elem) { return set_.find(elem) != set_.end(); }
size_t size() const {
DCHECK_EQ(list_.size(), set_.size());
return set_.size();
}
bool empty() const {
DCHECK_EQ(list_.empty(), set_.empty());
return set_.empty();
}
class const_iterator;
class iterator {
public:
typedef iterator self_type;
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {}
inline self_type& operator++() {
++it_;
return *this;
}
inline self_type operator++(int /*ignored*/) {
self_type result(*this);
++(*this);
return result;
}
inline self_type& operator--() {
--it_;
return *this;
}
inline self_type operator--(int /*ignored*/) {
self_type result(*this);
--(*this);
return result;
}
inline value_type& operator*() { return *it_; }
inline value_type* operator->() { return &(*it_); }
inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }
inline operator const_iterator() const { return const_iterator(it_); }
private:
typename std::list<T>::iterator it_;
};
class const_iterator {
public:
typedef const_iterator self_type;
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
explicit inline const_iterator(typename std::list<T>::const_iterator it)
: it_(it) {}
inline self_type& operator++() {
++it_;
return *this;
}
inline self_type operator++(int ignored) {
self_type result(*this);
++(*this);
return result;
}
inline self_type& operator--() {
--it_;
return *this;
}
inline self_type operator--(int ignored) {
self_type result(*this);
--(*this);
return result;
}
inline const value_type& operator*() { return *it_; }
inline const value_type* operator->() { return &(*it_); }
inline bool operator==(const const_iterator& rhs) const {
return it_ == rhs.it_;
}
inline bool operator!=(const const_iterator& rhs) const {
return it_ != rhs.it_;
}
private:
typename std::list<T>::const_iterator it_;
};
iterator begin() { return iterator(list_.begin()); }
iterator end() { return iterator(list_.end()); }
const_iterator begin() const { return const_iterator(list_.begin()); }
const_iterator end() const { return const_iterator(list_.end()); }
private:
std::list<T> list_;
std::set<T> set_;
};
// Prevent instantiation of list_set<scoped_ptr<T>> as the current
// implementation would fail.
// TODO(jsbell): Support scoped_ptr through specialization.
template <typename T>
class list_set<scoped_ptr<T> >;
#endif // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
|
