5

Is there any way to avoid sorting of map on the basis of key value. Actually i want to display all pair in same order i insert it into map.

Ganesh
  • 71
  • 4
  • 5
  • 3
    How many entries will be there in the map? if not too many or lookup is not that important you can use `vector >` – Naveen Mar 07 '11 at 06:26
  • Also see the related question: http://stackoverflow.com/questions/1605807/boostunordered-map-maintains-order-of-insertion – Naveen Mar 07 '11 at 06:50
  • @Naveen: You really should post this as an answer. – Björn Pollex Mar 07 '11 at 07:52
  • As well as the obvious (and sensible) option of using a vector, there's the silly but correct answer: use an insertion counter as your key... :-(. Of course, if you want to store a key value too, you may need a pair of (ordering, key) and custom comparison.... Anyway, too much said ;-). – Tony Delroy Mar 07 '11 at 08:42

5 Answers5

9

Why not use a vector of pairs? That would suffice your requirement i guess

mukeshkumar
  • 2,698
  • 3
  • 19
  • 20
3

No, there isn't. std::map<> sorts by key to implement O(lg(n)) lookup.

You can get around with a std::vector<std::pair<Key,Value>> to achieve what you need, but you'll need to write your own O(n) lookup function to retrieve values by key.

André Caron
  • 44,541
  • 12
  • 67
  • 125
3

It seems what you require is two "views" of the data, one which maintains insert order and one which (presumably) you use for fast lookups. There is a structure which allows you to maintain this - if you can include boost. It's the boost multi_index container. You can specify two indexes, a hashed_unique and ordered_unique.

Nim
  • 33,299
  • 2
  • 62
  • 101
2

The way map is implemented internally, it's not possible for you to prevent keys to be sorted. However, you can maintain an additional list(using vector) to store the order in which keys appear. Later on, iterate over the map and the vector to achieve what you want.

Shamim Hafiz - MSFT
  • 21,454
  • 43
  • 116
  • 176
  • 6
    It's more than an internal implementation issue, it's an interface _guarantee_ that a `map` is ordered by key. – CB Bailey Mar 07 '11 at 08:24
0

I'm speculating here. Other would know for sure, but maps aren't stored in an array. It's more like a B-tree.

That means there is no way to know what record in the map was stored before or after another. Were I to build a map from scratch, I'd surely have no way to accomplish your task. Sorry.

Perhaps a map isn't your best option for storage. If you want to retrieve things in the order you've pushed them in, then perhaps a vector.

baash05
  • 4,394
  • 11
  • 59
  • 97
  • If I recall, the complexity requirements of `std::set<>` and `std::map<>` implicitly impose the use of red-black trees, as they are the only ones that offer `O(lg(n))` on insertion, lookup *and* removal. – André Caron Mar 07 '11 at 15:08