C++ Behavior of set range constructor?

Question

If I have a vector which has many duplicate elements,then I construct a set from this vector .

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main ()
{
    vector<pair<int,int> > myvec={{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}};
    auto comp=[](pair<int,int> a,pair<int,int> b){return a.first<b.first;};
    set<pair<int,int>, decltype(comp)> myset(myvec.begin(),myvec.end(),comp);
    for (auto p:myset)
        cout<<p.second<<endl;
    return 0;
}

My question is, is it guaranteed that these elements will be insert to the set by the order of the vector ,like :

for (auto p:myvec)
myset.insert(p);

BTW, for (auto p : myvec) should be for (const auto& p : myvec) in this case, for betterment. — iammilind
– iammilind, Commented Apr 18, 2016 at 5:26
Two questions occur to me here: Firstly, have you tried looking at the documentation? Maybe the constructor of a set from an iterator range is defined in a way that answers your question? Secondly, set orders its elements anyway, so the order shouldn't make a difference. So why do you care? — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Apr 18, 2016 at 5:32
Whenever you insert an element (or multiple elements) to the set, it's always ordered using your comparison function. And yes, like Ulrich Eckhardt points out, this can be found in documentation. — Ternvein
– Ternvein, Commented Apr 18, 2016 at 5:35
@UlrichEckhardt He cares because he wants to confirm the iterator sequence will be scanned from beginning to end, as it would be if done manually by way of a for-loop or other logic control loop. With that comparator, the content of the set would be be different if every element of the iteration were guaranteed to be visited once (and obviously, only once), but the sequence was not guaranteed visited in-order from beginning to end. Pretty sure the OP knows the set will be ordered regardless. — WhozCraig
– WhozCraig, Commented Apr 18, 2016 at 5:42
You should rethink your data structure needs. If the order in which an item is added to the set matters, you probably need a different data structure -- maybe std::multiset. — R Sahu
– R Sahu, Commented Apr 18, 2016 at 15:22

Humam Helfawi · Accepted Answer · 2016-04-18 05:50:35Z

1

From MSVC implementation of std::set :

template<class _Iter>
void insert(_Iter _First, _Iter _Last)
{   // insert [_First, _Last)
    _DEBUG_RANGE(_First, _Last);
    for (; _First != _Last; ++_First)
        this->emplace(*_First);
}

This method is called from the constructor you used. So, it is guarantees by this implementation. However, I am not sure that this behavior is guaranteed by the standard.

IMO and for readability, I advise that you state the order you want clearly in the comparer like this:

auto comp=[](std::pair<int,int> a,std::pair<int,int> b){
    if(a.first==b.first){
        return a.second<b.second;
    }
    return a.first<b.first;
};

answered Apr 18, 2016 at 5:50

Humam Helfawi

20.4k18 gold badges92 silver badges170 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sameerkn · Accepted Answer · 2016-04-18 05:53:43Z

1

"I have a vector which has many duplicate elements". By this assuming that you are only concerned with the first component of pair as its evident from your code. Since 'set' is used then, all the elements inside 'set' will be unique and in Strict Weak Ordering i.e increasing order (as per your 'comp' Binary Predicate). So if vector has elements(considering first part of pair) already in sorted order then, its guaranteed that elements will be inserted in set by the order of the first part of pairs in the vector.

Final value in myset = {1,1}{2,1}{3,1}.

answered Apr 18, 2016 at 5:53

sameerkn

2,2591 gold badge13 silver badges13 bronze badges

4 Comments

iouvxz Over a year ago

Any documentary support ?

sameerkn Over a year ago

@iouvxz: unique element constraints can be checked in introduction part at "cplusplus.com/reference/set/set". If there is an element with value "abc" in set and again if a new element with same value "abc" is inserted in set then, the new element won't get inserted in set. Since you are comparing only the first part of pairs therefore the value of elements is same as first part of pairs.

iouvxz Over a year ago

My question is that is it guaranteed that the elements will be inserted from myvec.begin() to myvec.end()? What if the implementation start insert from the middle ?if I get a sorted array and want to build a set from it ,I will definitely start insert from the middle.

iouvxz Over a year ago

What if the compiler construct myvec to several small sets and merge the them into a final result ?That will be easy to optimize on a multi-core computer .

Collectives™ on Stack Overflow

C++ Behavior of set range constructor?

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related