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
162
163
164
165
166
167
168
169
170
171
172
|
// Copyright 2013 The Chromium Authors
// 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 <stddef.h>
#include <algorithm>
#include <iterator>
#include <list>
#include <memory>
#include <set>
#include "base/check_op.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_front(const T& elem) {
if (set_.find(elem) != set_.end())
return;
set_.insert(elem);
list_.push_front(elem);
}
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::ranges::find(list_, elem);
CHECK(it != list_.end());
list_.erase(it);
}
void clear() {
set_.clear();
list_.clear();
}
size_t count(const T& elem) const {
return set_.find(elem) == set_.end() ? 0 : 1;
}
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 value_type& reference;
typedef value_type* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
explicit iterator(typename std::list<T>::iterator it) : it_(it) {}
self_type& operator++() {
++it_;
return *this;
}
self_type operator++(int /*ignored*/) {
self_type result(*this);
++(*this);
return result;
}
self_type& operator--() {
--it_;
return *this;
}
self_type operator--(int /*ignored*/) {
self_type result(*this);
--(*this);
return result;
}
reference operator*() const { return *it_; }
pointer operator->() const { return &(*it_); }
friend bool operator==(const iterator&, const iterator&) = default;
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 const value_type& reference;
typedef const value_type* 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) {}
self_type& operator++() {
++it_;
return *this;
}
self_type operator++(int ignored) {
self_type result(*this);
++(*this);
return result;
}
self_type& operator--() {
--it_;
return *this;
}
self_type operator--(int ignored) {
self_type result(*this);
--(*this);
return result;
}
reference operator*() const { return *it_; }
pointer operator->() const { return &(*it_); }
bool operator==(const const_iterator& rhs) const { return it_ == rhs.it_; }
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<std::unique_ptr<T>> as the current
// implementation would fail.
// TODO(jsbell): Support scoped_ptr through specialization.
template <typename T>
class list_set<std::unique_ptr<T>>;
#endif // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
|
