Dictionary – Entry Use Counts

Mentioned in the last post, the use count vector member was removed and a use count was put into the value of the map.  A new private Entry Value structure was created to hold the index and the use count of the entry.  Both were defined as unsigned 16-bit integers.  A constructor was added taking a single index argument and the use count is initialized to 1.

For the add function, the entry in the use count vector no longer needs to be added or initialized (in the case of a reused entry).  Instead of assigning a key to an index using the bracket operator, the map emplace function is used with a single index.  The use count get set to 1 whether it is a new or a reused entry by the constructor of the Entry Value structure.  For an existing entry, the iterator is used to increment the use count.

For the remove function, since the use count is no longer available by index, the index is used to get the key from the key list member.  The key is converted to upper case for case insensitive dictionaries and used to find an iterator for the key.  While the index is available in the iterator, it is used to clear the entry in the key list and pushed to the free stack.  The iterator is used to erase the entry from the key map (entries can be erased either by key value or iterator).

For the debug text function, since the use count is no longer available by index, a non-empty entry in the key list is used to identify if an entry is used.  The key is used to find an iterator to the entry.  An error check was added if the key was not found (shouldn't happen).  The iterator is used to get the use count.  When outputting the indexes of the free stack, the check for a non-zero use count was removed since the use count is no longer available (the entry in the map with the use count was erased, and an entry is not pushed to the free stack unless the use count was zero).

[branch stl commit e79c179ad5]

Dictionary – Case Sensitive Member

The next changes for the Dictionary class are some improvements in its implementation.  One of these changes is to integrate the use count into the value of the key map instead of using a separate vector for the use counts of each entry.  Putting the use count into the key map value will require the use of iterators to get to the use count since they will no longer be in an indexed vector.

The debug text function (which will be changed to a put stream operator function) will need to use an iterator to look up a key to get the use count.  When using iterators, the debug text function will also need to convert the key to upper case for case sensitive dictionaries, which implies that it would also need a case sensitive flag argument like the add and remove function.

This made me realize that passing a case sensitive flag to all of these functions was not the best design.  A better design is to have a case sensitive flag as a member variable initialized once when the dictionary is constructed.  Using arguments allows different case sensitivities on a dictionary and this will cause problems.  A case sensitive member was added, the constructors were added or modified, and the case sensitive arguments were removed.

[branch stl commit b78217c5a4]

Dictionary – Key Map

The remaining member of the Dictionary class to change to a standard class is the key hash, which was defined as a QHash.  This class is equivalent to the std::unordered_map, which also stores keys using a hash.  The member was renamed to key map and a Key Map alias was added since the the map type is rather lengthy:

using KeyMap = std::unordered_map<std::string, int>;

The add routine, was changed to use the key as a standard string.  The standard string class does not have a member function for converting the string to upper case.  For case insensitive dictionaries, the string is converted to upper case using the standard transform function:

std::transform(key.begin(), key.end(), key.begin(), toupper);

The first two arguments specify the range of the string to transform (the entire string).  The third argument specifies the destination (back into the string).  The last argument is function that takes and returns a character.  To find a key value in the map, the map find function is used, which returns an iterator.  A key not found is detected if the iterator is the end iterator of the map.  The value in the map (the index of the entry) is obtained using the iterator:

auto iterator = m_keyMap.find(key);
if (iterator == m_keyMap.end())  // key not found?
...
index = iterator->index;

Similar changes were made in the remove function for converting the key to upper case for case insensitive dictionaries.  The map erase function is used to remove a key from the map.

[branch stl commit 66561d4532]