std::map

This is a discussion on std::map within the C++ Programming forums, part of the General Programming Boards category; Code: int main() { typedef std::map<string, int>::const_iterator Iter; std::map<string, int> words; // Map to store words and word counts cout ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    164

    std::map

    Code:
    int main()
    {
      typedef std::map<string, int>::const_iterator Iter;
      
      std::map<string, int> words;           // Map to store words and word counts
      cout << "Enter some text and press Enter followed by Ctrl+Z to end:" 
           << endl << endl;
    
      std::istream_iterator<string> begin(cin); // Stream iterator 
      std::istream_iterator<string> end;        // End stream iterator
      while(begin != end )                      // Iterate over words in the stream 
        words[*begin++]++;                      // Increment and store a word count
    
      // Output the words and their counts
      cout << endl << "Here are the word counts for the text you entered:" << endl;
      for(Iter iter = words.begin() ; iter != words.end() ; ++iter) 
        cout << std::setw(5) << iter->second << " " << iter->first << endl;
    
      return 0;
    }

    The above snippet tells the number of words in a given string, it works perfectly because it is from my book

    So the confusion I'm having is that in the line bold

    words[*begin++]++;


    This would create a new pair in the map because there are no entries in the map and the key is the string in the stream pointed by begin right? How will it create the int???? and how does it gives 0 value to the int??? it has no default constructor???

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Quote Originally Posted by manzoor
    This would create a new pair in the map because there are no entries in the map and the key is the string in the stream pointed by begin right?
    Yes, at least whenever begin points to a string that is not already a key in the map (in which case it merely increments the value of the element with that key).

    Quote Originally Posted by manzoor
    How will it create the int???? and how does it gives 0 value to the int??? it has no default constructor???
    When an int is value-initialised, it is zero-initialised, i.e., it is initialised to 0.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    Quote Originally Posted by laserlight View Post
    When an int is value-initialised, it is zero-initialised, i.e., it is initialised to 0.
    And what does that means ??? If possible please explain ty

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Are you aware that the constructor syntax T() can be used with the built-in types? For example, if we want to, we can write:
    Code:
    int x = int();
    Now, what std::map's operator[] does is that it attempts to insert std::make_pair(key, T()). The T() notation causes the value-initialisation of an object of type T. When T is int, this means creating an int with the value of 0.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Built-in types support constructor-like syntax too:

    Code:
    int n = int(); //"default-constructed" integer, has value 0
    So the template code
    Code:
    template <class T>
    ...
    T t = T();
    would also work for built-in types, and zero-initialize them.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    Thank you guys for the easy to understandable explanation

    Best place to ask C++ Questions

    What should I read next to know about the details of C++?
    Last edited by manzoor; 11-13-2008 at 08:35 AM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by manzoor View Post
    Thank you guys for the easy to understandable explanation

    Best place to ask C++ Questions

    What should I read next to know about the details of C++?
    If you're after something online, then I recommend these articles: http://www.gotw.ca/gotw/
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    For the original topic starter, why not just a vector?

    Vector[JustSomeInteger++] = word; ??
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Quote Originally Posted by execute
    For the original topic starter, why not just a vector?
    Because the aim is to record how many times each distinct word appears in the input. What you would be doing is storing in a vector all the words found in the input (and in your given example, you assume that the total number of words is known in advance).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    No, then you can just do a search with vector, and find how many times you've recorded it.

    Only arrays -- is when you need to know the number in advance.

    vectors and maps are the same, except that maps are used to associative assigning for keys. They can probably both be used in this situation, I just wanted to simplify it with vectors.
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by execute View Post
    vectors and maps are the same, except that maps are used to associative assigning for keys. They can probably both be used in this situation, I just wanted to simplify it with vectors.
    I'd say there are other significant differences, such as insertion/lookup complexity, and the fact that the ordering of elements in a map isn't under your control (except in the sense that the keys are arranged in increasing order)
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    Registered User
    Join Date
    Apr 2006
    Posts
    2,019
    You could use a vector, but a map has better complexity: Looking up a word and and inserting a word not in the list are both O(log N). With an unsorted vector finding a word is O(N), and inserting is O(1). With a sorted vector finding a word is O(log N), but inserting a word is very expensive.

    Also, for related reasons, the map API helps a cleaner looking solution to the problem.
    Last edited by King Mir; 11-14-2008 at 11:03 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Quote Originally Posted by execute
    Only arrays -- is when you need to know the number in advance.
    However, your example use of a vector treats it as if the number of elements is known in advance. You should be using push_back() instead of just assigning to the element at the given index.

    Quote Originally Posted by execute
    No, then you can just do a search with vector, and find how many times you've recorded it.
    ...
    They can probably both be used in this situation, I just wanted to simplify it with vectors.
    If you actually tried to write your "simplification", you would probably find that it is not so simple (hence King Mir's remark that the "the map API helps a cleaner looking solution to the problem"). Besides, the concerns about complexity as pointed out by brewbuck and King Mir, how are you going to eliminate duplicates after counting them? This means that you have to do a little more than just count.

    If you want complexity comparable to the solution with a map, then you have to sort, and then make a single pass over the sorted vector in which you detect each new word and begin counting until the next word, or the end of the vector. The std::equal_range generic algorithm could help with this, but it still would not be as simple as just inserting and then printing out the elements of a map.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. store in std::map all kind of structs
    By umen242 in forum C++ Programming
    Replies: 7
    Last Post: 10-19-2008, 02:24 AM
  2. std::map Alternatives
    By EvilGuru in forum C++ Programming
    Replies: 8
    Last Post: 04-12-2008, 03:45 AM
  3. Is std::map efficient for this problem?
    By dudeomanodude in forum C++ Programming
    Replies: 12
    Last Post: 04-10-2008, 02:15 PM
  4. std::map question.
    By Raigne in forum C++ Programming
    Replies: 7
    Last Post: 03-19-2008, 12:29 PM
  5. passing std::map from one dll to another
    By Carlos in forum Windows Programming
    Replies: 2
    Last Post: 05-16-2003, 07:45 AM

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