Filling map with 2 keys from a string. Character and frequency c++

I am new to maps so an a little unsure of the best way to do this. This task is in relation to compression with huffman coding. Heres what I have.

#include <map>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

typedef map<char,int> huffmanMap;

void getFreq(string file, map<char, int> map) 
{ 
    map.clear();    
    for (string::iterator i = file.begin(); i != file.end(); ++i) {
        ++map[*i];   
    }
}

above is one method I found online but was unable to print anything

int main()
{
    map<char, int> huffmanMap;
    string fileline;

    ifstream myfile;
    myfile.open("text.txt",ios::out); 

    while(!myfile.eof())  {
    getline(myfile, fileline); //get the line and put it in the fileline string
    }
    myfile.close();

I read in a from a text file to populate string fileline.

    for (int i=0; i<fileline.length(); i++) {
        char t = fileline[i];
        huffmanMap[i]? huffmanMap[i]++ : huffmanMap[i]=1;
    }

here is a second method I tried for populating the map, the char values are incorrect, symbols and smileyfaces..

    getFreq(fileline,huffmanMap);

    huffmanMap::iterator position;
    for (position = huffmanMap.begin(); position != huffmanMap.end(); position++)  {
        cout << "key: \"" << position->first << endl;
        cout << "value: " << position->second << endl;
    }

This is how 开发者_如何转开发I tried to print map

    system("pause");
    return 0;
}

When I run my getFreq method the program crashes. I dont get any errors with either. With the second method the char values are nonsense.Note I have not had both methods running at the same time I just incuded them both to show what i have tried.

Any insight would be appreciated.Thanks. Be lenient im a beginner ;)

Your code is all over the place, it's not very coherent so difficult to understand the flow.

Here are some low-lights:

This is wrong: myfile.open("text.txt",ios::out); - why would you open an input stream with out flag? it should simply be:

string fileline;
ifstream myfile("text.txt"); 

while(getline(myfile, fileline))  {
   // now use fileline.
}

In the while loop, what you want to do is to iterate over the content and add it to your map? So now the code looks like:

string fileline;
ifstream myfile("text.txt"); 

while(getline(myfile, fileline))  {
   getFreq(fileline, huffmanMap);
}

Next fix, this is wrong: you have a typedef and a variable of the same name!

typedef map<char,int> huffmanMap;

map<char, int> huffmanMap;

Use sensible naming

typedef map<char,int> huffmanMap_Type;

huffmanMap_Type huffmanMap;

Next fix, your getFreq method signature is wrong, you are passing the map by value (i.e. copy) rather than reference, hence you modification in the function is to a copy not the original!

wrong: void getFreq(string file, map<char, int> map)

correct: void getFreq(string file, huffmanMap_Type& map)

Next: why clear() in the above method? What if there is more than one line? No need for that surely?

That's enough for now, clean up your code and update your question if there are more issues.

One fix and One improvement.

Fix is : make second parameter in getFreq reference:

void getFreq(string file, map<char, int> & map); //notice `&`

Improvement is : just write

huffmanMap[i]++;

instead of

huffmanMap[i]? huffmanMap[i]++ : huffmanMap[i]=1;

After all, by writing huffmanMap[i]? you're checking whether it's zero or not. If zero, then you make it one, which is same as huffmanMap[i]++.

(An answer using C++ language features fom C++20.

But first, you were asking about getting getting the count (frequency) of letters in a text.

There is nearly a universal solution approach for this. We can use the std::unordered_map. It is described in the C++ reference here.

It is the std::unordered_maps very convienient index operator [] which makes counting very simple. This operator returns a reference to the value that is mapped to a key. So, it searched for the key and then returns the value. If the key does not exist, it inserts a new key/value pair and returns a reference to the value.

So, in any way, a reference to the value is returned. And this can be incremented. Example:

With a "std::unordered_map<char, int> mymap{};" and a text "aba", the follwoing can be done with the index operator:

• mymap['a'] will search for an 'a' in the map. It is not found, so a new entry for 'a' with corresponding value=0 is created: The a reference to the value is returned. And, if we now increment that, we will increment the counter value. So, mymap['a']++, wiil insert a new gey/value pair 'a'/0, then increment it, resulting in 'a'/1
• For 'b' the same as above will happen.
• For the next 'a', an entry will be found in the map, an so a reference to the value (1) is returned. This is incremented and will then be 2

And so on and so on.

By using some modern language elements, a whole file can be read and its characters counted, with one simple for-loop:

for (const char c : rng::istream_view<char>(ifs)) counter[c]++;

Additional information:

For building a Huffmann tree, we can use a Min-Heap, which can be easily implemented with the existing std::priority_queue. Please read here abour it.

With 4 lines of code, the complete Huffmann tree can be build.

And the end, we put the result in a code book. Again a std::unordered_map and show the result to the user.

This could zhen be for example implemented like the below:

#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <ranges>
#include <vector>
#include <utility>

namespace rng = std::ranges;            // Abbreviation for the rnages namespace
using namespace std::string_literals;   // And we want to use stding literals

// The Node of the Huffmann tree
struct Node {                           
    char letter{ '\0' };                // The letter that we want to encode
    std::size_t frequency{};            // The letters frequency in the source text
    Node* left{}, *right{};             // The pointers to the children of this node
};

// Some abbreviations to reduce typing work and make code more readable
using Counter = std::unordered_map<char, std::size_t>;
struct Comp { bool operator ()(const Node* n1, const Node* n2) { return n1->frequency > n2->frequency; } }; 
using MinHeap = std::priority_queue<Node*, std::vector<Node*>, Comp>;
using CodeBook = std::unordered_map<char, std::string>;

// Traverse the Huffmann Tree and build the code book
void buildCodeBook(Node* root, std::string code, CodeBook& cb) {
    if (root == nullptr) return;
    if (root->letter != '\0') cb[root->letter] = code;
    buildCodeBook(root->left, code + "0"s, cb);
    buildCodeBook(root->right, code + "1"s, cb);
}
// Get the top most two Elements from the Min-Heap
std::pair<Node*, Node*> getFrom(MinHeap& mh) {
    Node* left{ mh.top() }; mh.pop();
    Node* right{ mh.top() }; mh.pop();
    return { left, right };
}

// Demo function
int main() {
    if (std::ifstream ifs{ "r:\\lorem.txt" }; ifs) {

        // Define moste important resulting work products
        Counter counter{};
        MinHeap minHeap{};
        CodeBook codeBook{};

        // Read complete text from source file and count all characters ---------
        for (const char c : rng::istream_view<char>(ifs)) counter[c]++;

        // Build the Huffmann tree ----------------------------------------------
        // First, create a min heap, based and the letters frequency
        for (const auto& p : counter) minHeap.push(new Node{p.first, p.second});

        // Compress the nodes
        while (minHeap.size() > 1u) {
            auto [left, right] = getFrom(minHeap);
            minHeap.push(new Node{ '\0', left->frequency + right->frequency, left, right });
        }
        // And last but not least, generate the code book -----------------------
        buildCodeBook(minHeap.top(), {}, codeBook);

        // And, as debug output, show the code book -----------------------------
        for (const auto& [letter, code] : codeBook) std::cout << '\'' << letter << "': " << code << '\n';
    }
    else std::cerr << "\n\n***Error: Could not open source text file\n\n";
}

You my notice that we use new to allocate memory. But we do not delete it afterwards.

We could now add the delete statements at the approiate positions but I will show you a modified solution using smart pointers.

Please see here:

#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <queue>
#include <ranges>
#include <vector>
#include <utility>
#include <memory>

namespace rng = std::ranges;                // Abbreviation for the rnages namespace
using namespace std::string_literals;       // And we want to use stding literals
struct Node;                                // Forward declaration
using UPtrNode = std::unique_ptr<Node>;     // Using smart pointer for memory management

// The Node of the Huffmann tree
struct Node {
    char letter{ '\0' };                    // The letter that we want to encode
    std::size_t frequency{};                // The letters frequency in the source text
    UPtrNode left{}, right{};               // The pointers to the children of this node
};

// Some abbreviations to reduce typing work and make code more readable
using Counter = std::unordered_map<char, std::size_t>;
struct CompareNode { bool operator ()(const UPtrNode& n1, const UPtrNode& n2) { return n1->frequency > n2->frequency; } };
using MinHeap = std::priority_queue<UPtrNode, std::vector<UPtrNode>, CompareNode>;
using CodeBook = std::map<Counter::key_type, std::string>;

// Traverse the Huffmann Tree and build the code book
void buildCodeBook(UPtrNode&& root, std::string code, CodeBook& cb) {
    if (root == nullptr) return;
    if (root->letter != '\0') cb[root->letter] = code;
    buildCodeBook(std::move(root->left), code + "0"s, cb);
    buildCodeBook(std::move(root->right), code + "1"s, cb);
}
// Get the top most to Elements from the Min-Heap
std::pair<UPtrNode, UPtrNode> getFrom(MinHeap& mh) {

    UPtrNode left = std::move(const_cast<UPtrNode&>(mh.top()));mh.pop();
    UPtrNode right = std::move(const_cast<UPtrNode&>(mh.top()));mh.pop();
    return { std::move(left), std::move(right) };
}

// Demo function
int main() {
    if (std::ifstream ifs{ "r:\\lorem.txt" }; ifs) {

        // Define moste important resulting work products
        Counter counter{};
        MinHeap minHeap{};
        CodeBook codeBook{};

        // Read complete text from source file and count all characters ---------
        for (const char c : rng::istream_view<char>(ifs)) counter[c]++;

        // Build the Huffmann tree ----------------------------------------------
        // First, create a min heap, based and the letters frequency
        for (const auto& p : counter) minHeap.push(std::make_unique<Node>(Node{ p.first, p.second }));

        // Compress the nodes
        while (minHeap.size() > 1u) {
            auto [left, right] = getFrom(minHeap);
            minHeap.push(std::make_unique<Node>(Node{ '\0', left->frequency + right->frequency, std::move(left), std::move(right) }));
        }
        // And last but not least, generate the code book -----------------------
        buildCodeBook(std::move(const_cast<UPtrNode&>(minHeap.top())), {}, codeBook);

        // And, as debug output, show the code book -----------------------------
        for (std::size_t k{}; const auto & [letter, code] : codeBook) std::cout << ++k << "\t'" << letter << "': " << code << '\n';
    }
    else std::cerr << "\n\n***Error: Could not open source text file\n\n";
}