Talk:Map (C++ container)

From Wikipedia, the free encyclopedia

This article is supported by the Wikipedia:WikiProject C++. Please visit the project page for more details on the project.

Contents

[edit] "Iterating through every element of a map takes O(n) time" ?

But "Incrementing/decrementing an iterator takes O(log n) time". Therefore, shouldn't the iteration over all elements be O(n log n)? --Kaba3 (talk) 19:56, 18 January 2008 (UTC)

Oh, now I think I know what's wrong. I don't know what the standard guarantees, but if you implement the map with a binary tree (with data at every node), then you get amortized constant behaviour for iterator increment/decrement. This can be seen by considering that when iterating over all elements in order, every node gets visited at most twice. Because the number of nodes equals the number of elements, visiting all elements takes O(n). So is the claim "Incrementing/decrementing an iterator takes O(log n) time" correct? --Kaba3 (talk) 20:28, 18 January 2008 (UTC)

Amortized constant behaviour, yes, but in the worst case a single increment can still take O(log n) time. Think eg. of the case when the iterator is a leaf which is the right child of its parent but the parent is the left child of its parent, which is the left child of its parent, and so on. —Preceding unsigned comment added by 76.8.64.166 (talk) 21:54, 1 April 2008 (UTC)

[edit] Bad example

This is a very bad example for many reasons.

  1. "map" is the wrong data structure to use for the problem. One only desired to keep track of who is present, and has no need to keep track of who is not present (presumed to be everyone else). Although a value type (bool) is declared, it is never given a value other than "true", which is redundant. Therefore a "set" is the proper data structure.
  2. The present[s] uses the [] operator, which is bad. When "s" is not already in the map, it inserts a new element with key "s" and undefined value. This adds useless entries into the map about people who are not present.

I propose to replace the example with a real example where a mapping is used. Perhaps some kind of address book which maps names (string) to their address (another string); and then it prints out all the info in order by name. --Spoon! 01:23, 7 December 2006 (UTC)

I agree with your first point. I updated the "present" example to instead count words. This is a more realistic usage that requires map instead of set. Your second point is incorrect. While the [] operator does insert a new element with key "s", the value is not undefined; it is defined as 0/false. While using operator[] does add entries into the map about words that are not there, that is perfectly OK for the purposes of the example because it is correct and it clearly demonstrates that the operator[] inserts pairs with zeros as values. Krelborne (talk) 03:29, 2 January 2008 (UTC)

[edit] Initialization

Is it true that integers are initialized to zero and booleans to false? I'm doubtful. Can you cite a source for this statement?

MrDizzy 16:25, 20 February 2007 (UTC)

This sounds wrong to me, as integers and bools are primitive data types and hence have not default constructor, im "being bold" and killing the comment. 129.78.64.102 06:56, 7 March 2007 (UTC)

Built in data types can be default-initialized, ISO/IEC 14882, 8.5.5 says, slightly reworded:
Unless T is an array type or a (non-POD) class type, it is zero-initialized. For scalar types, the object is set to the value of 0 (zero) converted to T. Ufretin (talk) 19:22, 11 January 2008 (UTC)

[edit] Bad Colors

cout.setf(ios::boolalpha)

The cyan setf and boolalpha against the gray is really difficult for me to read.

Also, Hello, Wikipedia World! This is my first discussion post.

Juancnuno 20:09, 13 October 2007 (UTC)



[edit] Code Not Working Right

Guys I just wanted to let you know that the code posted

  1. include <iostream>
  2. include <string>
  3. include <map>

using namespace std;

int main() {

   map<string, int> wordcounts;
   string s;
   int count = 1;

   while (cin >> s && s != "end")
       wordcounts[s] = count++;

   while (cin >> s && s != "end")
       cout << s << ' ' << wordcounts[s] << endl;

}

does not work right and for some strings it just gives meaningless outputs.

And in any case count should first be initialized to 0

Wanted to let you know... —Preceding unsigned comment added by 128.211.171.92 (talk) 23:01, 26 March 2008 (UTC)