|
w w w . a q u a m e n t u s . c o m |
laps and lashes are ordered (like std::list), associative
(like std::map) data structures. They have the same behavior
and API, but differ in implementation; laps are
implemented as a tree (like std::map, giving logarithmic time for insert,
query, and removal), whereas lashes are implemented as a
hash (giving (amortized) constant time for insert, query, and removal).
Why create the lap? Because it fills a niche not covered by any
one STL class. std::list is not associative, so you cannot perform a key-value
lookup. std::map is not ordered, so you cannot retrieve objects from it in the
order that you added them. laps bridge that gap.
laps and lashes have iterator
subclasses, so you can use them just like any STL
class. In particular, they can be used with STL algorithms such as
find and remove (though they have their own
member functions for both of those functions).
The hashing algorithm used by lash is specific to text strings, and
is something I found on the internet. If you use anything other than
std::string as the key value, you will want to define your own
hash function for that type. It's structured as a template specialization,
which sounded like a good idea at the time but I haven't tried to pretend to
be a general user and define my own function to see if it actually works. Enjoy! :)
Templates being templates, all the code is in a single .h file. STL being STL, there probably should not be a .h in the actual file name.
Note that I put these in namespace std just to align with STL.
| tree-based implementation: | lap.h |
| hash-based implementation: | lash.h |
| returns | method | description |
methods common to both lap and lash | ||
| long | size() | Returns the number of elements |
| bool | empty() | Returns whether it is empty |
| void | push_front(T key, U value) | Adds a new data item to the front |
| void | push_back(T key, U value) | Adds a new data item to the back |
| pop_front() | Removes and returns the item from the front | |
| std::pair<T, U> | pop_back() | Removes and returns the item from the back |
| std::pair<T, U> | peek_front() | Returns (but does not remove) the item at the front |
| std::pair<T, U> | peek_back() | Returns (but does not remove) the item at the back |
| iterator | begin() | Returns an iterator pointing to the front (first element) |
| iterator | end() | Returns an iterator pointing past the end (last element) |
| iterator | rbegin() | Returns an iterator pointing to the end (last element) |
| iterator | rend() | Returns an iterator pointing past the front (first element) |
| iterator | find(T key) | If key exists, returns the iterator pointing to it; otherwise, returns end() |
| void | insert(iterator it, T key, U data) | Adds a new data item before it |
| iterator | erase(iterator it) | Removes an element. Returns an iterator pointing to the next element. |
| iterator | clear() | Clears out all contained data and resets the datastructure. |
methods common to lap::iterator
and lash::iterator | ||
| void | operator++() | "Increments" the iterator to the next element, where "increment" means going front-to-back for forward iterators and back-to-front for reverse iterators. This is the pre-increment operator. |
| void | operator--() | "Decrements" the iterator to the previous element, where "decrement" means going back-to-front for forward iterators and front-to-back for reverse iterators. This is the pre-increment operator. |
| T | first() | Dereferences the iterator to get the key |
| U | second() | Dereferences the iterator to get the value |
| bool | Returns if two iterators are the same | |
| bool | operator!=(const iterator &rhs) | Returns if two iterators are not the same |
| interator& | operator=(const iterator &rhs) | Assigns one iterator to point to the same place another does. |
methods specific to lap | ||
| lap() | Default constructor | |
| lap(const lap &) | Copy constructor. Makes laps safe for passing around as
function parameters, but the internal objects are only owned by the original
lap instance. As such, don't try to modify any copies. |
|
| lap& | operator=(const lap &) | Assignment operator. Same as for the copy constructor, the assignment
operator makes it possible to assign lap objects; however,
ownership of the internal data stays with the original object, so don't
try to modify any assigned objects. |
methods specific to lash | ||
| lash() | Default constructor | |
| lash(const lash &) | Copy constructor. Makes lashes safe for passing around as
function parameters, but the internal objects are only owned by the original
lash instance. As such, don't try to modify any copies. |
|
| lash& | operator=(const lash &) | Assignment operator. Same as for the copy constructor, the assignment
operator makes it possible to assign lash objects; however,
ownership of the internal data stays with the original object, so don't
try to modify any assigned objects. |
| void | reserve(int new_capacity) | Expands the capacity of the hash table to hold new_capacity items.
If you know how many items you'll be adding, reserving avoids resizing. |
| friend functions | ||
| ostream& | operator<<(ostream&, lap&) | Overloaded for easy printing. It iterates through a lap
from front to back and prints out every key-value pair, once per line. |
| ostream& | operator<<(ostream&, lash&) | Overloaded for easy printing. It iterates through a lash
from front to back and prints out every key-value pair, once per line. |
#include <iostream>
#include <lap>
using namespace std;
int main(int, char**) {
lap<string, int> foo;
foo.push_back("ab", 3);
foo.push_back("cd", 4);
foo.push_front("ef", 2);
foo.push_front("gh", 1);
cout << "initial size: " << foo.size() << endl;
foo.erase(foo.find("cd"));
cout << "size after erasing: " << foo.size() << endl;
foo.insert(foo.find("ef"), "ij", 42);
cout << "size after inserting: " << foo.size() << endl;
cout << "In order:" << endl;
for (lap<string, int>::iterator it = foo.begin();
it != foo.end();
++it) {
cout << it->first << " -> " << it->second << endl;
}
// play around with associated data:
foo.find("ab")->second = 1234;
foo.find("gh")->second = 2345;
foo.push_front("kl", 234);
foo.insert(foo.find("kl"), "mn", 89);
cout << "After messing with it:" << endl;
for (lap<string, int>::iterator it = foo.begin();
it != foo.end();
++it) {
cout << it->first << " -> " << it->second << endl;
}
foo.clear();
cout << "After clearing: " << endl;
cout << foo;
}