FST  openfst-1.8.2
OpenFst Library
symbol-table.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Classes to provide symbol-to-integer and integer-to-symbol mappings.
19 
20 #ifndef FST_SYMBOL_TABLE_H_
21 #define FST_SYMBOL_TABLE_H_
22 
23 #include <cstdint>
24 #include <functional>
25 #include <ios>
26 #include <iostream>
27 #include <iterator>
28 #include <memory>
29 #include <sstream>
30 #include <string>
31 #include <type_traits>
32 #include <utility>
33 #include <vector>
34 
35 #include <fst/compat.h>
36 #include <fst/flags.h>
37 #include <fst/log.h>
38 #include <fstream>
39 #include <fst/windows_defs.inc>
40 #include <map>
41 #include <functional>
42 #include <string_view>
43 #include <fst/lock.h>
44 
45 DECLARE_bool(fst_compat_symbols);
46 
47 namespace fst {
48 
49 inline constexpr int64_t kNoSymbol = -1;
50 
51 class SymbolTable;
52 
54  explicit SymbolTableTextOptions(bool allow_negative_labels = false);
55 
57  std::string fst_field_separator;
58 };
59 
60 namespace internal {
61 
62 // Maximum line length in textual symbols file.
63 inline constexpr int kLineLen = 8096;
64 
65 // List of symbols with a dense hash for looking up symbol index, rehashing at
66 // 75% occupancy.
68  public:
70 
71  std::pair<int64_t, bool> InsertOrFind(std::string_view key);
72 
73  int64_t Find(std::string_view key) const;
74 
75  size_t Size() const { return symbols_.size(); }
76 
77  const std::string &GetSymbol(size_t idx) const { return symbols_[idx]; }
78 
79  void RemoveSymbol(size_t idx);
80 
81  void ShrinkToFit();
82 
83  private:
84  static constexpr int64_t kEmptyBucket = -1;
85 
86  // num_buckets must be power of 2.
87  void Rehash(size_t num_buckets);
88 
89  size_t GetHash(std::string_view key) const {
90  return str_hash_(key) & hash_mask_;
91  }
92 
93  const std::hash<std::string_view> str_hash_;
94  std::vector<std::string> symbols_;
95  std::vector<int64_t> buckets_;
96  uint64_t hash_mask_;
97 };
98 
99 // Base class for SymbolTable implementations.
100 // Use either MutableSymbolTableImpl or ConstSymbolTableImpl to derive
101 // implementation classes.
103  public:
104  SymbolTableImplBase() = default;
105  virtual ~SymbolTableImplBase() = default;
106 
107  // Enforce copying through Copy().
108  SymbolTableImplBase(const SymbolTableImplBase &) = delete;
109  SymbolTableImplBase &operator=(const SymbolTableImplBase &) = delete;
110 
111  virtual std::unique_ptr<SymbolTableImplBase> Copy() const = 0;
112 
113  virtual bool Write(std::ostream &strm) const = 0;
114 
115  virtual int64_t AddSymbol(std::string_view symbol, int64_t key) = 0;
116 
117  virtual int64_t AddSymbol(std::string_view symbol) = 0;
118 
119  // Removes the symbol with the specified key. Subsequent Find() calls
120  // for this key will return the empty string. Does not affect the keys
121  // of other symbols.
122  virtual void RemoveSymbol(int64_t key) = 0;
123 
124  // Returns the symbol for the specified key, or the empty string if not found.
125  virtual std::string Find(int64_t key) const = 0;
126 
127  // Returns the key for the specified symbol, or kNoSymbol if not found.
128  virtual int64_t Find(std::string_view symbol) const = 0;
129 
130  virtual bool Member(int64_t key) const { return !Find(key).empty(); }
131 
132  virtual bool Member(std::string_view symbol) const {
133  return Find(symbol) != kNoSymbol;
134  }
135 
136  virtual void AddTable(const SymbolTable &table) = 0;
137 
138  virtual int64_t GetNthKey(ssize_t pos) const = 0;
139 
140  virtual const std::string &Name() const = 0;
141 
142  virtual void SetName(std::string_view new_name) = 0;
143 
144  virtual const std::string &CheckSum() const = 0;
145 
146  virtual const std::string &LabeledCheckSum() const = 0;
147 
148  virtual int64_t AvailableKey() const = 0;
149 
150  virtual size_t NumSymbols() const = 0;
151 
152  virtual bool IsMutable() const = 0;
153 };
154 
155 // Base class for SymbolTable implementations supporting Add/Remove.
157  public:
158  void AddTable(const SymbolTable &table) override;
159  bool IsMutable() const final { return true; }
160 };
161 
162 // Base class for immutable SymbolTable implementations.
164  public:
165  std::unique_ptr<SymbolTableImplBase> Copy() const final;
166 
167  int64_t AddSymbol(std::string_view symbol, int64_t key) final;
168 
169  int64_t AddSymbol(std::string_view symbol) final;
170 
171  void RemoveSymbol(int64_t key) final;
172 
173  void SetName(std::string_view new_name) final;
174  void AddTable(const SymbolTable &table) final;
175 
176  bool IsMutable() const final { return false; }
177 };
178 
179 // Default SymbolTable implementation using DenseSymbolMap and std::map.
180 // Provides the common text and binary format serialization.
182  public:
183  explicit SymbolTableImpl(std::string_view name)
184  : name_(name),
185  available_key_(0),
186  dense_key_limit_(0),
187  check_sum_finalized_(false) {}
188 
190  : name_(impl.name_),
191  available_key_(impl.available_key_),
192  dense_key_limit_(impl.dense_key_limit_),
193  symbols_(impl.symbols_),
194  idx_key_(impl.idx_key_),
195  key_map_(impl.key_map_),
196  check_sum_finalized_(false) {}
197 
198  std::unique_ptr<SymbolTableImplBase> Copy() const override {
199  return std::make_unique<SymbolTableImpl>(*this);
200  }
201 
202  int64_t AddSymbol(std::string_view symbol, int64_t key) override;
203 
204  int64_t AddSymbol(std::string_view symbol) override {
205  return AddSymbol(symbol, available_key_);
206  }
207 
208  // Removes the symbol with the given key. The removal is costly
209  // (O(NumSymbols)) and may reduce the efficiency of Find() because of a
210  // potentially reduced size of the dense key interval.
211  void RemoveSymbol(int64_t key) override;
212 
213  static SymbolTableImpl *ReadText(
214  std::istream &strm, std::string_view name,
216 
217  // Reads a binary SymbolTable from stream, using source in error messages.
218  static SymbolTableImpl *Read(std::istream &strm, std::string_view source);
219 
220  bool Write(std::ostream &strm) const override;
221 
222  // Returns the string associated with the key. If the key is out of
223  // range (<0, >max), return an empty string.
224  std::string Find(int64_t key) const override;
225 
226  // Returns the key associated with the symbol; if the symbol
227  // does not exists, returns kNoSymbol.
228  int64_t Find(std::string_view symbol) const override {
229  int64_t idx = symbols_.Find(symbol);
230  if (idx == kNoSymbol || idx < dense_key_limit_) return idx;
231  return idx_key_[idx - dense_key_limit_];
232  }
233 
234  int64_t GetNthKey(ssize_t pos) const override {
235  if (pos < 0 || static_cast<size_t>(pos) >= symbols_.Size()) {
236  return kNoSymbol;
237  } else if (pos < dense_key_limit_) {
238  return pos;
239  }
240  return Find(symbols_.GetSymbol(pos));
241  }
242 
243  const std::string &Name() const override { return name_; }
244 
245  void SetName(std::string_view new_name) override {
246  name_ = std::string(new_name);
247  }
248 
249  const std::string &CheckSum() const override {
250  MaybeRecomputeCheckSum();
251  return check_sum_string_;
252  }
253 
254  const std::string &LabeledCheckSum() const override {
255  MaybeRecomputeCheckSum();
256  return labeled_check_sum_string_;
257  }
258 
259  int64_t AvailableKey() const override { return available_key_; }
260 
261  size_t NumSymbols() const override { return symbols_.Size(); }
262 
263  void ShrinkToFit();
264 
265  private:
266  // Recomputes the checksums (both of them) if we've had changes since the last
267  // computation (i.e., if check_sum_finalized_ is false).
268  // Takes ~2.5 microseconds (dbg) or ~230 nanoseconds (opt) on a 2.67GHz Xeon
269  // if the checksum is up-to-date (requiring no recomputation).
270  void MaybeRecomputeCheckSum() const;
271 
272  std::string name_;
273  int64_t available_key_;
274  int64_t dense_key_limit_;
275 
276  DenseSymbolMap symbols_;
277  // Maps index to key for index >= dense_key_limit:
278  // key = idx_key_[index - dense_key_limit]
279  std::vector<int64_t> idx_key_;
280  // Maps key to index for key >= dense_key_limit_.
281  // index = key_map_[key]
282  std::map<int64_t, int64_t> key_map_;
283 
284  mutable bool check_sum_finalized_;
285  mutable std::string check_sum_string_;
286  mutable std::string labeled_check_sum_string_;
287  mutable Mutex check_sum_mutex_;
288 };
289 
290 } // namespace internal
291 
292 // Symbol (string) to integer (and reverse) mapping.
293 //
294 // The SymbolTable implements the mappings of labels to strings and reverse.
295 // SymbolTables are used to describe the alphabet of the input and output
296 // labels for arcs in a Finite State Transducer.
297 //
298 // SymbolTables are reference-counted and can therefore be shared across
299 // multiple machines. For example a language model grammar G, with a
300 // SymbolTable for the words in the language model can share this symbol
301 // table with the lexical representation L o G.
302 class SymbolTable {
303  public:
304  class iterator {
305  public:
306  // TODO(wolfsonkin): Expand `SymbolTable::iterator` to be a random access
307  // iterator.
308  using iterator_category = std::input_iterator_tag;
309 
310  class value_type {
311  public:
312  // Return the label of the current symbol.
313  int64_t Label() const { return key_; }
314 
315  // Return the string of the current symbol.
316  // TODO(wolfsonkin): Consider adding caching.
317  std::string Symbol() const { return table_->Find(key_); }
318 
319  private:
320  explicit value_type(const SymbolTable &table, ssize_t pos)
321  : table_(&table), key_(table.GetNthKey(pos)) {}
322 
323  // Sets this item to the pos'th element in the symbol table
324  void SetPosition(ssize_t pos) { key_ = table_->GetNthKey(pos); }
325 
326  friend class SymbolTable::iterator;
327 
328  const SymbolTable *table_; // Does not own the underlying SymbolTable.
329  int64_t key_;
330  };
331 
332  using difference_type = std::ptrdiff_t;
333  using pointer = const value_type *const;
334  using reference = const value_type &;
335 
337  ++pos_;
338  if (static_cast<size_t>(pos_) < nsymbols_) iter_item_.SetPosition(pos_);
339  return *this;
340  }
341 
343  iterator retval = *this;
344  ++(*this);
345  return retval;
346  }
347 
348  bool operator==(const iterator &that) const { return (pos_ == that.pos_); }
349 
350  bool operator!=(const iterator &that) const { return !(*this == that); }
351 
352  reference operator*() { return iter_item_; }
353 
354  pointer operator->() const { return &iter_item_; }
355 
356  private:
357  explicit iterator(const SymbolTable &table, ssize_t pos = 0)
358  : pos_(pos), nsymbols_(table.NumSymbols()), iter_item_(table, pos) {}
359 
360  friend class SymbolTable;
361 
362  ssize_t pos_;
363  size_t nsymbols_;
364  value_type iter_item_;
365  };
366 
368 
369  // Constructs symbol table with an optional name.
370  explicit SymbolTable(std::string_view name = "<unspecified>")
371  : impl_(std::make_shared<internal::SymbolTableImpl>(name)) {}
372 
373  virtual ~SymbolTable() {}
374 
375  // Reads a text representation of the symbol table from an istream. Pass a
376  // name to give the resulting SymbolTable.
378  std::istream &strm, std::string_view name,
380  auto impl =
382  return impl ? new SymbolTable(std::move(impl)) : nullptr;
383  }
384 
385  // Reads a text representation of the symbol table.
386  static SymbolTable *ReadText(
387  const std::string &source,
389 
390  // Reads a binary dump of the symbol table from a stream.
391  static SymbolTable *Read(std::istream &strm, const std::string &source) {
392  auto impl = fst::WrapUnique(internal::SymbolTableImpl::Read(strm, source));
393  return impl ? new SymbolTable(std::move(impl)) : nullptr;
394  }
395 
396  // Reads a binary dump of the symbol table.
397  static SymbolTable *Read(const std::string &source) {
398  std::ifstream strm(source, std::ios_base::in | std::ios_base::binary);
399  if (!strm.good()) {
400  LOG(ERROR) << "SymbolTable::Read: Can't open file: " << source;
401  return nullptr;
402  }
403  return Read(strm, source);
404  }
405 
406  // Creates a reference counted copy.
407  virtual SymbolTable *Copy() const { return new SymbolTable(*this); }
408 
409  // Adds another symbol table to this table. All keys will be offset by the
410  // current available key (highest key in the symbol table). Note string
411  // symbols with the same key will still have the same key after the symbol
412  // table has been merged, but a different value. Adding symbol tables do not
413  // result in changes in the base table.
414  void AddTable(const SymbolTable &table) {
415  MutateCheck();
416  impl_->AddTable(table);
417  }
418 
419  // Adds a symbol with given key to table. A symbol table also keeps track of
420  // the last available key (highest key value in the symbol table).
421  int64_t AddSymbol(std::string_view symbol, int64_t key) {
422  MutateCheck();
423  return impl_->AddSymbol(symbol, key);
424  }
425 
426  // Adds a symbol to the table. The associated value key is automatically
427  // assigned by the symbol table.
428  int64_t AddSymbol(std::string_view symbol) {
429  MutateCheck();
430  return impl_->AddSymbol(symbol);
431  }
432 
433  // Returns the current available key (i.e., highest key + 1) in the symbol
434  // table.
435  int64_t AvailableKey() const { return impl_->AvailableKey(); }
436 
437  // Return the label-agnostic MD5 check-sum for this table. All new symbols
438  // added to the table will result in an updated checksum.
439  OPENFST_DEPRECATED("Use `LabeledCheckSum()` instead.")
440  const std::string &CheckSum() const { return impl_->CheckSum(); }
441 
442  int64_t GetNthKey(ssize_t pos) const { return impl_->GetNthKey(pos); }
443 
444  // Returns the string associated with the key; if the key is out of
445  // range (<0, >max), returns an empty string.
446  std::string Find(int64_t key) const { return impl_->Find(key); }
447 
448  // Returns the key associated with the symbol; if the symbol does not exist,
449  // kNoSymbol is returned.
450  int64_t Find(std::string_view symbol) const { return impl_->Find(symbol); }
451 
452  // Same as CheckSum(), but returns an label-dependent version.
453  const std::string &LabeledCheckSum() const {
454  return impl_->LabeledCheckSum();
455  }
456 
457  bool Member(int64_t key) const { return impl_->Member(key); }
458 
459  bool Member(std::string_view symbol) const { return impl_->Member(symbol); }
460 
461  // Returns the name of the symbol table.
462  const std::string &Name() const { return impl_->Name(); }
463 
464  // Returns the current number of symbols in table (not necessarily equal to
465  // AvailableKey()).
466  size_t NumSymbols() const { return impl_->NumSymbols(); }
467 
468  void RemoveSymbol(int64_t key) {
469  MutateCheck();
470  return impl_->RemoveSymbol(key);
471  }
472 
473  // Sets the name of the symbol table.
474  void SetName(std::string_view new_name) {
475  MutateCheck();
476  impl_->SetName(new_name);
477  }
478 
479  bool Write(std::ostream &strm) const { return impl_->Write(strm); }
480 
481  bool Write(const std::string &source) const;
482 
483  // Dumps a text representation of the symbol table via a stream.
484  bool WriteText(std::ostream &strm, const SymbolTableTextOptions &opts =
485  SymbolTableTextOptions()) const;
486 
487  // Dumps a text representation of the symbol table.
488  bool WriteText(const std::string &source) const;
489 
490  const_iterator begin() const { return const_iterator(*this, 0); }
491 
492  const_iterator end() const { return const_iterator(*this, NumSymbols()); }
493 
494  const_iterator cbegin() const { return begin(); }
495 
496  const_iterator cend() const { return end(); }
497 
498  protected:
499  explicit SymbolTable(std::shared_ptr<internal::SymbolTableImplBase> impl)
500  : impl_(std::move(impl)) {}
501 
502  template <class T = internal::SymbolTableImplBase>
503  const T *Impl() const {
504  return down_cast<const T *>(impl_.get());
505  }
506 
507  template <class T = internal::SymbolTableImplBase>
508  T *MutableImpl() {
509  MutateCheck();
510  return down_cast<T *>(impl_.get());
511  }
512 
513  private:
514  void MutateCheck() {
515  if (impl_.unique() || !impl_->IsMutable()) return;
516  std::unique_ptr<internal::SymbolTableImplBase> copy = impl_->Copy();
517  CHECK(copy != nullptr);
518  impl_ = std::move(copy);
519  }
520 
521  std::shared_ptr<internal::SymbolTableImplBase> impl_;
522 };
523 
524 // Iterator class for symbols in a symbol table.
526  "Use SymbolTable::iterator, a C++ compliant iterator, instead")
527  SymbolTableIterator {
528  public:
529  explicit SymbolTableIterator(const SymbolTable &table)
530  : table_(table), iter_(table.begin()), end_(table.end()) {}
531 
532  ~SymbolTableIterator() {}
533 
534  // Returns whether iterator is done.
535  bool Done() const { return (iter_ == end_); }
536 
537  // Return the key of the current symbol.
538  int64_t Value() const { return iter_->Label(); }
539 
540  // Return the string of the current symbol.
541  std::string Symbol() const { return iter_->Symbol(); }
542 
543  // Advances iterator.
544  void Next() { ++iter_; }
545 
546  // Resets iterator.
547  void Reset() { iter_ = table_.begin(); }
548 
549  private:
550  const SymbolTable &table_;
551  SymbolTable::iterator iter_;
552  const SymbolTable::iterator end_;
553 };
554 
555 // Relabels a symbol table as specified by the input vector of pairs
556 // (old label, new label). The new symbol table only retains symbols
557 // for which a relabeling is explicitly specified.
558 //
559 // TODO(allauzen): consider adding options to allow for some form of implicit
560 // identity relabeling.
561 template <class Label>
563  const SymbolTable *table,
564  const std::vector<std::pair<Label, Label>> &pairs) {
565  auto *new_table = new SymbolTable(
566  table->Name().empty() ? std::string()
567  : (std::string("relabeled_") + table->Name()));
568  for (const auto &[old_label, new_label] : pairs) {
569  new_table->AddSymbol(table->Find(old_label), new_label);
570  }
571  return new_table;
572 }
573 
574 // Returns true if the two symbol tables have equal checksums. Passing in
575 // nullptr for either table always returns true.
576 bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2,
577  bool warning = true);
578 
579 // Symbol table serialization.
580 
581 void SymbolTableToString(const SymbolTable *table, std::string *result);
582 
583 SymbolTable *StringToSymbolTable(const std::string &str);
584 
585 } // namespace fst
586 
587 #endif // FST_SYMBOL_TABLE_H_
const std::string & Name() const
Definition: symbol-table.h:462
bool Write(std::ostream &strm) const
Definition: symbol-table.h:479
int64_t AddSymbol(std::string_view symbol, int64_t key)
Definition: symbol-table.h:421
void SymbolTableToString(const SymbolTable *table, std::string *result)
void SetName(std::string_view new_name) override
Definition: symbol-table.h:245
void AddTable(const SymbolTable &table)
Definition: symbol-table.h:414
virtual bool Member(std::string_view symbol) const
Definition: symbol-table.h:132
const_iterator end() const
Definition: symbol-table.h:492
pointer operator->() const
Definition: symbol-table.h:354
static SymbolTableImpl * Read(std::istream &strm, std::string_view source)
const_iterator cbegin() const
Definition: symbol-table.h:494
SymbolTable(std::string_view name="<unspecified>")
Definition: symbol-table.h:370
virtual SymbolTable * Copy() const
Definition: symbol-table.h:407
void SetName(std::string_view new_name)
Definition: symbol-table.h:474
std::input_iterator_tag iterator_category
Definition: symbol-table.h:308
#define LOG(type)
Definition: log.h:49
SymbolTable * StringToSymbolTable(const std::string &str)
constexpr int kLineLen
Definition: symbol-table.h:63
int64_t AddSymbol(std::string_view symbol) override
Definition: symbol-table.h:204
To down_cast(From *f)
Definition: compat.h:50
std::unique_ptr< T > WrapUnique(T *ptr)
Definition: compat.h:125
constexpr int64_t kNoSymbol
Definition: symbol-table.h:49
const std::string & GetSymbol(size_t idx) const
Definition: symbol-table.h:77
size_t NumSymbols() const
Definition: symbol-table.h:466
SymbolTableImpl(const SymbolTableImpl &impl)
Definition: symbol-table.h:189
static SymbolTable * ReadText(std::istream &strm, std::string_view name, const SymbolTableTextOptions &opts=SymbolTableTextOptions())
Definition: symbol-table.h:377
bool operator==(const iterator &that) const
Definition: symbol-table.h:348
std::ptrdiff_t difference_type
Definition: symbol-table.h:332
void RemoveSymbol(int64_t key)
Definition: symbol-table.h:468
const value_type *const pointer
Definition: symbol-table.h:333
SymbolTableTextOptions(bool allow_negative_labels=false)
Definition: symbol-table.cc:39
size_t NumSymbols() const override
Definition: symbol-table.h:261
int64_t GetNthKey(ssize_t pos) const override
Definition: symbol-table.h:234
static SymbolTable * Read(std::istream &strm, const std::string &source)
Definition: symbol-table.h:391
SymbolTable(std::shared_ptr< internal::SymbolTableImplBase > impl)
Definition: symbol-table.h:499
bool operator!=(const iterator &that) const
Definition: symbol-table.h:350
const T * Impl() const
Definition: symbol-table.h:503
int64_t AddSymbol(std::string_view symbol)
Definition: symbol-table.h:428
int64_t Find(std::string_view symbol) const override
Definition: symbol-table.h:228
static SymbolTableImpl * ReadText(std::istream &strm, std::string_view name, const SymbolTableTextOptions &opts=SymbolTableTextOptions())
const std::string & LabeledCheckSum() const override
Definition: symbol-table.h:254
const std::string & Name() const override
Definition: symbol-table.h:243
int64_t AvailableKey() const
Definition: symbol-table.h:435
int64_t AvailableKey() const override
Definition: symbol-table.h:259
virtual ~SymbolTable()
Definition: symbol-table.h:373
virtual bool Member(int64_t key) const
Definition: symbol-table.h:130
DECLARE_bool(fst_compat_symbols)
bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
std::string Find(int64_t key) const
Definition: symbol-table.h:446
class OPENFST_DEPRECATED("Use SymbolTable::iterator, a C++ compliant iterator, instead") SymbolTableIterator
Definition: symbol-table.h:525
const std::string & LabeledCheckSum() const
Definition: symbol-table.h:453
const_iterator begin() const
Definition: symbol-table.h:490
#define CHECK(x)
Definition: log.h:61
std::unique_ptr< SymbolTableImplBase > Copy() const override
Definition: symbol-table.h:198
int64_t GetNthKey(ssize_t pos) const
Definition: symbol-table.h:442
static SymbolTable * Read(const std::string &source)
Definition: symbol-table.h:397
const std::string & CheckSum() const override
Definition: symbol-table.h:249
SymbolTable * RelabelSymbolTable(const SymbolTable *table, const std::vector< std::pair< Label, Label >> &pairs)
Definition: symbol-table.h:562
SymbolTableImpl(std::string_view name)
Definition: symbol-table.h:183
bool Member(std::string_view symbol) const
Definition: symbol-table.h:459
bool Member(int64_t key) const
Definition: symbol-table.h:457
int64_t Find(std::string_view symbol) const
Definition: symbol-table.h:450
const_iterator cend() const
Definition: symbol-table.h:496