SortKeyToMultiValueContainer C++ Container Template

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:

  1. a set of keys ki
  2. a set of values vi,j
  3. 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:

  1. k1 < k2
  2. k2 < k3
  3. the pair (k1,v1,2) was inserted after the pair (k1,v1,1)
  4. the pair (k3,v3,2) was inserted after the pair (k3,v3,1)
  5. the pair (k3,v3,3) was inserted after the pair (k3,v3,2)

then we can read the values sequentially:

  1. v1,1
  2. v1,2
  3. v2,1
  4. v3,1
  5. v3,2
  6. 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

More by Author

Must Read