Talk:Map (C++)

"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)

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)

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. Decltype (talk) 19:22, 11 January 2008 (UTC)

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)

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)

Renaming this article to follow a consistent convention

Hi, I am currently considering renaming this article to conform to a common convention for C++ Standard Library components. The full discussion can be found here. decltype 09:45, 6 March 2009 (UTC)

Performance

According to the referenced page 3, those following items:

• Iterating through all elements ( O(n) time )

and

• Copying an entire map ( O(n log n ) time )

It seems, reading the wikipedia sentence that the above items take O( log n ). Is it a mistake from me ???

Heretik_0127 06 July 2009 —Preceding undated comment added 05:15, 6 July 2009 (UTC).

map::erase() and iterators

Are you sure that statement [1] "iterators are not invalidated by insert ***and erase*** operations (...)" is true?

According to spec: "Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased". Also users' experience [2] show that iterators are invalidated by ::erase(). —Preceding unsigned comment added by 212.2.96.101 (talk) 09:28, 20 May 2010 (UTC)

Yes, [t]he erase members shall invalidate only iterators and references to the erased elements. I would think it was obvious that a reference to an object that has been erased from a container would be invalid, but perhaps the sentence needs clarification. decltype (talk) 09:54, 20 May 2010 (UTC)

Problem with example

The example for the insert method states that if you supply a key that is already used in the map, the existing value is overwritten. I've seen elsewhere (cplusplus.com) that the new value is ignored and the existing one is not modified. Clarification?

24.2.1.193 (talk) 01:03, 23 August 2010 (UTC)

You are right, except I don't see the example you are talking about. But this example works as you describe:

    typedef std::map<int, std::string> map_t;
    map_t m;
    typedef std::pair<map_t::iterator, bool> ret_t;
    ret_t ret = m.insert(std::make_pair(1, "foo"));
    std::cout << &*ret.first << " " << ret.second << " " << m[1] << "\n";
    ret = m.insert(std::make_pair(1, "bar"));
    std::cout << &*ret.first << " " << ret.second << " " << m[1] << "\n";
    m[1] = "baz";
    std::cout << m[1] << "\n";

This returns for me:

     0x1343060 1 foo
     0x1343060 0 foo
     baz

That is, it inserts foo, then doesn't insert bar and so returns an iterator to the foo that was there, then replaces it with baz. The c++.com reference. —Ben FrantzDale (talk) 13:09, 23 August 2010 (UTC)

Performance note

"Note that this performance cost applies to each task individually."

No point in noting. 4O(logn) = O(logn), right? —Preceding unsigned comment added by 194.237.142.7 (talk) 12:10, 4 May 2011 (UTC)

confusing statements on overwriting keys

you have me confused about whether I overwrite an existing value in the map when I assign a key/value pair like this:

   data["Rockys score"] = 22;
   data["Rockys score"] = 23;  /*overwrites the 22 as keys are unique */

but in the beginning of the article is stated:

Since each key value is unique, if an object is inserted with an already existing key, the object already present in the map does not change.

now, which is it ? — Preceding unsigned comment added by 77.248.90.201 (talk) 20:00, 14 July 2011 (UTC)

The article is talking about map::insert. You use subscripting operator which has different semantics - it always returns a reference to the value corresponding to the key, creating new key-value pair if the key does not already exist. See this reference.

Reorganization

There's an ongoing discussion about an reorganization of the articles about the C++ containers. This page is one of the subjects of that discussion. Please express your opinion. 1exec1 (talk) 20:16, 2 December 2011 (UTC)