Noob question to hlep getting started with priority queue

This is a discussion on Noob question to hlep getting started with priority queue within the C++ Programming forums, part of the General Programming Boards category; Can I retried the actual contents from the argv element or do I still have to open the files in ...

  1. #16
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    Can I retried the actual contents from the argv element or do I still have to open the files in main and operate on them?
    No, open the file. Your assignment requires that the input comes from a file, as far as I can tell. Not to mention that entering in file contents on the command line is kind of weird. Basically, why would you do that when you have cin to read keyboard input anyway.
    Also, once I do that how do I skip the first letter of each row i.e. B in my first post and just build my heap from the value pairs?
    Well, you shouldn't want to skip it. The first letter in each row stands for an operation. B in the first post means build the heap. In order for your program to be the best it can be, you ought to program a response to each possible request and be flexible. If you make a program that reacts properly to only the one file, that's kind of lazy. Your instructor might see that and punish you with a lower grade.

  2. #17
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Quote Originally Posted by whiteflags View Post
    No, open the file. Your assignment requires that the input comes from a file, as far as I can tell. Not to mention that entering in file contents on the command line is kind of weird. Basically, why would you do that when you have cin to read keyboard input anyway.

    Well, you shouldn't want to skip it. The first letter in each row stands for an operation. B in the first post means build the heap. In order for your program to be the best it can be, you ought to program a response to each possible request and be flexible. If you make a program that reacts properly to only the one file, that's kind of lazy. Your instructor might see that and punish you with a lower grade.
    Yeah, I thought I should open the file, but I didn't understand what the point of having the file name in argv[].
    Thanks, I wasn't trying to be lazy, just trying to understand how it should process the data.

    So I've built my header file, and am working on my functions and have a couple more questions.
    -Would I be better off doing everything in one source file and having functions instead of having a header and file associated with?

    Will a tradition heap process both letters, numbers (including floats) and how does it work? i.e. What has priority etc? Or is that something I am supposed to design.

    Also, is there any advice/references to figure out how to take the first character of each row (the command letters) and then use the rest for the heap?
    -Do I just build an array with the first row and have it stop when it hits a command letter?
    Last edited by carpeltunnel; 09-15-2013 at 08:19 PM. Reason: Edit question

  3. #18
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    -Would I be better off doing everything in one source file and having functions instead of having a header and file associated with?
    Your assignment seems to answer the question:
    Use good programming style. Your priority queue code should be separated from the driver program pa1 which is used to test the code and from the class of the object that it is storing.
    Will a tradition heap process both letters, numbers (including floats) and how does it work? i.e. What has priority etc? Or is that something I am supposed to design.
    If you don't know what a priority queue is, I don't see how you are going to do the assignment. You need to do some reading: Priority queue - Wikipedia, the free encyclopedia
    Also, is there any advice/references to figure out how to take the first character of each row (the command letters) and then use the rest for the heap?
    -Do I just build an array with the first row and have it stop when it hits a command letter?
    You should be able to read the file one line at a time. When you run out of lines, the program is done working.

    A line like:
    Code:
    B foo 1 bar 2 quz 3 qux 4
    contains everything you need to know about a specific operation.
    Your plan was:
    My plan was to make a switch and for each case it performs specific task, so would I store foo-4 into an array
    That's actually a very good plan, but your running before walking. Each line, especially if it is going to make or edit a priority queue, has the following format:
    Code:
    Operation-Code Optional-Queue-Element, Optional-Queue-Element, Optional-Queue-Element, Optional-Queue-Element, ... End-of-line
    You need to break this line apart first, with something like http://www.cplusplus.com/reference/s.../stringstream/. Then decide what to do based on the operation code, using the queue elements. Some operations, like dumping, don't require file processing beyond reading the operation code.
    Last edited by whiteflags; 09-16-2013 at 12:28 AM.

  4. #19
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    I'm so overwhelmed, paypal for help!

  5. #20
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    If nobody wants that offer lol,

    Code:
    while
    (inFile)
    	{
    		std::string lineRead;
    		
    char command;
    		inFile.getline(inFile) >> lineRead;
    		lineRead.getChar() >> command;
    		
    switch(command)
    	}
    

    Is there away to take it string by string like an array.

    So I can do something like
    Code:
    //get.char[0]>>command;
    
    //get.pair{I,i+1)
    or something to that extent



  6. #21
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    Quote Originally Posted by carpeltunnel View Post
    I'm so overwhelmed, paypal for help!
    Hi, I'm sorry it's taking me so long to get back with you. It sounds like you're giving up though. I don't want you to do that.
    Quote Originally Posted by carpeltunnel View Post
    If nobody wants that offer lol,

    Code:
    while
    (inFile)
    	{
    		std::string lineRead;
    		
    char command;
    		inFile.getline(inFile) >> lineRead;
    		lineRead.getChar() >> command;
    		
    switch(command)
    	}
    

    Is there away to take it string by string like an array.

    So I can do something like
    Code:
    //get.char[0]>>command;
    
    //get.pair{I,i+1)
    or something to that extent


    Please try to be patient. Speaking as a person from a higher perspective, it takes time to work on your problem. It can help you feel less stressed if you trust that people are trying to help you.

    I have some bad news. That is a pretty awful attempt at reading a file. Luckily, I think I put something together that will help you understand the steps you need to take to process the file. That's later on in the post. I want to try rewriting my answers to your questions first.

    -Would I be better off doing everything in one source file and having functions instead of having a header and file associated with?
    If you do the assignment in C++ (the assignment seems ambiguous on the language), I think it would be best to turn in a header file for a priority queue class, a source file with a priority queue implementation, and another source file that tests the implementation in a main() function, where you read the file and respond accordingly.

    Will a tradition heap process both letters, numbers (including floats) and how does it work? i.e. What has priority etc? Or is that something I am supposed to design.
    A normal heap would work fine. The queue element has to be designed though, because in C++, most data structures, including heaps, are homogeneous, meaning they work on one kind of thing. So to complete the assignment, you need to design a queue element that fits your data. Again, you'll see my ideas on this in a moment.

    Also, is there any advice/references to figure out how to take the first character of each row (the command letters) and then use the rest for the heap?
    I can give you something that might help. There are a few things I am worried about though. It looks like you aren't very familiar with C++ file stream workings or syntax. You need to be comfortable with those things if you want to do it in C++. Most of the tutorials on that subject are inferior to books that teach C++, so you might want to reread a college textbook or something. Again, the assignment seems ambiguous about the language requirement, so, you might just want to do it in an easier language for you.

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <sstream>
    using namespace std;
    
    struct qelement {
    	string data;
    	float priority;
    	
    	// This operator makes it concise for me to display information.
    	friend ostream& operator << (ostream& outstr, const qelement& elem);
    
    	// This operator makes it concise for me to read information.
    	friend istream& operator >> (istream& instr, qelement& elem);
    };
    
    ostream& operator << (ostream& outstr, const qelement& elem) {
    	outstr << "priority: " << elem.priority << ", " << "data: " << elem.data << '\n';
    	return outstr;
    }
    
    istream& operator >> (istream& instr, qelement& elem) {
    	qelement result;
    	if (instr >> result.data >> result.priority) {
    		elem = result;
    	}
    	return instr;
    }
    
    int main() {
    
    // 1. Open the file from the thread.
    	ifstream file("carpeltunnel.txt");
    	if (file.is_open() == false) {
    		cout << "couldn't open carpeltunnel.txt\n";
    		return 0;
    	}
    	
    	char operation;
    	string ln;
    
    	// 2. Read each line.
    	while (getline(file, ln)) {
    
    		// 3. Parse the operation/read the operation from the line.
    		stringstream buffer(ln);
    		buffer >> operation;
    
    		// 4. Display the operation.
    		cout << "Operation is " << operation << ":\n";
    
    		// 5. Parse any queue elements that are part of the line.
    		qelement elem;
    		while (buffer >> elem) {
    
    			// 6. Show what we received as input.
    			cout << '\t' << elem << '\n';
    		}
    	}
    	return 0;
    }
    The output of the above code is:
    Code:
    C:\Users\Josh2>readfile
    Operation is B:
            priority: 9.1, data: foo
    
            priority: 2.1, data: bar
    
            priority: 1, data: a
    
            priority: -4, data: b
    
            priority: 7, data: c
    
            priority: 2, data: d
    
            priority: -4, data: e
    
            priority: 5, data: f
    
            priority: 7, data: g
    
            priority: 9, data: h
    
            priority: 4, data: i
    
    Operation is D:
    Operation is U:
            priority: 2, data: f
    
            priority: 11, data: d
    
            priority: 3, data: c
    
    Operation is P:
    Operation is R:
    Operation is R:
    Operation is R:
    Operation is D:
    
    C:\Users\Josh2>
    This is to show that we successfully parsed the entire file. You can see the operations and the relevant data.

    The way that I attacked the problem is, to go more into detail about it than what's in the comments: I think it is really important to read the file one whole line at a time, storing the line in a big string. After you do that, you can focus on turning the big string into whatever you really need.

    Usually that means breaking up the string into tiny parts. Using stringstream, I was able read in an operation and modify the elem object as many times as I needed to on one line.

    If I wrote this for real, some things would change. There would be more logic to decide what to do with the data I was receiving. Build would make me insert the elem I just read into the queue, and keep going until there is no more stuff to put in queue. I would have to update an existing item in the heap when I read operation U: that item should look like elem. The other operations, even though they don't involve data from the file, would mean that I would have to change or display the queue.

    Anyway, I really hope this helped. I tried to present a really clean example so I don't really know how else to inspire you.
    Last edited by whiteflags; 09-18-2013 at 08:39 PM.

  7. #22
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Quote Originally Posted by whiteflags View Post
    Anyway, I really hope this helped. I tried to present a really clean example so I don't really know how else to inspire you.
    No, this is extremely helpful and in a really easy to process format.

    My issue is I have split my classes between universities and my entry level code classes did not equip me for what I am getting into now.

    Unfortunately C++ is my "most" familiar language, although I wish it was python (my instructor said it would take 1/10 of the time), but I will go over what you have taken the time to write out and try to work through some of my issues and misconceptions.

    And I can't express how much I appreciate the detailed instruction of going on, I feel like I grasp the logic behind the code well, I just struggle with implementation.

    I am eager to get better and really enjoy code and the satisfaction involved with a running program (albeit rare), do you have any suggestions on a must-have book?
    Last edited by carpeltunnel; 09-18-2013 at 09:35 PM. Reason: More gratitude

  8. #23
    Registered User
    Join Date
    Apr 2013
    Posts
    1,322
    ... c++ ... array ... smart pointers
    The problem statement suggests that the program should use an array / vector / heap pointers to objects (structures). It also suggest using some hash like method, such as std::unordered_map, where the mapped value could be a pointer to an object. It's not clear if the unordered_map class can be used by itself, or if the mapped values are supposed to be used to index the array / vector of pointers to objects. It also mentions using smart pointers but smart pointers auto-delete at function completion, and the same map or array of pointers will be used across multiple functions, including insert and delete operations.

    It's not clear to me what the rules are for implementing the priority queue itself, and I suspect it's not clear to the original poster, so hopefully someone here can explain this?

  9. #24
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    And I can't express how much I appreciate the detailed instruction of going on, I feel like I grasp the logic behind the code well, I just struggle with implementation.
    Just don't feel pressured to use what I used in the example. It's completely OK with me if you use C++ code that you can teach to me instead.

    do you have any suggestions on a must-have book?
    Not really. Look at the Book recommendations thread. There are plenty of good books in there, but I don't really have a personal bible. (Call it aptitude I guess.) And I still feel dumb sometimes. Don't sell your college books if you finally understand them, they can be referenced over and over.

  10. #25
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    It's not clear to me what the rules are for implementing the priority queue itself, and I suspect it's not clear to the original poster, so hopefully someone here can explain this?
    I think the assignment is confusing too. If you've never implemented a priority queue before, well, it is a queue, and each element has an associated priority. Elements are meant to be processed in priority order. Making the data conform to a min heap property is one way to implement it.

    The specifics of the assignment demand some things that I have never really cared about but wouldn't have a personal issue doing, like wanting to find specific elements in the queue in better than linear time. Admittedly, some of the ideas put forward, like hashing, are bad, if you want the data to work remotely like a queue. I would just sort and use a binary search.
    Last edited by whiteflags; 09-18-2013 at 10:27 PM.

  11. #26
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Quote Originally Posted by whiteflags View Post
    I think the assignment is confusing too. If you've never implemented a priority queue before, well, it is a queue, and each element has an associated priority. Elements are meant to be processed in priority order. Making the data conform to a min heap property is one way to implement it.

    The specifics of the assignment demand some things that I have never really cared about but wouldn't have a personal issue doing, like wanting to find specific elements in the queue in better than linear time. Admittedly, some of the ideas put forward, like hashing, are bad, if you want the data to work remotely like a queue. I would just sort and use a binary search.
    The class is for algorithms is that has any play into some of those guidelines to the assignment, just food for thought. I'm obv the noob so idk if that even correlates but it may be the case.

    And thanks to white flags I have a solid main() outline, am working on making functions from my queue class to do all the necessary operating but I feel so much farther and under control relative to a couple days ago.

  12. #27
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    Quote Originally Posted by carpeltunnel View Post
    I am eager to get better and really enjoy code and the satisfaction involved with a running program (albeit rare), do you have any suggestions on a must-have book?
    C++ Book Recommendations

    Quote Originally Posted by rcgldr View Post
    ...It also mentions using smart pointers but smart pointers auto-delete at function completion, and the same map or array of pointers will be used across multiple functions, including insert and delete operations.
    Ummm, no? They auto-delete when the last reference (for shared_ptr) goes out of scope, or when it goes out of scope (unique_ptr).
    Sure, they go out of scope at the function end, if if you keep the data alive by some global data structure or some parameter, then the memory won't be freed at function end.
    The same applies to pointers. You must have a parameter or some global state to retain the pointers; otherwise, you must just as well delete them at the scope's end because you'll never be able to use them anywhere else anyway.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #28
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    Okay, a couple questions.

    Would
    Code:
     qelement elem; while (buffer >> elem) {
     
               pq[priority] = string;
    
            }
    
    Map the struct elements into an map (given pq is the map name)?

    Is it possible to take contents from a map and store them into a vector...or is my perception of how that would work flawed?

    Also,

    Code:
    // 1. Open the file from the thread.
        ifstream file("carpeltunnel.txt");
        if (file.is_open() == false) {
            cout << "couldn't open carpeltunnel.txt\n";
            return 0;
        }
    


    If I have the file name in argv[1] how to I open it. I have tried ifstream file ("argv [1]") and without quotes and a couple others forms with no luck.

    Code:
    case P:
       for ( i = 1; i+=)
       {
       x = pq.find[i];
       if (x != pq.end()) //found key
        cout << p->first << p-> second << endl; 
       else
        cout << "Item not found" << endl;
       break;
      }
    Is this even remotely close to a peek and find using my map?

    And thanks to white flags I have a solid main() outline, am working on making functions from my queue class to do all the necessary operating but I feel so much farther and under control relative to a couple days ago.
    ....I spoke to soon
    Last edited by carpeltunnel; 09-20-2013 at 06:14 PM.

  14. #29
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    Is it possible to take contents from a map and store them into a vector...or is my perception of how that would work flawed?
    If you want a vector of qelements, it should be possible. Map automatically stores a type called pair -- the pair is a key type and a value type -- so you could just do:
    Code:
    #include <map>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    vector<pair<float, string> > flatmap(map.size());
    copy(map.begin(), map.end(), flatmap.begin());
    Then each map element is in the vector: flatmap[i].first is the key, flatmap[i].second is the value.

    If you just want a vector of keys, or values, then it's literally just a loop that calls push_back, for example, a vector of values is:
    Code:
    #include<vector>
    #include<map>
    vector<string> values(map.size());
    for (map<float, string>::iterator i = map.begin(); i != map.end(); i++)
        values.push_back(i->second);
    I have tried ifstream file ("argv [1]") and without quotes and a couple others forms with no luck.
    ifstream file(argv[1]); will work.

    You have to pass in command line arguments though, or it will probably crash. We discussed that a few days ago I believe.

    1. You have to set up your IDE in the following way:
    Quote Originally Posted by Elysia
    Goto project properties -> Debugging and enter your parameters under "Command Arguments".
    Also consider upgrading. 2012 has been out for a long while now. 2013 RC is also out if you like experimenting with new software (not production ready).
    2. And of course main() will change to
    Code:
    int main(int argc, const char *argv[])
    With those changes it should work.
    Last edited by whiteflags; 09-20-2013 at 07:11 PM. Reason: arguments to copy were incorrect

  15. #30
    Registered User
    Join Date
    Sep 2012
    Posts
    86
    With those changes it should work.
    Yea, I was making a mistake displaying the file.

    So, from talking to my professor a priority queue is "abstract" for lack of a better word (or understanding).

    So putting my pairs into the vector would "build the heap"
    or do I need to store the mapping elements into the vector and then "build a heap".

    A sub question, is can I take my struct as white flags demonstrated, make a vector from within my priority queue class and then transmit the information/updates... or am I waaaaaaaaayyyyy offfffff?

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Priority queue STL
    By dpp in forum C++ Programming
    Replies: 2
    Last Post: 01-08-2009, 02:21 AM
  2. Priority queue
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2007, 01:30 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-15-2007, 12:48 AM
  4. Priority Queue Question
    By ac251404 in forum C++ Programming
    Replies: 26
    Last Post: 08-16-2006, 12:51 PM
  5. Priority Queue
    By evotron in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 01:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21