Any efficient way to do word count without STL?

Oct 19, 2012 at 3:33pm
I have to write a program that can show "top N most frequently words" in an article, and cannot implement with any STL container or algorithm.

(N is depend on input value)

If I implement with my custom class which contains a string value and a int value, and then count the frequency directly, is there any way to lower the time complexity? Or is there any other algorithms that can do this work with higher efficiency?

Thanks!
Last edited on Oct 19, 2012 at 3:42pm
Oct 19, 2012 at 4:58pm
Well, you can't lower the time complexity to better than O(n), where n is the numer of words in the article. Given a container for each word, you have to find the right container, and create it if it is not present, so you really want a sorted array for you containers (sorted by the string). Finally, I hope you mean that you have a c-string - ie a NULL terminated character array - because the string class is a stl container: string == std::basic_string<char>.
Oct 19, 2012 at 5:58pm
I would build a container as an ordered list. That is a list where elements are inserted in the lexicographical order. After that I would use the binary search to detreming whether a given word is already in the list or should be inserted in it.
Last edited on Oct 19, 2012 at 5:59pm
Topic archived. No new replies allowed.