What data structure is better to use for storing and sorting <int, int> structure?

Question

I have such structure with ids and their count:

product[38] = 10;
product[22] = 7;
product[39] = 18;

I need to use some structure for it. But not sure what should serve better (map, unordered_map, set, vector).

I was trying to use:

map<int, int> product;

But not sure is it the best choice. The only thing that I should do with it - sorting.

As a result I need:

product[39] = 18;
product[38] = 10;
product[22] = 7;

UPD: Sort by value.

Answer 1

A std::map is fine in this case, considering that you are mapping IDs to a count.

For future reference:

Answer 2

If i had to do this in the confines of your proposed usage (maintain a key-map for quick counter updates, then dump a sorted result), I would likely use an unordered map and a pointer vector. With this I'm assuming the primary reason you want some indexed-key soluton in the first place is to make data processing significantly quicker when updating counts.

In other words, you're looking to get a good speed-bump out of code that does this:

++product[ id ]; // increment counter for product 'id' in our keyed-container.

But still be able to report output sorted not on id, but rather on the accumulated count of each id. That being said, the following, though a little dense, will do exactly that:

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <iterator>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[])
{
    typedef std::unordered_map<int, int> Products;
    Products product;

    // fill with random data for our test.
    std::srand((unsigned)time(0));
    for (int i=1;i<20;++i)
    {
        product[i] = rand() % 50 + 1;
        cout << setw(3) << i << " ==> " << product[i] << endl;
    }
    cout << endl;


    // now setup a one-shot sort. we're using a vector of
    //  pointers to our map value type
    std::vector<const Products::value_type*> data;
    data.reserve(product.size());
    std::transform(product.begin(), product.end(), std::back_inserter(data),
                   [](const Products::value_type& obj) { return std::addressof(obj); });

    // sort the vector by value (second)
    std::stable_sort(data.begin(), data.end(),
                     [](const Products::value_type* left, const Products::value_type* right)
                     { return left->second < right->second; });

    // results are in the vector as pointers. the original map is unchanged.
    for (auto ptr : data)
        cout << setw(3) << ptr->first << " ==> " << ptr->second << endl;

    return EXIT_SUCCESS;
};

Sample Run

  1 ==> 42
  2 ==> 18
  3 ==> 35
  4 ==> 1
  5 ==> 20
  6 ==> 25
  7 ==> 29
  8 ==> 9
  9 ==> 13
 10 ==> 15
 11 ==> 6
 12 ==> 46
 13 ==> 32
 14 ==> 28
 15 ==> 12
 16 ==> 42
 17 ==> 46
 18 ==> 43
 19 ==> 28
 20 ==> 37

  4 ==> 1
 11 ==> 6
  8 ==> 9
 15 ==> 12
  9 ==> 13
 10 ==> 15
  2 ==> 18
  5 ==> 20
  6 ==> 25
 14 ==> 28
 19 ==> 28
  7 ==> 29
 13 ==> 32
  3 ==> 35
 20 ==> 37
  1 ==> 42
 16 ==> 42
 18 ==> 43
 12 ==> 46
 17 ==> 46

I've used this method in the past because it is swimmingly-efficient for more complex structures that are expensive to copy into temporary containers for sorting. That the ending pointer-vector references the real data in the map is a nicety that, while probably overkill for this specific problem, certainly has reaps of benefits as a general solution.

That being said, if all you want is an int-to-int dump, sorted on second-int rather than your map key, this will likewise do the trick, though it does replicate data out of your container to accomplish the end-goal:

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <iterator>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[])
{
    typedef std::unordered_map<int, int> Products;
    Products product;

    // fill with random data for our test.
    std::srand((unsigned)time(0));
    for (int i=1;i<20;++i)
    {
        product[i] = rand() % 50 + 1;
        cout << setw(3) << i << " ==> " << product[i] << endl;
    }
    cout << endl;

    // copy the values from the map to a sort bed.
    std::vector<std::pair<int,int>> vals;
    std::copy(product.begin(), product.end(), back_inserter(vals));
    std::stable_sort(vals.begin(), vals.end(),
        [](const std::pair<int,int>& left, const std::pair<int,int>& right)
        { return left.second < right.second; });

    // dump to stdout
    for (auto val : vals)
        cout << setw(3) << val.first << " ==> " << val.second << endl;

    return EXIT_SUCCESS;
}

Sample Output

  1 ==> 48
  2 ==> 30
  3 ==> 25
  4 ==> 32
  5 ==> 34
  6 ==> 21
  7 ==> 26
  8 ==> 6
  9 ==> 50
 10 ==> 28
 11 ==> 50
 12 ==> 32
 13 ==> 35
 14 ==> 17
 15 ==> 33
 16 ==> 30
 17 ==> 13
 18 ==> 1
 19 ==> 50

 18 ==> 1
  8 ==> 6
 17 ==> 13
 14 ==> 17
  6 ==> 21
  3 ==> 25
  7 ==> 26
 10 ==> 28
  2 ==> 30
 16 ==> 30
  4 ==> 32
 12 ==> 32
 15 ==> 33
  5 ==> 34
 13 ==> 35
  1 ==> 48
  9 ==> 50
 11 ==> 50
 19 ==> 50

Answer 3

I usually do in following way:

create a class/struct of two int member

struct int_pair{
     int key;
     int value;
}

then create a

   vector<int_pair> myvector;

then create two bool compare functions:

 bool sort_by_key(int_pair left, int_pair right){
      return left.key<right.key;
 }

 bool sort_by_value(int_pair left, int_pair right){
     return left.value<right.value;
 }

then sort using std::sort and those bool functions.

 std::sort (myvector.begin(), myvector.end(), sort_by_key); 

p.s: sorry about the formatting. typing from mobile.

Answer 4

You could simply use boost.bimap. Its is a little work to understand it but its worth and I think its fits exactly your use case.

Answer 5

You may want to make a struct or std::pair and sore them in std::vector

std::vector<std::pair<int, int>> product;

product.push_back(std::pair<int,int>(38, 27));
product.push_back(std::pair<int,int>(22, 7));
product.push_back(std::pair<int,int>(39, 18));

sort by value:

std::sort(product.begin(), product.end(), 
  [](const std::pair<int,int>& p1, const std::pair<int,int>& p2){ return p1.second < p2.second; });