NAME¶
FBB::LinearMap - A mapping container using linear searching
SYNOPSIS¶
#include <bobcat/linearmap>
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<Key, Value, Allocator>
TEMPLATE TYPES¶
The full template type definition of
LinearMap is:
template <
typename Key, typename Value,
typename Alloc = std::allocator< std::pair<Key const, Value> >
>
The
Key type must offer
bool operator==. Furthermore,
Key
and
Value types must support default and copy constructors and
overloaded (copy) assignment operators.
TYPEDEFS¶
- o
- typedef std::pair<Key, Value> value_type;
- 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<value_type> 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 and copy constructors 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.
- The copy assignment operator is available.
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<iterator, bool> 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<iterator, iterator> 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<iterator, bool> insert(value_type const
&keyValue):
tries to inserts a new value_type object into the LinearMap,
returning a std::pair<iterator, bool>. 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, Value and
Alloc 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 <iostream>
#include <string>
#include <iostream>
#include <bobcat/linearmap>
using namespace std;
using namespace FBB;
int main()
{
typedef LinearMap<string, string> 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)
BUGS¶
None Reported.
DISTRIBUTION FILES¶
- o
- bobcat_3.23.01-x.dsc: detached signature;
- o
- bobcat_3.23.01-x.tar.gz: source archive;
- o
- bobcat_3.23.01-x_i386.changes: change log;
- o
- libbobcat1_3.23.01-x_*.deb: debian package holding the
libraries;
- o
- libbobcat1-dev_3.23.01-x_*.deb: debian package holding the
libraries, headers and manual pages;
- o
- http://sourceforge.net/projects/bobcat: public archive location;
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).