std::map observation

L

lallous

Hello,

I noticed that as I insert items to std::map<std::string, std::string> map1
as:
map1["test"] = "hello";
map1["hello"] = "test";

Then use an iterator to walk in the map, the items will be retrieved by the
alphabetical order of the keys...is there is a way to allow std::map to enum
items in the order of insertion?
 
B

Brian Genisio

lallous said:
Hello,

I noticed that as I insert items to std::map<std::string, std::string> map1
as:
map1["test"] = "hello";
map1["hello"] = "test";

Then use an iterator to walk in the map, the items will be retrieved by the
alphabetical order of the keys...is there is a way to allow std::map to enum
items in the order of insertion?

From the implementations of the map containers I have seen, the map is
stored in a red-black, ordered tree. This greatly increases the lookup
speed. Storing in input order is very slow, and would make most
instances of std::map useless to the programmer.

If you want something ordered in the order they were put in there, use a
vector or list of pairs, and do a scan of the container (for loop) for
the key.

Brian
 
D

Dimitris Kamenopoulos

lallous said:
Hello,

I noticed that as I insert items to std::map<std::string, std::string>
map1 as:
map1["test"] = "hello";
map1["hello"] = "test";

Then use an iterator to walk in the map, the items will be retrieved by
the alphabetical order of the keys...is there is a way to allow std::map
to enum items in the order of insertion?

No. An std::map is a balanced tree that stays sorted whatever you put in it.
The insertion order is lost. Read any introductory text on trees. If you
want to enum items in the order of insertion you need a linear data
structure, such as a list or a deque.
 
R

Ron Natalie

lallous said:
Hello,

I noticed that as I insert items to std::map<std::string, std::string> map1
as:
map1["test"] = "hello";
map1["hello"] = "test";

Then use an iterator to walk in the map, the items will be retrieved by the
alphabetical order of the keys...is there is a way to allow std::map to enum
items in the order of insertion?

The only ordering the std::map knows is the one specified in it's declaration
(by default the simple Less (operator<) ordering). You can't change it, it's
inherently how the map is arranged internally. The "insertion order" is not
remembered anywhere. If you need the insertion order, you'll have to remember
it elsewhere.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,181
Messages
2,570,969
Members
47,536
Latest member
VeldaYoung

Latest Threads

Top