STL map to find the first non repeatable character

Question

I have written a small C++ program to keep a count of the alphabets. I am using stl map for the same,

Interestingly, i am not getting the list as it appeared in the input. For example for the word TESTER, my program should give

T  2
E  2
S  1
R  1

But its giving,

change in the position of the alphabets,

I want the o/p of the alphabets as it appeared in the input. Please help me if i am missing anything.Here is my code

#include<iostream>
#include<map>

using namespace std;

int main()
{
    char *str = "TESTER";
    map<char,int> checkmap;
    map<char,int>::iterator p;
    int i;
    while( *str != '\0' )
    {
        p = checkmap.find(*str);
        i = p->second;
        if(p == checkmap.end())
        {
            checkmap.insert(std::make_pair(*str,++i));
        }
        else
        {
            p->second = ++(p->second);
        }
    str++;
    }
    for(p=checkmap.begin(); p!=checkmap.end(); p++)
    {
        /*if(p->second == 1)
        {
            cout<<(*p).first<<endl;
        }*/
        cout<<p->first<<"\t"<<p->second<<endl;
    }

    return 0;
}

possible duplicate of [A std::map that keep track of the order of insertion?](http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion) — bolov, May 28 '15 at 10:39
You can use an array instead of a map since characters are considered as integers. — Brahim, May 28 '15 at 11:19

score 5 · Accepted Answer · answered May 28 '15 at 10:42

5

Here is shown an approach how it can be done

#include <iostream>
#include <map>
#include <cstring>

int main() 
{
    const char *str = "TESTER";

    auto order = [&]( char c1, char c2 )
    {
        return ( std::strchr( str, c1 ) < std::strchr( str, c2 ) );
    };

    std::map<char, int, decltype( order )> m( order );

    for ( const char *p = str; *p; ++p ) ++m[*p];

    for ( const auto &p : m ) std::cout << p.first << ' ' << p.second << std::endl;
    std::cout << std::endl;

    return 0;
}

The program output is

T 2
E 2
S 1
R 1

answered May 28 '15 at 10:42

Vlad from Moscow

301,070
26
186
335

@juanchopanza I simply repeated my old answer to some other similar question. The only difference is that there was used an std:;string object instead of the string literal. So instead of standard function strchr I used member function find.:) – Vlad from Moscow May 28 '15 at 10:51
It's somewhat of a pity that the `order` lambda is so expensive (O(N) per invocation). – MSalters May 28 '15 at 11:56
@MSalters What can you suggest? – Vlad from Moscow May 28 '15 at 12:11
`std::strchr(str,c)` can be memoized. If I would have had a simple suggestion how to do that, I'd offer it. But I'm afraid you're going to need a `size_t[UCHAR_MAX]` and that in turn means your lambda has to become a stateful functor. – MSalters May 28 '15 at 12:33

score 1 · Answer 2 · edited May 23 '17 at 11:58

1

You're missing that std::map has its own internal ordering, which is completely independent of the order in which elements are added. As you can see from your example, it is ordered alphabetically. This is in increasing order of the value of the char key.

Also note that your map manipulations are overly complex. All you need to do is

char *str = "TESTER";
map<char,int> checkmap;

while( *str != '\0' )
{
    checkmap[*str]++;
    ++str;
}

The while can be collapsed further if you're into that kind of thing:

while( *str != '\0' ) checkmap[*str++]++;

For the general problem of mapping values while maintaining insertion order, see A std::map that keep track of the order of insertion?

edited May 23 '17 at 11:58

Community

1
1

answered May 28 '15 at 10:19

juanchopanza

223,364
34
402
480

Thanks @juanchopanza Is there any way i can get the alphabets as it appeared in the input? – Rndp13 May 28 '15 at 10:21
1

@Rndp13 Not trivially. You could push elements into a vector of `pair`, and only push new elements if the pair's first element does not already exist. – juanchopanza May 28 '15 at 10:23

score 0 · Answer 3 · answered May 28 '15 at 10:38

0

There is no way to keep track of the order in which elements are added to map. To get the same order it would be advisable to use std::vector<std::char, int> and then update the same.

answered May 28 '15 at 10:38

bhavesh

1,343
2
14
23

STL map to find the first non repeatable character

3 Answers3