Time-Efficient Sorting of structure in c++

Question

I have a structure

 struct abc
       {
        int p;
        int q;
       }

and a file which gives the value of p and q and the operation that is to be done( insert,delete or modify) and then accordingly the values needs to be maintained in a sorted manner(sort acc to p).
The sequence is

1.Read the line from file
2.If insert, insert in a sorted manner<br>   
  If modify,delete; first remove the element and then sort<br>
3.Repeat step 1<br><br>

I already implemented this with a linked list but is there any other more time-efficient method than this?
I thought of an array(with memcpy-ing to ease the operations),set and vector but implementation wise it seems to be a bit difficult as all the operations has to done.
Would be helpful if i could get an algorithm or snapshot of the code

Answer 1

You shouldn't need to implement many operations.

Define your ordering relation:

bool operator<(const abc& lhs, const abc& rhs) { return lhs.p < rhs.p; }    

Read the data:

std::vector<abc> data;
abc x;
while (whatever >> x.p >> x.q)
{
    data.push_back(x);
}

Sort the data:

std::sort(data.begin(), data.end());

Insert while maintaining the order

abc y = whatever;
data.insert(std::lower_bound(data.begin(), data.end(), y), y);

Answer 2

You can use array of structure to get input and then use built-in sort according to a compare function.

bool compare(struct abc c1,struct abc c2)
{ 
 return c1.p < c2.p;
}


//main
abc arr[n];
for(int i=0;i<n;i++)
{
 cin>>arr[i].p>>arr[i].q;
}
//O(n lg n)
sort(arr,arr+n,compare);