/usr/include/ace/Array_Map.h is in libace-dev 6.2.8+dfsg-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 | // -*- C++ -*-
//=============================================================================
/**
* @file Array_Map.h
*
* $Id: Array_Map.h 97262 2013-08-09 08:32:10Z johnnyw $
*
* Light weight array-based map with fast iteration but linear
* (i.e. O(n)) search times. STL-style interface is exposed.
*
* @note This class requires the STL generic algorithms and
* reverse_iterator adapter.
*
* @author Ossama Othman
*/
//=============================================================================
#ifndef ACE_ARRAY_MAP_H
#define ACE_ARRAY_MAP_H
#include /**/ "ace/pre.h"
#include /**/ "ace/config-lite.h"
#if !defined (ACE_LACKS_PRAGMA_ONCE)
# pragma once
#endif /* ACE_LACKS_PRAGMA_ONCE */
#include <utility>
#include <iterator>
#include <functional>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL
/**
* @class ACE_Array_Map
*
* @brief Light weight array-based map with fast iteration, but linear
* (i.e. O(n)) search times.
*
* Map implementation that focuses on small footprint and fast
* iteration. Search times are, however, linear (O(n)) meaning that
* this map isn't suitable for large data sets that will be searched
* in performance critical areas of code. Iteration over large data
* sets, however, is faster than linked list-based maps, for example,
* since spatial locality is maximized through the use of contiguous
* arrays as the underlying storage.
* @par
* An @c ACE_Array_Map is a unique associative container, meaning that
* duplicate values may not be added to the map. It is also pair
* associative (value_type is a std::pair<>). It is not a sorted
* container.
* @par
* An STL @c std::map -like interface is exposed by this class
* portability. Furthermore, this map's iterators are compatible with
* STL algorithms.
* @par
* <b> Requirements and Performance Characteristics</b>
* - Internal Structure
* Array
* - Duplicates allowed?
* No
* - Random access allowed?
* Yes
* - Search speed
* O(n)
* - Insert/replace speed
* O(n), can be longer if the map has to resize
* - Iterator still valid after change to container?
* No
* - Frees memory for removed elements?
* Yes
* - Items inserted by
* Value
* - Requirements for key type
* -# Default constructor
* -# Copy constructor
* -# operator=
* -# operator==
* - Requirements for object type
* -# Default constructor
* -# Copy constructor
* -# operator=
*/
template<typename Key, typename Value, class EqualTo = std::equal_to<Key> >
class ACE_Array_Map
{
public:
// STL-style typedefs/traits.
typedef Key key_type;
typedef Value data_type;
typedef std::pair<key_type, data_type> value_type;
typedef value_type * iterator;
typedef value_type const * const_iterator;
typedef value_type & reference;
typedef value_type const & const_reference;
typedef value_type * pointer;
typedef value_type const * const_pointer;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
ACE_DECLARE_STL_REVERSE_ITERATORS
/// Default Constructor.
/**
* Create an empty map with a preallocated buffer of size @a s.
*/
ACE_Array_Map (size_type s = 0);
template<typename InputIterator>
ACE_Array_Map (InputIterator f, InputIterator l);
ACE_Array_Map (ACE_Array_Map const & map);
ACE_Array_Map & operator= (ACE_Array_Map const & map);
/// Destructor.
~ACE_Array_Map (void);
/**
* @name Forward Iterator Accessors
*
* Forward iterator accessors.
*/
//@{
iterator begin (void);
iterator end (void);
const_iterator begin (void) const;
const_iterator end (void) const;
//@}
/**
* @name Reverse Iterator Accessors
*
* Reverse iterator accessors.
*/
//@{
reverse_iterator rbegin (void);
reverse_iterator rend (void);
const_reverse_iterator rbegin (void) const;
const_reverse_iterator rend (void) const;
//@}
/// Return current size of map.
/**
* @return The number of elements in the map.
*/
size_type size (void) const;
/// Maximum number of elements the map can hold.
size_type max_size (void) const;
/// Return @c true if the map is empty, else @c false.
bool is_empty (void) const; // ACE style
/**
* Return @c true if the map is empty, else @c false. We recommend
* using @c is_empty() instead since it's more consistent with the
* ACE container naming conventions.
*/
bool empty (void) const; // STL style
/// Swap the contents of this map with the given @a map in an
/// exception-safe manner.
void swap (ACE_Array_Map & map);
/// Insert the value @a x into the map.
/**
* STL-style map insertion method.
*
* @param x @c std::pair containing key and datum.
*
* @return @c std::pair::second will be @c false if the map already
* contains a value with the same key as @a x.
*/
std::pair<iterator, bool> insert (value_type const & x);
/// Insert range of elements into map.
template<typename InputIterator>
void insert (InputIterator f, InputIterator l);
/// Remove element at position @a pos from the map.
void erase (iterator pos);
/// Remove element corresponding to key @a k from the map.
/**
* @return Number of elements that were erased.
*/
size_type erase (key_type const & k);
/// Remove range of elements [@a first, @a last) from the map.
/**
* @note [@a first, @a last) must be valid range within the map.
*/
void erase (iterator first, iterator last);
/// Clear contents of map.
/**
* @note This a constant time (O(1)) operation.
*/
void clear (void);
/**
* @name Search Operations
*
* Search the map for data corresponding to key @a k.
*/
//@{
/**
* @return @c end() if data corresponding to key @a k is not in the
* map.
*/
iterator find (key_type const & k);
/**
* @return @c end() if data corresponding to key @a k is not in the
* map.
*/
const_iterator find (key_type const & k) const;
//@}
/// Count the number of elements corresponding to key @a k.
/**
* @return In the case of this map, the count will always be one if
* such exists in the map.
*/
size_type count (key_type const & k);
/// Convenience array index operator.
/**
* Array index operator that allows insertion and retrieval of
* elements using an array index syntax, such as:
* @par
* map["Foo"] = 12;
*/
data_type & operator[] (key_type const & k);
private:
/// Increase size of underlying buffer by @a s.
void grow (size_type s);
private:
/// Number of elements in the map.
size_type size_;
/// Current size of underlying array.
/**
* @note @c capacity_ is always greater than or equal to @c size_;
*/
size_type capacity_;
/// Underlying array containing keys and data.
value_type * nodes_;
};
// --------------------------------------------------------------
/// @c ACE_Array_Map equality operator.
template <typename Key, typename Value, class EqualTo>
bool operator== (ACE_Array_Map<Key, Value, EqualTo> const & lhs,
ACE_Array_Map<Key, Value, EqualTo> const & rhs);
/// @c ACE_Array_Map lexicographical comparison operator.
template <typename Key, typename Value, class EqualTo>
bool operator< (ACE_Array_Map<Key, Value, EqualTo> const & lhs,
ACE_Array_Map<Key, Value, EqualTo> const & rhs);
// --------------------------------------------------------------
ACE_END_VERSIONED_NAMESPACE_DECL
#ifdef __ACE_INLINE__
# include "ace/Array_Map.inl"
#endif /* __ACE_INLINE__ */
#if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
# include "ace/Array_Map.cpp"
#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
#pragma implementation ("Array_Map.cpp")
#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
#include /**/ "ace/post.h"
#endif /* ACE_ARRAY_MAP_H */
|