如何将元素添加到排序列表...？ （C ++） [英] How to add elements to a sorted list ...? (C++)

问题描述

我刚刚与我的std ::向量第一次接触，现在我想改变我的使用普通的C风格的数组坏习惯。我发现的std ::列表是当它涉及到分拣使用的容器。不过，我不是100％如何实现以下目标：

I just had my first contact with std::vector and now I want to change my bad habit of using plain C-style arrays. I found that std::list is the container to use when it comes to sorting. However, I am not 100% how to accomplish the following:

我做了一些计算，其结果取决于两个指​​标（i和j）。最终我只在100最小的结果（不一定是100，但是可以肯定比我的计算值，M *的总数小得多N的低于code）感兴趣。

I am doing some calculations whose outcome depends on two indices (i and j). In the end I am only interested in the 100 smallest results (not necessarily 100, but for sure much smaller than my total number of calculated values, m*n in the below code).

const int L = 100;
int i_list[L];
int j_list[L];
double value_list[L];

for (int i=0;i<m;i++){
    for (int j=0;j<n;j++){
        double x = doSomeCalculations(i,j);
        insertTheValueAndIndices(i,j,x,i_list,j_list,value_list);
    }
}

完成后，VALUE_LIST应该包含最小的100个值（升序）和I_LIST / j_list相应的指数。我有insertValues​​AndIndices（）的工作版本，但我使用普通阵列和插入新的价值观的最没有效率的方法。在写我认识到，我其实有两个不同的问题：

After completion, value_list should contain the 100 smallest values (increasing order) and i_list / j_list the corresponding indices. I have a working version of the "insertValuesAndIndices()", but there I use plain arrays and the most inefficient way of inserting new values. While writing I realize that i actually have 2 distinct questions:

1. 计算的值（M * N）的数量远远大于我想保留在列表中的号码，从而简单地将所有值，并在最后一次排序做大是不是一个真正的选择。在另一方面，我需要以正确的顺序，结果只在末尾，这样也许有排序列表中只有一次的方式。是否有任何标准聪明而有效的方式做这样的排序？

1. The number of computed values (m*n) is by far bigger than the number I want to keep in the list, thus simply keeping all values and sorting only once in the end is not really an option. On the other hand, I need the results in the right order only in the end, so maybe there is a way of sorting the list only once. Is there any "standard" clever and efficient way do to this kind of sorting?

即使我能存储所有的结果和事后做了排序，我不知道如何使用的std :: list.sort（）来获得指标的阵列以正确的顺序。什么来到我的脑海里是定义包含结果的一些类和两个指数，把这些元素在一个列表中，然后使用该检查只值来进行排序的比较器。不过，也许还有一个更简单的方法做同样的？

Even if I could store all results and do the sorting afterwards, I am not sure how to use the std::list.sort() to get the arrays of indices in the right order. What came to my mind is to define some class containing the result and the two indices, put those elements in a list and then use a comparator that checks only the value to do the sorting. However, maybe there is a more straightforward way to do the same?

＆干杯放大器;在此先感谢

Cheers & Thanks in advance

推荐答案

感谢您的意见。由于我的帖子没有说明一个明确的问题，但它是相当展示我如何解决我的问题的无知;），我想我张贴的结论和一个工作示例...

Thanks for you comments. As my post does not state a single well defined question, but it was rather demonstrating my ignorance of how to solve my problem ;), I want to post my conclusions and a working example...

首先，感谢澄清，认为性病::名单是容器，当谈到排序用
是不正确的。正如例如指出由詹姆斯·观世，性病::向量做这项工作为好。其次，我真的没有之类的矢量如果我只是在正确的地方插入新值。此外，还有对我如何获得指数也进行排序和这里的想法没有异议是我的解决方案：

First of all, thanks for clarifying, that "std::list is the container to use when it comes to sorting" is not true. As pointed out e.g. by James Kanze, std::vector does the job as well. Second, I really do not have to "sort" the vector if I just "insert" new values at the right place. Further, there was no objection towards my idea of how to get the indices also sorted and here is my solution:

#include <cfloat>
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

struct MyValue{
    MyValue(double v,int f,int s):value(v),first(f),second(s){}
    double value;
    int first;
    int second;
};
bool compareValues(const MyValue a,const MyValue b){return a.value < b.value;}
void insertMyValue(std::vector<MyValue>* v,MyValue x,int maxSize){
    v->insert(std::lower_bound(v->begin(),v->end(),x,compareValues),x);
    if (v->size()>maxSize){v->erase(v->end()-1);}
}
void main(){
    const int imax = 10;
    const int jmax = 10;
    const int Nmax = 30;
    std::vector<MyValue> results;
    results.reserve(Nmax+1);
    // Fill the vector
    for (int i=0;i<imax;i++){
        for (int j=0;j<jmax;j++){
            double result = i*(j+0.1);
            insertMyValue(&results,MyValue(result,i,j),Nmax);
        }
    }
    // Print it
    for (std::vector<MyValue>::iterator it = results.begin();it<results.end();it++){
        cout << (*it).first << " " << (*it).second << " " << (*it).value << endl;
    }
}

这篇关于如何将元素添加到排序列表...？ （C ++）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！