terminator wrote:
On Nov 20, 3:23 pm, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
terminator wrote:
On Nov 20, 7:42 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
Neehar wrote:
Hello
For one of the interviews I took recently, I was given an offline
programming quiz.
In 30 minutes I had to write code in C++ to counts the number of
times each unique word appears in a given file.
I tried my level best even after the quiz to come up with a
solution but cudnt find an efficient one. :(
This is what I did.
1. Read all the words from the file and store them in a vector
container.
2. Sort the words in the vector container using most efficient
algorithm ( like Quicksort, Mergesort etc)
3. Then finding duplicates and occurences is very easy.
I was asked to do this without sorting.
Is there a better way to do this?
std::map< std::string, unsigned long > count;
std::string word;
while ( std::cin >> word ) {
++ count[ word ];
}
Now, there are issues on deciding what a word is. The above just
leaves that to operator>>.
does map initialize values to zero for intrinsic types?
[23.3.1.2/1]:
T& operator[](const key_type& x);
Returns: (*((insert(make_pair(x, T()))).first)).second.
Note that the default-value is T(). For unsigned long, that would be
0.
long l;
cout<<l<<endl;
you do not expect the above to print '0' for all runs of the program
do you?
Nope. But the above does not default-initialize l. The reason is clause
[8.5/9]:
If no initializer is specified for an object, and the object is of
(possibly cv-qualified) non-POD class type (or array thereof), the
object shall be default-initialized; if the object is of
const-qualified type, the underlying class type shall have a
user-declared default constructor. Otherwise, if no initializer is
specified for a nonstatic object, the object and its subobjects, if
any, have an indeterminate initial value90); ...
With
long l;
you request an uninitialized long, and that is what you get.
I do not think that default ctor for intrinsic types do anything.
Please refer to [8.5/5]
To default-initialize an object of type T means:
? if T is a non-POD class type (clause 9), the default constructor for
T
is called (and the initialization is ill-formed if T has no
accessible default constructor);
? if T is an array type, each element is default-initialized;
? otherwise, the object is zero-initialized.
However, that is of little relevance. The real question is, what is the
value of T() if T is a built-in type. To answer that, we need to know
about
[8.5/7]:
An object whose initializer is an empty set of parentheses, i.e., (),
shall be value-initialized.
and about [5.2.3/2]:
The expression T(), where T is a simple-type-specifier (7.1.5.2) for a
non-array complete object type or the (possibly cv-qualified) void
type, creates an rvalue of the specified type, which is
value-initialized (8.5; no initialization is done for the void() case).
So that says that long() will be a value-initialized long. Now, look up
[8.5/5]:
To value-initialize an object of type T means:
? if T is a class type (clause 9) with a user-declared constructor
(12.1),
then the default constructor for T is called (and the initialization
is ill-formed if T has no accessible default constructor);
? if T is a non-union class type without a user-declared constructor,
then
every non-static data member and base-class component of T is
value-initialized;
? if T is an array type, then each element is value-initialized;
? otherwise, the object is zero-initialized
The last item applies and we have to look up zero-initialization in the
same clause:
To zero-initialize an object of type T means:
...
? if T is a scalar type (3.9), the object is set to the value of 0
(zero)
converted to T;
So, if you do:
std::cout << long() << '\n';
you are justified to expect 0.