2

I have a constant integer vector const vector<int> v = {5,1,3,2,4} . How can I sort it without using any extra memory like vector, array etc.

Peter - Reinstate Monica
  • 15,048
  • 4
  • 37
  • 62
Tanmoy Datta
  • 1,604
  • 1
  • 17
  • 15
  • 1
    Depending on compiler and OS, `const std::vector v = {5,1,3,2,4};` could end up in a segment of memory configured as read-only, in which case it can't modified. – rcgldr Oct 17 '19 at 12:26
  • @rcgldr That is true, but the *data pointed to* is syntactically not part of the vector and has the type given in its declaration, in this case `int` (not `const int`). Objects of type `int` are generally writable though ;-). – Peter - Reinstate Monica Oct 21 '19 at 16:02
  • @PeterA.Schneider - The example is using a literal, which is normally an array of constant elements. In the case of Visual Studio 2015, looking at the produced assembly, the array of data ends up in the const segment – rcgldr Oct 21 '19 at 17:54

3 Answers3

5

You can't.

Your vector is immutable. It cannot be changed. There is no [legal] way to re-order its contents.

By extension, if you want a sorted version of its contents, you will need a new vector, which needs more memory.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • But I have done it using these two lines of code`vector*temp=(vector*)&v;` `sort(temp->begin(),temp->end())` . Then can you please explain me how is it possible ? I have done it in c++11. Thanks in advance. – Tanmoy Datta Oct 16 '19 at 20:29
  • @TanmoyDatta Either NathanOliver's answer is correct or this one is correct and you have Undefined Behaviour (and UB can do everything, starting from seemingly working correct through crashing the application to [demons flying out of your nose](http://catb.org/jargon/html/N/nasal-demons.html)). Even if it is valid, I'd suggest treating it as invalid, to avoid discussions like occurred here when someone will come across your code. – Yksisarvinen Oct 16 '19 at 20:36
  • @Yksisarvinen https://stackoverflow.com/questions/58419749/how-to-sort-a-constant-vector-without-using-any-extra-memory/58419750?noredirect=1#comment103182443_58419750 (basically I'm cheating but on this topic I'm kinda fine with it) – Lightness Races in Orbit Oct 16 '19 at 20:43
  • 1
    @TanmoyDatta What is possible and appears to work, and what is legal/valid and will always work, are two different things. "It works for me" is _never_ enough proof in C++. However, do see my comment above because I'm cheating a bit here. (If this causes much more confusion I'll probably delete but let's see how it goes) – Lightness Races in Orbit Oct 16 '19 at 20:44
  • I was solving an interview problem in the interviewbit site. For solving that problem I need some way to do this. Then I use this idea and I solved that problem successfully so that I share this idea here. So now may I delete my answer or this question ?? – Tanmoy Datta Oct 16 '19 at 20:50
  • @Tanmoy: Why would you delete anything? Don't delete things. – Lightness Races in Orbit Oct 16 '19 at 20:51
  • @LightnessRacesinOrbit: After seeing those downvotes I thought that I am an idiot, it's better to delete it. Now I will not delete anything. Thank you for your opinion. – Tanmoy Datta Oct 16 '19 at 20:54
  • Which of vector's members -- which, as you correctly state, are declared const -- is changed by sorting its data? – Peter - Reinstate Monica Oct 21 '19 at 12:28
  • @PeterA.Schneider None of the vector's direct members is physically changed. Feel free to read all the conversation on this page; we covered the topic well last week. – Lightness Races in Orbit Oct 21 '19 at 14:32
  • I had read this page pretty much in its entirety but not the part which moved to chat; I wish you would include the relevant parts of the discussion, including in chat, in this answer in order to give it context (and probably qualify or change its conclusion). The way your answer is standing now everybody (including you) appears to agree that it is technically wrong. – Peter - Reinstate Monica Oct 21 '19 at 15:40
3

As you have shown in your answer the solution is to cast away const from the vector, ie:

vector<int>&temp = const_cast<vector<int>&>(v);
sort(temp.begin(), temp.end());

This works because you are not changing the state of the vector. The only thing standard says about undefined behavior and casting away const is in [dcl.type.cv]/4

Any attempt to modify ([expr.ass], [expr.post.incr], [expr.pre.incr]) a const object ([basic.type.qualifier]) during its lifetime ([basic.life]) results in undefined behavior. [...]

Any nothing in [expr.ass], [expr.post.incr], and [expr.pre.incr] applies to this example so you are not considered to be modifying the object.

I do feel this is a defect though. The order of the elements matter for comparison operators so this modification should apply.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • one bit that keeps me puzzling: is it possible to implement a contrived but conforming `std::vector` that uses `const int*` as `data` and only falls back to `int*` once you modify elements or the vector itself? If thats the case...hope you get what I am aiming for. Or am I just missing that it is specified to have `int*` as data? – 463035818_is_not_an_ai Oct 16 '19 at 19:23
  • @FrançoisAndrieux thats why the fallback to `int*` is need when you modify it. The vector does not know if it is `const` but it knows when it is modified – 463035818_is_not_an_ai Oct 16 '19 at 19:25
  • 1
    @formerlyknownas_463035818 The data type of `cv-qualifer std::vector` is `T*` The *cv-qualification* of the vector does not play into the type of the elements inside it. – NathanOliver Oct 16 '19 at 19:25
  • @NathaonOliver in case it is non-const it can still pretend to have `T*` as value_type when it actually stores `const T*`, once you modify it could switch back to storing `T*`. From outside you wouldnt notice other than this hack being ub, unless I miss something – 463035818_is_not_an_ai Oct 16 '19 at 19:27
  • @formerlyknownas_463035818 It sounds like you might be thinking of "copy on write" where an initialized but unmodified vector just has a pointer to some static version of the data. If this is what you mean, time complexity and iterator invalidation rules would likely forbid such a strategy. Edit : In practice, I don't think it's possible to use anything but a non-const pointer, though it still sounds like an implementation detail and in theory is up to the implementer (even if only 1 solution is possible). – François Andrieux Oct 16 '19 at 19:28
  • well anyhow, I think this is going too discussy-in-comments. I'll have to do some reading to convince myself. Thanks for the references – 463035818_is_not_an_ai Oct 16 '19 at 19:28
  • @formerlyknownas_463035818 I don't think that would be legal, but you'd have to detail what you are thinking in some code for me to give you a better answer. – NathanOliver Oct 16 '19 at 19:31
  • its getting late here, but I will definitely come back to this at some point. Maybe I can manage to write up a question to clear up my doubts – 463035818_is_not_an_ai Oct 16 '19 at 19:32
  • @formerlyknownas_463035818 Sure. Just give me a ping. Some more food for thought: https://timsong-cpp.github.io/cppwp/container.requirements#general-8 Basically the storage type is the pointer type returned by the allocator and in this case (since it uses the default allocator) that is `T*`. You'd have to check the allocator requirements to see if `const T*` is allowed. – NathanOliver Oct 16 '19 at 19:34
  • I think this is basically the same question, though the answer may be a bit short: https://stackoverflow.com/questions/55977942/modifying-element-of-const-stdvectort-via-const-cast – walnut Oct 16 '19 at 19:35
  • @uneven_mark It does. I'm really hesitant to close as a dupe though. – NathanOliver Oct 16 '19 at 19:37
  • TBH I'd be okay with it. – Lightness Races in Orbit Oct 16 '19 at 20:52
  • @LightnessRacesinOrbit If you're comfortable with it go ahead. It is two sides of the same coin, it's just coming from opposite directions so it makes me hesitate. – NathanOliver Oct 16 '19 at 20:54
  • If you don't feel comfortable casting away const from the vector you can simply sort `temp.data()`, right? It should return `T*`, in this case `int*` (non-const). – Peter - Reinstate Monica Oct 21 '19 at 12:25
  • 1
    @PeterA.Schneider [`data()`](https://en.cppreference.com/w/cpp/container/vector/data) is const qualified so `v.data()` yeilds `const T*` so you would still need to cast. – NathanOliver Oct 21 '19 at 12:27
  • @NathanOliver Ah, I see. I didn't expect that the data pointed to would be declared const but failed to check beforehand. – Peter - Reinstate Monica Oct 21 '19 at 12:48
  • With respect to the "syntactic" vs. "semantic" constness: There is a limit to what the standard can do for you. If you cast away a "semantic" const (e.g. the result of `data()` or `operator[]()`) but expect that logical invariants still hold you just discovered one of the many ways to shoot yourself in the foot. A cast is a sign that you think you know what you are doing ;-). – Peter - Reinstate Monica Oct 21 '19 at 15:55
-1

I have tested using c++11. In my job, it's working fine for me

You can sort any constant container in c++ using a pointer.

In your case, if you want to sort this vector using sort(v.begin(),v.end()) then it will result in some runtime error due to violation of const.

But you can sort your container in following way-

vector<int>*temp=(vector<int>*)&v;
sort(temp->begin(),temp->end());

After this, your constant vector v will be like this - 

const vector<int> v = {1,2,3,4,5}

View of my working code and output

Tanmoy Datta
  • 1,604
  • 1
  • 17
  • 15
  • Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/200983/discussion-on-answer-by-tanmoy-datta-how-to-sort-a-constant-vector-without-using). – Samuel Liew Oct 16 '19 at 22:57
  • If it's important, please edit the info into the question or answers. – Samuel Liew Oct 21 '19 at 21:03