In this article….
- Introduction
- Compatibility
- What it does
- What it does NOT
- Background
- Motivation
- How to define the value, the key and, the
- container class and the cursor
- How to insert the values
- How to scan the entire set of values
- How to search for a key and scan the set of result values
- Source Code
- Test
- History
- Author
Figure 1: The sample project runs a set of tests to check source code correctness
Introduction
This article proposes my personal approach to the problem of storing and retrieving data in memory through the lmtl::SortKeyToMultiValueContainer
class template.
Don’t expect to find a replacement of STL, but a class template written to solve a special problem and that can be useful in building generic data structures.
I wrote some tests to check the software and it seems to work fine, but I dont’ take any responsibility: Use it at your own risk.
Compatibility
I compiled and tested the source code file html.h under both Microsoft Visual C++ 6.0 and Borland C++ Builder 5.0.
The source did not require any change.
What It Does
Here is a list of the functionalities of lmtl::SortKeyToMultiValueContainer
in version 1.0.
Description |
Stores data in memory (“by value” copy) |
Maintains data sorted by a user definable key, its operator<() and its operator==() |
Maintains a match between keys and multiple values |
Keeps the data structure efficient using a new internal balancing algorithm |
Reads ascendently the data stored |
Inserts data whenever needed |
Finds all the data matching a given key |
Reads ascendently the found data from start to end |
In case of equality between keys, keeps the insertion order in returning the results |
What It Does NOT Do
The following is obviously only a partial list. There would be too many the things that this class does not do to include them all.
Description | Comment |
It does not delete data | Deletion is not implemented yet, only the creation of the data structure, growing with insertion, ascending read, and find with ascending read. |
It does not read sequentially in reverse order (in descending order) | Bidirectional iteration is not yet implemented, only forward (ascending). |
Background
In C++, there are many data structures available, such as arrays, vectors, lists, binary trees, hash tables, maps, multimaps, and so on. Every data structure has its own advantages, disadvantages, and limitations.
Now, let’s talk about “multimap.” A multimap is a container that keeps the following in memory:
- a set of keys ki
- a set of values vi,j
- a set of links between the keys and the values
Figure 2: keys, values, and links in a multimap.
In a multimap, you can insert data pairs (k,v), scan the data sorted by key, delete the data, and retrieve a value v given its key k.
SortKeyToMultiValueContainer
is a template class very similar to a multimap.
With SortKeyToMultiValueContainer
, you can easily implement a lot of data structures because you can manage the “functional dependencies” that are links (or matches) between data. The concept of “functional dependency” is based the relational algebra and thus all the relational databases.
With SortKeyToMultiValueContainer
, you can read the values sequentially. If we assume that:
- k1 < k2
- k2 < k3
- the pair (k1,v1,2) was inserted after the pair (k1,v1,1)
- the pair (k3,v3,2) was inserted after the pair (k3,v3,1)
- the pair (k3,v3,3) was inserted after the pair (k3,v3,2)
then we can read the values sequentially:
- v1,1
- v1,2
- v2,1
- v3,1
- v3,2
- v3,3
To read sequentially, we use a cursor: SortKeyToMultiValueContainer::Cursor
. Cursors are also called iterators. With a cursor, we can read the entire set of values sequentially.
Figure 3: scanning the entire set of values
We can also make a search by a given key, retrieve the result, and scan it.
Figure 4: scanning the result of a search