Member Avatar for Nexadus

Hello, I have this problem that's been bothering me on the back of my head for so long now. I don't know how to pursue or even break it down, I've tried reading the book, look at notes, nothing helps. Problem is, I have this file which contains

/*
Nitrite N1O2
NitrousOxide N2O1
Nitric N1O1
Nitryl N1O2
list goes on
*/

I've read from the file ( easy ) but the directions for this lab states
to store for each special formula along with names then display it in ascending order. The formulas are to be stored in structs and then placed in vectors. Basically the output should look like this.

N1O1
Nitric

N1O2
Nitrite, Nitryl

N2O1
NitrousOxide

etc.

It's said to be done "without sorting" and states

Notice that the output is sorted only by the number of nitrogen atoms.
There is no attempt to sort by anything else.
Or, put another way: all other orderings show simply the order the items were taken from the file.

I don't understand how this can be done without sorting. Please help.

Edited by Nexadus because: n/a
  • 6 Contributors
  • 8 Replies
  • 125 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by Nexadus

Dani AI

Generated

Short answer: do the ordering as you read the file instead of "sorting" the whole dataset afterward. The lab phrase "sorted only by the number of nitrogen atoms" means the output must be grouped by nitrogen count (ascending) and — per the spec — any ordering beyond that should reflect the order items came from the file. Note: the sample in the thread looks inconsistent with that sentence, so confirm with the instructor if in doubt.

Suggested approach (one pass, stable grouping)

  • Parse each input line to get the name plus the N and O counts (handle multi‑digit counts).
  • Keep a collection of buckets indexed by nitrogen count. Each bucket holds the distinct formula(s) seen for that N in the order they were first encountered, and for each formula a list of names (append when the same formula appears again).
  • While reading: ensure the bucket vector can grow to index N, then add the name to the appropriate formula entry in bucket N (create that formula entry if it’s the first time).
  • After reading: iterate buckets from low N to high N and print nonempty buckets. This requires no general-purpose sort and preserves file order for ties.

Why this fits the lab and how it compares to other suggestions found in the thread

  • and pointed at insertion-on-the-fly — that’s effectively what the bucket approach does but without scanning global data for each insert.
  • ’s map idea will give you ordered keys automatically, but you still need per-key vectors to preserve input order for names/formulas; using a tree map hides the “no explicit sort” requirement but is OK only if you understand its behavior.
  • Complexity: the bucket technique is linear-ish and conceptually simplest for small N ranges. If N can be huge, use a hash map keyed by N plus tracking min/max or seen keys and be mindful of memory.

Practical notes: parse digits robustly, trim whitespace, resize buckets on demand, and use a small per-bucket index map if you want O(1) appends to an existing formula entry.

Recommended Answers

All 8 Replies

Member Avatar for hag++

Just an idea.... im not sure if this is what you want but, you could create a struct that contains the chemical name and chemical makeup, then create an array of that struct to store file contents, which is easy. But in order to list in ascending order you HAVE to sort through all of the chemicals, I dont understand why sorting is not allowed....

Member Avatar for Nexadus

alright thanks, it's better than not getting any feedback =) so basically create an array of structs of that makeup and then sort. Oh we'll guess i'm going to have to ignore what the lab needs.

Any other feedback would help greatly!

Member Avatar for mrnutty

All you have to do is read the file but insert the elements you get into
its correct place. Is this enough of a hint?

Member Avatar for WaltP

Isn't a vector automatically sorted? Or am I thinking of something else?

Member Avatar for Nexadus

No, a vectors not sorted =(. It has a function to sort stuff I believe but it doesn't look like it's allowed in this lab.

firstPerson - So your saying I have to read the file such as

in >> nitrogenName >> tempChar >> nitrogenNumber >> tempChar >> oxygenNumber;

then place the elements in the correct spot? But how? What If I stored a nitrogen of number 12 and placed it into a struct, then pushed it back a vector, then the next number is 1 and I do the same. It's not like fstream allows me to skip reading some stuff from the file and goes back to it, then I could store it. The lab states "all other orderings show simply the order the items were taken from the file." which makes no sense because i can't simply just read, push back, and display! It doesn't make much sense to me.

Member Avatar for pecet

Maybe map/multimap is the solution. N2O1 could be used as the key and NitrousOxide as stored value. All elements in map are implicity sorted.

Member Avatar for jonsca

Just my 0.02 but it sounds like it might be a candidate for a singly linked list. You can enter the datum into it's proper place in the chain as it's coming in from the file. That approach is basically sorting the data but it doesn't explicitly take everything into a collection and then sort it.

Member Avatar for Nexadus

Well according to this thread I concluded that, theres no other way to solve this problem BUT to use a sort function. Can one more person confirm this?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.