Attribute Parser

This is a challenge question from hackerrank.com.


We have defined our own markup language HRML. In HRML, each element
consists of a starting and ending tag, and there are attributes
associated with each tag. Only starting tags can have attributes. We
can call an attribute by referencing the tag, followed by a tilde,
'~' and the name of the attribute. The tags may also be nested.


The opening tags follow the format:

The closing tags follow the format:

For example:

The attributes are referenced as:

tag1~value  
tag1.tag2~name

You are given the source code in HRML format consisting of N lines.
You have to answer Q queries. Each query asks you to print the value
of the attribute specified. Print "Not Found!" if there isn't any such
attribute.

Input Format


The first line consists of two space separated integers, N and Q.
N specifies the number of lines in the HRML source program. Q specifies the number of queries.


The following N lines consist of either an opening tag with zero or
more attributes or a closing tag.


Q queries follow. Each query consists of string that references an attribute in the source program.

Constraints


1 ≤ N ≤ 20

1 ≤ Q ≤ 20


Each line in the source program contains, at max, 200 characters.


Every reference to the attributes in the Q queries contains at max
200 characters.


All tag names are unique.

Output Format


Print the value of the attribute for each query. Print "Not Found!"
without quotes if there is no such attribute in the source program.

Sample Input

4 3

tag1.tag2~name
tag1~name
tag1~value

Sample Output

Name1
Not Found!
HelloWorld

Please review my code and let me know your suggestions.

```
#include
#include
#include
#include
#include
#include
#include
#include

int main() {
std::string first;
std::getline(std::cin, first);
std::

Here are some ideas that may help you improve your code.

Use functions

Right now this code is all one big block of code in main. This makes it more difficult to read and understand than if functions were used.

Simplify your code

Consider this sequence of code to read two integers:

std::string first;
std::getline(std::cin, first);
std::istringstream iss(first);
std::vector tokens1;
std::copy(std::istream_iterator (iss),
             std::istream_iterator(),
             std::back_inserter(tokens1));

int n = tokens1[0], q=tokens1[1];

Now consider this version:

int n, q;
std::cin >> n >> q;

Which is easier to read and understand? It's true they don't do the exact same thing, but I suspect the differences don't much matter in this case.

Eliminate unused variables

Unused variables are a sign of poor quality code, and you don't want to write poor quality code. In this code, source is unused. Your compiler may be smart enough to tell you about this if you ask it nicely.

Don't #include headers that aren't needed

This code includes ` and but neither are actually used. Those lines should be deleted.

Use appropriate data structures

The tagKey variable is a std::string and keeps the current tag stack as a '.' separated string. However this gets messy and complex because "popping" a tag from the end means looking for that delimiter and then erasing just that bit. I'd be inclined to create a class for that to encapsulate this complexity. Here's one way to do that:

class StringStack : public std::deque {
public:
    std::string asString() const {
        auto it{cbegin()};
        std::string str{*it};
        for (++it; it != cend(); ++it) {
            str += "." + *it;
        }
        return str;
    }
};

Use a state machine

The logic of this code could be expressed as a state machine. If that were done, one could process the stream "on the fly" character at a time with little difficulty.

Prefer unordered_map to map

There's not really any reason that this code needs a map instead of an unordered_map and one generally gets a performance increase using the unordered version.

An example

Using the suggestions above, my rewritten version of main looks like this:

int main() {
    constexpr std::size_t maxlinelen{200};

    int n, q;
    std::cin >> n >> q;
    std::cin.ignore(maxlinelen, '\n');

    auto tagValue{fetchTags(std::cin, n)};

    for(std::string query; q > 0 && std::getline(std::cin, query); --q) {
        auto search = tagValue.find(query);
        if (search == tagValue.end()) {
            std::cout second << '\n';
        }
    }
}

I implemented a fetchTags() routine using a state machine and returning a std::unordered_map` but rather than spoil the fun, I'll leave it to you to implement your own.

StackExchange Code Review Q#160150, answer score: 5