14 #ifndef STK_UTIL_UTIL_vecset_hpp 15 #define STK_UTIL_UTIL_vecset_hpp 58 template <
class Key,
class Compare = std::less<Key> >
62 struct const_key_type_meta_func
68 struct const_key_type_meta_func<T*>
70 typedef const T*
const type;
76 typedef Key value_type;
77 typedef Compare key_compare;
78 typedef Compare value_compare;
79 typedef typename const_key_type_meta_func<Key>::type const_key_type;
83 typedef std::vector<key_type> storage ;
87 typedef typename storage::allocator_type allocator_type ;
88 typedef typename allocator_type::reference reference ;
89 typedef typename allocator_type::const_reference const_reference ;
90 typedef typename allocator_type::pointer pointer ;
91 typedef typename allocator_type::const_pointer const_pointer ;
92 typedef typename storage::size_type size_type ;
93 typedef typename storage::difference_type difference_type ;
94 typedef typename storage::iterator iterator ;
95 typedef typename storage::const_iterator const_iterator ;
96 typedef typename storage::reverse_iterator reverse_iterator ;
97 typedef typename storage::const_reverse_iterator const_reverse_iterator ;
102 key_compare KeyComp ;
118 Storage = rhs.Storage ;
123 Storage.swap( v.Storage );
126 iterator begin() {
return Storage.begin(); }
127 iterator end() {
return Storage.end(); }
128 const_iterator begin()
const {
return Storage.begin(); }
129 const_iterator end()
const {
return Storage.end(); }
130 reverse_iterator rbegin() {
return Storage.rbegin(); }
131 reverse_iterator rend() {
return Storage.rend(); }
132 const_reverse_iterator rbegin()
const {
return Storage.rbegin(); }
133 const_reverse_iterator rend()
const {
return Storage.rend(); }
134 bool empty()
const {
return Storage.empty(); }
135 size_type size()
const {
return Storage.size(); }
136 size_type max_size()
const {
return Storage.max_size(); }
138 iterator lower_bound( const_key_type & k ) {
139 iterator __first = begin();
140 iterator __last = end();
142 difference_type __len = __last - __first;
143 difference_type __half;
150 if (KeyComp(*__middle, k)) {
153 __len = __len - __half - 1;
161 const_iterator lower_bound( const_key_type & k )
const {
162 const_iterator __first = begin();
163 const_iterator __last = end();
165 difference_type __len = __last - __first;
166 difference_type __half;
167 const_iterator __middle;
173 if (KeyComp(*__middle, k)) {
176 __len = __len - __half - 1;
184 iterator upper_bound( const_key_type & k ) {
185 iterator __first = begin();
186 iterator __last = end();
188 difference_type __len = __last - __first;
189 difference_type __half;
196 if (__comp(k, *__middle))
201 __len = __len - __half - 1;
208 const_iterator upper_bound( const_key_type & k )
const {
209 const_iterator __first = begin();
210 const_iterator __last = end();
212 difference_type __len = __last - __first;
213 difference_type __half;
214 const_iterator __middle;
220 if (__comp(k, *__middle))
225 __len = __len - __half - 1;
231 std::pair<iterator,bool>
insert(
const value_type & v ) {
232 typename storage::iterator ip = lower_bound(v);
234 const bool b = Storage.end() == ip || KeyComp( v , *ip );
236 if ( b ) ip = Storage.insert(ip,v);
237 return std::pair<iterator,bool>( ip, b );
240 void erase( iterator i ) {
241 Storage.erase( Storage.begin() + ( i - begin() ) );
244 void erase( iterator first , iterator last ) {
245 Storage.erase( Storage.begin() + ( first - begin() ) ,
246 Storage.begin() + ( last - begin() ) );
249 size_type erase( const_key_type & k ) {
250 typename storage::iterator i = lower_bound(k );
251 return KeyComp( k , *i ) ? 0 : ( Storage.erase(i) , 1 );
258 key_compare key_comp()
const {
return KeyComp ; }
259 value_compare value_comp()
const {
return KeyComp ; }
261 iterator
find( const_key_type & k ) {
262 const iterator i = lower_bound(k);
263 return end() == i || KeyComp( k , *i ) ? end() : i ;
266 const_iterator
find( const_key_type & k )
const {
267 const const_iterator i = lower_bound(k);
268 return end() == i || KeyComp( k , *i ) ? end() : i ;
271 size_type count( const_key_type & k )
const {
272 const const_iterator i = lower_bound(k);
273 return end() == i || KeyComp( k , *i ) ? 0 : 1 ;
279 operator const storage & ()
const {
283 void reserve( size_type n ) {
284 Storage.reserve( n );
288 return Storage == rhs.Storage ;
292 return Storage != rhs.Storage ;
298 #endif // STK_UTIL_UTIL_vecset_hpp
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
Vector-based std::set functionality.
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...