Suitable data structure to quickly retrieve two different parameters

user_15078875 0
Viewed 64

I have some pairs std::pair<X, Y>. X is unique and will never change and Y will be regularly updated. The pairs need to be sorted based on Y but I also want quick retrieval of a X to update a Y.

Until now I used std::set<std::pair<X, Y>, CustomCompare> to get the sorted list based on Y. However updates are now slow, I think in the worst case I need to run through the whole set to find the correct X. Am I right?

Is there any datastructure that supports sorting using Y plus quick (O(logn) or less) retrieval of X? I'm open to the idea of using a supporting data structure or splitting up X and Y.

EDIT: Maybe an example will clear things up. Let's say X is a name and Y is monthly salary. So a pair could be ("John", 5000). Now I need a list/set of people sorted by the highest salary, for example [("Mary", 8000), ("John", 5000), ("Chris", 2000)]. Additionaly, I need a way to lookup a person (in O(1) or O(logn)), so that I can remove the name-salary pair from the list/set, update the salary and then re-insert the name-salary pair into the sorted list/set. Updates occur very frequently.

data-structures c++
1 Answers

I do not think that one STL container or some nested STL containers can fullfill your requirements.

But I do think that a combination of STL containers could fullfill your requirements. In my proposal, I basically store the data 2 times redundant and connect them with some sort of ID. Like in a database where you build a m:n relation with an additional helper table.

Please see the below source code. It is only a skelleton and needs to be made iterable, but you may get the idea.

The overall performance depends strongly on the single performance of the hash algorithm. I assume O(1) for operations with a std::unordered_map and o(log n) for the std::map.

Sub optimum hashing can of course lead to O(n).

#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <unordered_map>

// Some aliases for easier understanding
using Salary = unsigned int;
using Name = std::string;
using ID = size_t;
using NameAndSalary = std::pair<Name, Salary>;

// New data structure according to given requirements
struct Employees {
    std::unordered_map<ID, NameAndSalary> lookup{}; // O(1)

    std::unordered_map<Name, ID> names{};           // O(1)
    std::map<Salary, ID> salaries{};                // O(log n)

    void add(Name&& n, Salary&& s) {
        ID newID = lookup.size();
        names[n] = newID;                           // O(1)
        salaries[s] = newID;                        // O(log n)
        lookup[newID] = { n,s };                    // O(1)
    }
    Salary getSalaryViaName(const Name& n)  { return lookup[names[n]].second; } // O(1) O(1)
    Name getNamebySalary(const Salary& s) { return lookup[salaries[s]].first; } // O(1) O(log n)
};
// Some test code
int main() {

    Employees employees{};
    // Populate struct
    employees.add("John", 456);
    employees.add("Paul", 345);
    employees.add("Ringo", 234);
    employees.add("George", 123);

    // Iterate
    for (const auto& [salary, id] : employees.salaries)  
        std::cout << "Salary: " << salary << "\t\t Name: " << employees.getNamebySalary(salary) << '\n';
    std::cout << '\n';
    for (const auto& [name, id] : employees.names)  
        std::cout << "Name: " << name << "\t\t Salary: " << employees.getSalaryViaName(name) << '\n';
}

Will not work with double names / salaries. That would need to be reworked. Also, slow update . . .

Please comment, if that is not what you expected. In that case I will delete the answer.

user_96660180
Related