How to iterate std::map values in my own order / the order they were inserted?

Question

Suppose I have a std::map and I've inserted the following values:

3, 5, 2, 1, 4, 6

By default std::map will iterate them in sorted order:

1, 2, 3, 4, 5, 6

But I want to iterate them in Insertion order:

3, 5, 2, 1, 4, 6

Can anyone tell me how can I do that?

Keep a sequence container containing the insert-order of your keys and enumerate that. — WhozCraig, Aug 28 '15 at 06:49
why would you need std::map? std::array would suffice your needs — Arun, Aug 28 '15 at 06:51
So how do you store single integers into an `std::map`? Are you sure you're not talking about `std::set`? — juanchopanza, Aug 28 '15 at 06:57

score 1 · Answer 1 · answered Aug 28 '15 at 07:26

1

Use a std::vector and use push_back for insertion. Then traversing the vector will output elements in insertion order.

Use std::sort(v.begin(), v.end()) (on a vector copy) if you want to get the elements sorted.

answered Aug 28 '15 at 07:26

Antonio Pérez

6,702
4
36
61

score 0 · Answer 2 · edited May 23 '17 at 10:26

std::map allways sorts for the key. You have to decide which functionality you want to use from the standard containers. Before you use one, simple check out for the functions of the templates:

http://www.cplusplus.com/reference/stl/

Or look here for a discussion on stl containers: What are the complexity guarantees of the standard containers?

Some examples and as last inside this you can find a combination of two containers if you need fast access via a sorted map ( binary search ) and the data in original order. As you can see within the example the data is only stored once, can be modified and accessed via both containers. int main() { // std::array is static initialized and unsorted std::array arr{ 3, 5, 2, 1, 4, 6}; std::cout << "Array:"<

    // std::array is a dynamic type, can be expanded at runtime
    std::vector<int> vec{3, 5, 2, 1, 4, 6};
    std::cout << "Vector:"<<std::endl;
    for( auto& el:vec){ std::cout << el << std::endl; }

    // std::map is always sorted
    std::cout << "Map" << std::endl;
    std::map<int,std::string> map{{3,"three"},{5,"five"},{2,"two"},{1,"one"},{4,"four"},{6,"six"}};
    for( auto& el:map){ std::cout << el.first << " " << el.second<< std::endl; }


    // if you need fast index access and also unsorted, you can combine two conatainers:
    using PT = std::pair<int, std::string>;

    std::array<PT,6> arr2{PT{3,"three"},PT{5,"five"},PT{2,"two"},PT{1,"one"},PT{4,"four"},PT{6,"six"}};
    std::map<int, PT*> map2;
    for ( auto& el: arr2) { map2[el.first]=&el;}

    // fast access of the sorted map to get to the unsorted elements and modify them there:
    map2[5]->second="five five";

    std::cout << "sorted combination" << std::endl;
    for( auto& el:map2){ std::cout << el.first << " " << el.second->second << std::endl; }
    std::cout << "unsorted direct" << std::endl;
    for( auto& el:arr2){ std::cout << el.first << " " << el.second<<std::endl; }

}

Using a sorted container type to output unsorted elements is simply impossible.

How to iterate std::map values in my own order / the order they were inserted?

2 Answers2