CODEWITHSUNDEEP
c++stl
Rafi Kamal
Rafi Kamal

Reputation: 4600

std::set elements vanishes away

I've created a std::set in the following code where elements are kept sorted based on an array.

int weight[] = {0, 1, 58, 21, 10, 21, 24};

struct Comp
{
    public:
    bool operator() (const int &a, const int &b) const
    {
        if (weight[a] == weight[b])
            return a < b;
        else
            return weight[a] < weight[b];
    }
};
set<int, Comp> s;

Surprisingly, when I change any element in the weight array, corresponding element in the set vanishes away. Here is my testing function:

void print()
{
    printf("Elements = ");  
    for(int i = 1; i <= 6; i++)
        if(s.find(i) != s.end())
            printf("%2d ", i);;
    printf("\n");
}

int main()
{   
    for(int i = 1; i <= 6; i++)
        s.insert(i);

    print();
    weight[2] = 1;
    weight[5] = 15;
    print();

    return 0;
}

Output:

Elements =  1  2  3  4  5  6  
Elements =  1  3  4  6

I'm using gcc 4.6.3 in buntu.

Upvotes: 1

Views: 71

Answers (2)

Preet Kukreti
Preet Kukreti

Reputation: 8607

As a corollary of what Andy Prowl quoted, you would need to regenerate a new set every time you change your weight array

Upvotes: 1

Andy Prowl
Andy Prowl

Reputation: 126422

Per Paragraph 23.2.4/3 of the C++11 Standard on requirements of associative containers:

The phrase “equivalence of keys” means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false. For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value.

Since you are not fulfilling this precondition by changing the weights (and your comparator uses those weights to define an ordering on elements of your set), your program has Undefined Behavior.

Upvotes: 6

Related Questions