How to insert the objects in a map keeping them sorted

Question

hi I am working on a c++ program to insert certain objects which has string as an attribute into a map. How to insert the objects keeping them sorted alphabetically

The code below is sample code for vector. I need to implement the same using map

    Word *WordVector::insert(const string text){
    Word newWord(text);
    if(data.size()==0)
    {
        data.push_back(newWord);
    }

    else{
        auto insert_itr = std::lower_bound(data.begin(), data.end(),newWord);
        if(insert_itr==data.end()||*insert_itr!=newWord){
            data.insert(insert_itr, newWord);
        }
        else newWord.increaseCount();
    }
    return &newWord;
}

I am new to c++ so please excuse if silly errors. Thanks for any help in advance.

Also this code is giving me a vector size greater than expected. Any insights would be helpful :)

`std::map` is always sorted. There is also `std::unordered_map`. — DimChtz, Nov 09 '17 at 10:41
Map is a sorted container. You might want to use a `std::set` where keys and values are the same thing. — Ron, Nov 09 '17 at 10:43
Can you specify the question? What object do you want to insert? Do you want to insert the string of the object as a key? — FloIsAwsm, Nov 09 '17 at 10:46
[This is the same assignment](https://stackoverflow.com/questions/47193727/how-to-insert-and-sort-a-vector-of-objects-with-unique-entries-in-c#comment81336798_47193727). Same code, same mistakes, even the mistake of returning the address of a local variable. — PaulMcKenzie, Nov 09 '17 at 10:57

Caleth · Answer 1 · 2017-11-09T11:17:45.557

It looks like you just need a std::map<std::string, int>.

class WordContainer
{
    std::map<std::string, int> words;
    public:
    void insert(const std::string & text)
    {
        ++words[text];
    }
    int count(const std::string & text)
    {
        return words[text];
    }
}

Original text about how to make a map of a new type:

Let's imagine you have a 'struct Thing', e.g.

struct Thing
{
    std::string name; // We need to keep Things in alphabetical order by name
    int other_member; // etc
};

Now if we try to use a std::map<Thing, T> like this, we will get a compilation error, something like:

/usr/local/include/c++/7.2.0/bits/stl_function.h:386:20: error: no match for 'operator<' (operand types are 'const Thing' and 'const Thing')
       { return __x < __y; }
                ~~~~^~~~~

This is because we haven't specified to our map how to order Things, and the default of using < doesn't find a match for Things either.

So we need a comparison:

struct Thing_less
{
    bool operator()(const Thing & lhs, const Thing & rhs)
    {
        return lhs.name < rhs.name;
    }
}

And we use this as part of the map type:

int main() {
    std::map<Thing, double, Thing_less> things;
    things[{ "First", 1 }] = 1.5;
    things[{ "Second", 2 }] = 3.14;
    things[{ "Third", 3 }] = 0.0;
    things[{ "Forth", 4 }] = 100.1;

    for (auto & pair : things)
    {
        std::cout << pair.first.name << pair.second << "\n";
    }

    return 0;   
}

We get the result:

First 1.5
Forth 100.1
Second 3.14
Third 0

How to insert the objects in a map keeping them sorted

1 Answers1