Quickly finding array element by pointer

0

I have an array of strings where each string can also be clearly identified by a unique pointer assigned to it. The order of the elements in that array often changes, for example because of sorting.

I want to be able to quickly find the numeric index of an array item just from its accompanying pointer. For example, after sorting the array in the code below, I'd like to have 0 for 0xfeedface, 1 for 0xc0decafe and 2 for 0xdeadbeef. Of course, I don't want to iterate over all elements and manually compare the pointer values because that would be too slow in the real life application. So how can I do that please?

I need a solution that still allows me to use std::sort to sort the items and I also don't have C++11 on my target platform so the solution should not require C++11 or higher. Thanks for your help!

#include <iostream>
#include <string>
#include <vector>
#include <array>

class RowItem
{
public:
   RowItem(std::string text, void *ptr) : m_text(text), m_ptr(ptr) {}
   std::string GetText() {return m_text;}
private:
   std::string m_text;
   void *m_ptr;
};
    
class RowCmp
{
public:
   RowCmp() {}
                    
   bool operator()(RowItem &first, RowItem &second) const
   {
    return first.GetText().compare(second.GetText()) < 0;   
   }
};

int main()
{   
    std::vector<RowItem> v;
    RowItem one("C\n", (void *) 0xdeadbeef), two("B\n", (void *) 0xc0decafe), three("A\n", (void *) 0xfeedface);
    
    v.push_back(one);
    v.push_back(two);
    v.push_back(three);
    
    std::sort(v.begin(), v.end(), RowCmp());                    
    
    for(size_t k = 0; k < v.size(); k++) std::cout << v[k].GetText();       

    return 0;
}
c++
arrays
algorithm
asked on Stack Overflow May 13, 2021 by Andreas • edited May 13, 2021 by CSBigSur

1 Answer

1

This is what I came up with after Paul's explanations in the comments. It seems to do the trick. As suggested by Paul, it doesn't sort the original vector but keeps that as it is. Since the positions in the original vector now stay the same, we can use a simple map to map the pointer values to the corresponding index.

All that's left to do now is to merely sort an array of indices referencing the strings in the original vector. After that is done we can easily find the new position of an item using its pointer value by just peeking into the sorted indices vector.

In code, it looks like this:

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <map>
#include <algorithm>

class RowItem
{
public:
   RowItem(std::string text, void *ptr) : m_text(text), m_ptr(ptr) {}
   std::string GetText() const {return m_text;} 
private:
   std::string m_text;
   void *m_ptr;
};

class RowCmp
{
public:
   RowCmp(std::vector<RowItem> &v) : m_v(v) {}
                    
   bool operator()(int first, int second) const
   {
    return m_v[first].GetText().compare(m_v[second].GetText()) < 0;     
   }
   
private:
   std::vector<RowItem> m_v;   
};

int main()
{   
    std::vector<RowItem> v;
    std::vector<int> index;
    RowItem one("C\n", (void *) 0xdeadbeef), two("B\n", (void *) 0xc0decafe), three("A\n", (void *) 0xfeedface);

    index.push_back(0);
    index.push_back(1);
    index.push_back(2);
    
    v.push_back(one);
    v.push_back(two);
    v.push_back(three);
    
    std::map<unsigned __int64, int> pmap;
    pmap[0xdeadbeef] = 0;    
    pmap[0xc0decafe] = 1;   
    pmap[0xfeedface] = 2;   
            
    std::sort(index.begin(), index.end(), RowCmp(v));                   
    
    for(size_t k = 0; k < v.size(); k++) std::cout << v[index[k]].GetText();        

    std::cout << "Deadbeef at: " << index[pmap[0xdeadbeef]] << "\n";
    std::cout << "Codecafe at: " << index[pmap[0xc0decafe]] << "\n";
    std::cout << "Feedface at: " << index[pmap[0xfeedface]] << "\n";
                
    return 0;
}
answered on Stack Overflow May 14, 2021 by Andreas • edited May 14, 2021 by Andreas

User contributions licensed under CC BY-SA 3.0