--- name: "linearmap" section: "3bobcat" platform: "linux" package: "libbobcat-dev" version: "6.07.01-2" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/linearmap" --- # linearmap(3bobcat) A mapping container using linear searching ## NAME FBB::LinearMap - A mapping container using linear searching ## SYNOPSIS **#include \**\ ## DESCRIPTION The class template **LinearMap** implements a mapping container using a linear searching algorithm. A mapping container using linear searching is less complex than either the sorted *std::map* or the unsorted *std::unordered\_map* container. For relative small number of elements the linear search algorithm is also faster than the binary search or hashing-based searching algorithms. **LinearMap** implements all of the members which are also found in the standard *std::map*, except for the *key\_comp* and *value\_comp* members. These latter two members are not available as ordering the keys is not an issue with the unordered, linear searching method which is used by **LinearMap**. ## NAMESPACE **FBB**\ All constructors, members, operators and manipulators, mentioned in this man-page, are defined in the namespace **FBB**. ## INHERITS (PRIVATELY) FROM *std::vector\* ## TEMPLATE TYPES The full template type definition of **LinearMap** is: ``` template < typename Key, typename Value > ``` The *Key* type must offer *bool operator==*. Furthermore, *Key* and *Value* types must support default and copy constructors and overloaded (copy) assignment operators. ## USING SPECIFICATIONS - o *using value\_type = std::pair\*; - o *iterator* - an iterator to a **LinearMap** object’s elements; - o *const\_iterator* - a *const\_iterator* to a **LinearMap** object’s elements; - o *reverse\_iterator* - a *reverse\_iterator* to a **LinearMap** object’s elements; - o *const\_reverse\_iterator* - a *const\_reverse\_iterator* to a **LinearMap** object’s elements. ## CONSTRUCTORS - o **LinearMap(Iterator begin, Iterator end)**:\ The constructor is initialized using the iterator range *\[begin,* *end)*, where *Iterator* is any iterator type pointing to *value\_type* objects. If identical keys *K* are used then only the first occurrence of the *value\_type* object using key *K* is inserted. - - o **LinearMap(std:initializer\_list\ initial)**:\ The constructor is initialized with the values stored in the *std::initializer\_list* of *value\_type* objects. If identical keys *K* are used then only the first occurrence of the *value\_type* object using key *K* is inserted. Default, copy and move constructors (and copy and move assignment operators) are available. ## OVERLOADED OPERATORS - o **Value &operator\[\](Key const &key)**:\ A reference to the *Value* associated with *key* is returned. If *key* was not available prior to the call of the index operator a *value\_map(key, Value()) object is inserted.* - ## MEMBER FUNCTIONS Note that the members of *std::vector* are not automatically available, as **LinearMap** is privately inherited from *std::vector*. - **LinearMap** offers the following member functions: - o **Value &at(int idx)**:\ returns a reference to the **LinearMap**’s *Value* that is associated with *key*. If the *key* is not stored in the **LinearMap** then an **std::out\_of\_range** exception is thrown. - - o **iterator begin()**:\ returns an iterator pointing to the **LinearMap**’s first element. - - o **size\_t capacity()**:\ returns the number of elements that can be stored in the **LinearMap** before its capacity is enlarged. - - o **const\_iterator cbegin() const**:\ returns a *const\_iterator* pointing to the **LinearMap**’s first element. - - o **const\_iterator cend() const**:\ returns a *const\_iterator* pointing beyond the **LinearMap**’s last element. - - o **void clear()**:\ erases all elements from the **LinearMap**. - - o **size\_t count(key)**:\ returns 1 if the provided key is available in the **LinearMap**, otherwise 0 is returned. - - o **const\_reverse\_iterator crbegin() const**:\ returns a *const\_reverse\_iterator* pointing to a **LinearMap** object’s last element. - - o **const\_reverse\_iterator crend() const**:\ returns a *const\_reverse\_iterator* pointing before a **LinearMap** object’s first element. - - o **std::pair\ emplace(Args &&...args)**:\ a *value\_type* object is constructed from *emplace*’s arguments. A *std::pair* is returned containing an iterator pointing to the object using that key. If the **LinearMap** already contains an object having the provided *Key* value then the returned *std::pair’s bool* value is *false*. If the provided *key* was not found, then the newly constructed object is inserted into the **LinearMap**, and the returned *std::pair’s bool* value is *true*. - - o **bool empty()**:\ returns *true* if the **LinearMap** contains no elements. - - o **iterator end()**:\ returns an iterator pointing beyond the **LinearMap**’s last element. - - o **std::pair\ equal\_range(key)**:\ returns a pair of iterators, being respectively the return values of the member functions *lower\_bound* and *upper\_bound*. - - o **bool erase(Key const &key)**:\ erases the element having the given *key* from the **LinearMap**. *True* is returned if the value was removed, *false* if the **LinearMap** did not contain an element using the given *key*. - - o **void erase(iterator pos)**:\ erases the element at iterator position *pos*. - - o **void erase(iterator begin, iterator end)**:\ erases all elements indicated by the iterator range *\[first,* *beyond)*. - - o **iterator find(Key const &key)**:\ returns an iterator to the element having the given key. If the element isn’t available, *end* is returned. - - o **const\_iterator find(Key const &key) const**:\ returns a *const\_iterator* to the element having the given key. If the element isn’t available, *end* is returned. - - o **allocator\_type get\_allocator() const**:\ returns a copy of the allocator object used by the **LinearMap** **object.** - - o **std::pair\ insert(value\_type const &keyValue):**\ **tries to inserts a new** *value\_type* **object into the LinearMap,** **returning a** *std::pair\***. If the returned ti(bool)** **field is** *true***,** *keyValue* **was inserted into the LinearMap. The** **value** *false* **indicates that the specified key was already available,** **and** *keyvalue* **was not inserted into the LinearMap. In both** **cases the** *iterator* **field points to the data element having the** **specified** *key***.** - - o **iterator insert(iterator pos, value\_type const &keyValue):**\ **tries to insert** *keyValue* **into the LinearMap.** *Pos* **is ignored,** **and an iterator to the element having** *keyValue***’s key value is** **returned. If the specified key was already present,** *keyValue* **is not** **inserted into the LinearMap.** - - o **void insert(Iterator begin, Iterator end):**\ **tries to insert the** *value\_type* **elements pointed at by the iterator** **range** *\[begin, end)* **objects into the LinearMap.** *Iterator* **is any iterator type pointing to** *value\_type* **objects. Already existing** *value\_type* **elements having keys equal to the keys of the elements** **pointed at by the iterator range are not replaced.** - - o **iterator lower\_bound(Key const &key):**\ **returns an iterator pointing to the** *keyvalue* **element having the** **specified** *key***. If no such element exists,** *end* **is returned.** - - o **const\_iterator lower\_bound(Key const &key) const:**\ **returns a** *const\_iterator* **pointing to the** *keyvalue* **element having** **the specified** *key***. If no such element exists,** *end* **is returned.** - - o **size\_t max\_size() const:**\ **returns the maximum number of elements this LinearMap may** **contain.** - - o **reverse\_iterator rbegin():**\ **returns a** *reverse\_iterator* **pointing to the LinearMap object’s last** **element.** - - o **const\_reverse\_iterator rbegin() const:**\ **returns a** *const\_reverse\_iterator* **pointing to the LinearMap** **object’s last element.** - - o **reverse\_iterator rend():**\ **returns a** *reverse\_iterator* **pointing before the LinearMap object’s** **first element.** - - o **const\_reverse\_iterator rbegin() const:**\ **returns a** *const\_reverse\_iterator* **pointing before the LinearMap** **object’s first element.** - - o **size\_t size() const:**\ **returns the number of elements in the LinearMap.** - - o **void swap(LinearMap &other):**\ **swaps two LinearMaps using identical** *Key* **and** *Value* **types.** - - o **iterator upper\_bound(Key const &key):**\ **returns an iterator pointing to the** *keyvalue* **element having the** **specified** *key***. If no such element exists,** *end* **is returned.** - - o **const\_iterator upper\_bound(Key const &key) const:**\ **returns a** *const\_iterator* **pointing to the** *keyvalue* **element having** **the specified** *key***. If no such element exists,** *end* **is returned.** ## EXAMPLE ``` #include #include #include #include using namespace std; using namespace FBB; int main() { typedef LinearMap LM; // constructors: LM lm; LM lm2 = { {"one", "value 1"}, {"two", "value 2"} }; LM lm3(lm2); LM lm4(lm3.begin(), lm3.end()); // assignment: lm = lm2; // some members: lm["key"] = "value"; cout << lm["key"] << ’\n’; cout << lm.find("key")->second << ’\n’; for (auto value: lm) cout << "For loop: " << value.first << ", " << value.second << ’\n’; cerr << "# times ’key’ is stored: " << lm.count("key") << "\n" "# times ’value is stored: " << lm.count("value") << ’\n’; lm4 = lm2; cout << "lm4’s size after assignment: " << lm4.size() << ’\n’; lm4.clear(); cout << "lm4’s size after clear: " << lm4.size() << ’\n’; }; ``` ## FILES *bobcat/linearmap* **- defines the class interface** ## SEE ALSO **[bobcat(7)](/bobcat/7.md)** ## BUGS **None Reported.** ## BOBCAT PROJECT FILES - o *https://fbb-git.gitlab.io/bobcat/***: gitlab project page;** **Debian Bobcat project files:** - o *libbobcat6***: debian package containing the shared library, changelog** **and copyright note;** - o *libbobcat-dev***: debian package containing the** **static library, headers, manual pages, and developer info;** ## BOBCAT **Bobcat is an acronym of \`Brokken’s Own Base Classes And Templates’.** ## COPYRIGHT **This is free software, distributed under the terms of the** **GNU General Public License (GPL).** ## AUTHOR **Frank B. Brokken (f.b.brokken@rug.nl).**