Any efficient way to do word count without STL?

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?

Last edited on
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>.
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
Topic archived. No new replies allowed.