On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana <ary@esperanto.org.ar> wrote:

> On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
>>
>> The basic response to this is, when dealing with containers generically
>> (that is, you know you have a container, but you don't know what type),
>> the "remove this element" operation is not necessarily a good primitive
>> to have.
>>
>> Simply because from the myriad of containers, only some can implement
>> this operation efficiently. Java embeds this operation in the interface,
>> which means any interface you have to a container could potentially use
>> O(n) time to remove that element. Such an innocuous piece of syntax
>> *should* have a cost if it's not efficient IMO.
>>
>> BTW, the original question doesn't provide enough information to say
>> "remove this element." Even in Java, if you aren't using the default
>> comparison, you must use a comparator method to determine which one to
>> remove. If cell.x == x && cell.y == y *is* the comparison operator for
>> the type, then the syntax gets much simpler, because you don't need to
>> pass a specialized comparison function.
>>
>> In dcollections, removing a specific element (using the default
>> comparison operator for that element) on a *fast lookup* container is as
>> simple as:
>>
>> container.remove(container.find(x));
>>
>> Which removes the element x if it's found. However, this is not defined
>> for containers which use O(n) time to search (such as linked list), you
>> must use std.algorithm.find for that:
>>
>> container.remove(find(container[], x).begin);
>>
>> Should work, and takes O(n) time.
>>
>> -Steve
>
> I don't really understand what's wrong with inefficient methods. You can have inefficient methods that are convenient, like removing an element by the default comparison, or giving it a delegate to match the element(s) to remove.
>
> You profile your application. Is that method the bottle-neck? If so, you change it to a more efficient one. If not, you are happy you had that method there, performing in an inefficient way, but which doesn't matter that much compared to, say, opening an SQL connection.
>
> Programmers want to program, fast. They have schedules, they need to deliver. They don't need to always find the best solution. They can find a compromise between "working" and "fast", move on, and later profile and worry about what matters most.
>
> Programmers don't want to fight with the language or think "Oh, so to remove an element I need to use this operation and combine it with that one and with that other one"...

Or use the right container for the job?

Where it really comes into play is generic programming.

Let's say I write some algorithm that removes certain elements from a container:

removeElements(C, T)(C c, T t[]...)
{
   foreach(x; t)
     c.remove(t);
}

What's the complexity of this algorithm?  For a HashSet, for instance, it will be O(n) where n is the number of elements to remove.

But for an ArrayList, it will be O(n*m) where m is the number of elements in c.

So what we get is, an algorithm whose complexity depends on the complexity of an operation that varies *widely*.  What you end up with is things like sorting algorithms which are O(n^2) or even worse.

What omitting those methods from the containers that don't support it does is allow you to make *predictably efficient* generic algorithms.  For example, you know sorting is going to be at most O(nlgn).  I don't care how beautiful the syntax is, a quadratic sort is epic fail, and should be avoided at all costs.

std.container tries to allow having these inefficient methods by changing the name (so algorithms can still claim efficiency by not using those names).  My stance is this makes the API overly complex for very little gain.  If something is inefficient, either don't use it, or use the range interface via std.algorithm.  Why should I write a linear search algorithm when std.algorithm already has done this?

-Steve

On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
> On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana <ary@esperanto.org.ar>
> wrote:
>
>> On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
>>>
>>> The basic response to this is, when dealing with containers generically
>>> (that is, you know you have a container, but you don't know what type),
>>> the "remove this element" operation is not necessarily a good primitive
>>> to have.
>>>
>>> Simply because from the myriad of containers, only some can implement
>>> this operation efficiently. Java embeds this operation in the interface,
>>> which means any interface you have to a container could potentially use
>>> O(n) time to remove that element. Such an innocuous piece of syntax
>>> *should* have a cost if it's not efficient IMO.
>>>
>>> BTW, the original question doesn't provide enough information to say
>>> "remove this element." Even in Java, if you aren't using the default
>>> comparison, you must use a comparator method to determine which one to
>>> remove. If cell.x == x && cell.y == y *is* the comparison operator for
>>> the type, then the syntax gets much simpler, because you don't need to
>>> pass a specialized comparison function.
>>>
>>> In dcollections, removing a specific element (using the default
>>> comparison operator for that element) on a *fast lookup* container is as
>>> simple as:
>>>
>>> container.remove(container.find(x));
>>>
>>> Which removes the element x if it's found. However, this is not defined
>>> for containers which use O(n) time to search (such as linked list), you
>>> must use std.algorithm.find for that:
>>>
>>> container.remove(find(container[], x).begin);
>>>
>>> Should work, and takes O(n) time.
>>>
>>> -Steve
>>
>> I don't really understand what's wrong with inefficient methods. You
>> can have inefficient methods that are convenient, like removing an
>> element by the default comparison, or giving it a delegate to match
>> the element(s) to remove.
>>
>> You profile your application. Is that method the bottle-neck? If so,
>> you change it to a more efficient one. If not, you are happy you had
>> that method there, performing in an inefficient way, but which doesn't
>> matter that much compared to, say, opening an SQL connection.
>>
>> Programmers want to program, fast. They have schedules, they need to
>> deliver. They don't need to always find the best solution. They can
>> find a compromise between "working" and "fast", move on, and later
>> profile and worry about what matters most.
>>
>> Programmers don't want to fight with the language or think "Oh, so to
>> remove an element I need to use this operation and combine it with
>> that one and with that other one"...
>
> Or use the right container for the job?
>
> Where it really comes into play is generic programming.
>
> Let's say I write some algorithm that removes certain elements from a
> container:
>
> removeElements(C, T)(C c, T t[]...)
> {
> foreach(x; t)
> c.remove(t);
> }
>
> What's the complexity of this algorithm? For a HashSet, for instance, it
> will be O(n) where n is the number of elements to remove.
>
> But for an ArrayList, it will be O(n*m) where m is the number of
> elements in c.

But I'm sure in this algorithm I have for this app I'm making, my collection won't have more than 50 elements. So everything will be O(1). I need to remove an element from the collection. I really don't care about the complexity of the operation, because if n is 50, everything is O(1).

Why can't I have an inefficient (for you) remove operation that, for me, will be ok? I don't want to spend 2 hours browsing the ranges algorithms to figure out how to combine them to remove an element...

My point is, as someone else said it in another post: add inefficient operations and tell the programmer so. Then he can decide what to do. If he's sure that that performance penalty is not a big issue for him, he'll be happy to have that method available.

On Wed, 02 Nov 2011 09:17:39 -0400, Ary Manzana <ary@esperanto.org.ar> wrote:

> On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
>> On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana <ary@esperanto.org.ar>
>> wrote:
>>
>>> On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
>>>>
>>>> The basic response to this is, when dealing with containers generically
>>>> (that is, you know you have a container, but you don't know what type),
>>>> the "remove this element" operation is not necessarily a good primitive
>>>> to have.
>>>>
>>>> Simply because from the myriad of containers, only some can implement
>>>> this operation efficiently. Java embeds this operation in the interface,
>>>> which means any interface you have to a container could potentially use
>>>> O(n) time to remove that element. Such an innocuous piece of syntax
>>>> *should* have a cost if it's not efficient IMO.
>>>>
>>>> BTW, the original question doesn't provide enough information to say
>>>> "remove this element." Even in Java, if you aren't using the default
>>>> comparison, you must use a comparator method to determine which one to
>>>> remove. If cell.x == x && cell.y == y *is* the comparison operator for
>>>> the type, then the syntax gets much simpler, because you don't need to
>>>> pass a specialized comparison function.
>>>>
>>>> In dcollections, removing a specific element (using the default
>>>> comparison operator for that element) on a *fast lookup* container is as
>>>> simple as:
>>>>
>>>> container.remove(container.find(x));
>>>>
>>>> Which removes the element x if it's found. However, this is not defined
>>>> for containers which use O(n) time to search (such as linked list), you
>>>> must use std.algorithm.find for that:
>>>>
>>>> container.remove(find(container[], x).begin);
>>>>
>>>> Should work, and takes O(n) time.
>>>>
>>>> -Steve
>>>
>>> I don't really understand what's wrong with inefficient methods. You
>>> can have inefficient methods that are convenient, like removing an
>>> element by the default comparison, or giving it a delegate to match
>>> the element(s) to remove.
>>>
>>> You profile your application. Is that method the bottle-neck? If so,
>>> you change it to a more efficient one. If not, you are happy you had
>>> that method there, performing in an inefficient way, but which doesn't
>>> matter that much compared to, say, opening an SQL connection.
>>>
>>> Programmers want to program, fast. They have schedules, they need to
>>> deliver. They don't need to always find the best solution. They can
>>> find a compromise between "working" and "fast", move on, and later
>>> profile and worry about what matters most.
>>>
>>> Programmers don't want to fight with the language or think "Oh, so to
>>> remove an element I need to use this operation and combine it with
>>> that one and with that other one"...
>>
>> Or use the right container for the job?
>>
>> Where it really comes into play is generic programming.
>>
>> Let's say I write some algorithm that removes certain elements from a
>> container:
>>
>> removeElements(C, T)(C c, T t[]...)
>> {
>> foreach(x; t)
>> c.remove(t);
>> }
>>
>> What's the complexity of this algorithm? For a HashSet, for instance, it
>> will be O(n) where n is the number of elements to remove.
>>
>> But for an ArrayList, it will be O(n*m) where m is the number of
>> elements in c.
>
> But I'm sure in this algorithm I have for this app I'm making, my collection won't have more than 50 elements. So everything will be O(1). I need to remove an element from the collection. I really don't care about the complexity of the operation, because if n is 50, everything is O(1).

Then your specific application can use std.algorithm.find to implement the equivalent.  Only the algorithm body changes, not the usage of the algorithm.

>
> Why can't I have an inefficient (for you) remove operation that, for me, will be ok?

I never said you couldn't (and I've even given examples of such implementations).  It's just not neatly packaged into a method.

But again, if the method is exactly the same as the efficient version for other containers, it becomes *impossible* to design an algorithm that guarantees any sort of complexity.  As I said before, quadratic sort is epic fail, and needs to always be avoided.

I'll give you a scenario:

People often complain that Linked List does not have an opIndex on it.  Yes it's inefficient, but so what?  "I know it's inefficient, let me decide whether it's worth it or not."

So let's say I add it to LinkList.  Those people are happy.

But now, LinkList becomes defined as a *random-access-range* according to std.ranges.  Therefore, std.algorithm.sort(linklist) compiles!  And is now something like O(n^3).

Whereas LinkList already defines a sort method, which uses mergesort (O(nlgn)).  So are you going to realize this when reading someones code and you see:

sort(somelist);

That it's going to be horribly inefficient?  Why shouldn't we strive for a library where such things just don't compile?

> I don't want to spend 2 hours browsing the ranges algorithms to figure out how to combine them to remove an element...

You severely exaggerate the amount of time needed to browse the algorithms.  I wrote an equivalent in less than a minute.  And I don't even look at std.algorithm maybe once every few months (and didn't look at it to write the solution).

> My point is, as someone else said it in another post: add inefficient operations and tell the programmer so. Then he can decide what to do. If he's sure that that performance penalty is not a big issue for him, he'll be happy to have that method available.

The operation is available using std.algorithm.  There is no need to reimplement it as a method, sanctioned by the container.  As I said before, if you find yourself wanting to remove specific elements from a container, perhaps Array is not the smartest choice for a container.  There are plenty of others.

There is something to be said for a language/library that discourages or prevents you from writing dumb code.  It means that I'm that much more confident a piece of code written in that language is more efficient than one written in another language.

-Steve

On 11/2/2011 2:41 PM, Steven Schveighoffer wrote:
> On Wed, 02 Nov 2011 09:17:39 -0400, Ary Manzana <ary@esperanto.org.ar>
> wrote:
>
>> On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
>>> On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana <ary@esperanto.org.ar>
>>> wrote:
>>>
>>>> On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
>>>>>
>>>>> The basic response to this is, when dealing with containers
>>>>> generically
>>>>> (that is, you know you have a container, but you don't know what
>>>>> type),
>>>>> the "remove this element" operation is not necessarily a good
>>>>> primitive
>>>>> to have.
>>>>>
>>>>> Simply because from the myriad of containers, only some can implement
>>>>> this operation efficiently. Java embeds this operation in the
>>>>> interface,
>>>>> which means any interface you have to a container could potentially
>>>>> use
>>>>> O(n) time to remove that element. Such an innocuous piece of syntax
>>>>> *should* have a cost if it's not efficient IMO.
>>>>>
>>>>> BTW, the original question doesn't provide enough information to say
>>>>> "remove this element." Even in Java, if you aren't using the default
>>>>> comparison, you must use a comparator method to determine which one to
>>>>> remove. If cell.x == x && cell.y == y *is* the comparison operator for
>>>>> the type, then the syntax gets much simpler, because you don't need to
>>>>> pass a specialized comparison function.
>>>>>
>>>>> In dcollections, removing a specific element (using the default
>>>>> comparison operator for that element) on a *fast lookup* container
>>>>> is as
>>>>> simple as:
>>>>>
>>>>> container.remove(container.find(x));
>>>>>
>>>>> Which removes the element x if it's found. However, this is not
>>>>> defined
>>>>> for containers which use O(n) time to search (such as linked list),
>>>>> you
>>>>> must use std.algorithm.find for that:
>>>>>
>>>>> container.remove(find(container[], x).begin);
>>>>>
>>>>> Should work, and takes O(n) time.
>>>>>
>>>>> -Steve
>>>>
>>>> I don't really understand what's wrong with inefficient methods. You
>>>> can have inefficient methods that are convenient, like removing an
>>>> element by the default comparison, or giving it a delegate to match
>>>> the element(s) to remove.
>>>>
>>>> You profile your application. Is that method the bottle-neck? If so,
>>>> you change it to a more efficient one. If not, you are happy you had
>>>> that method there, performing in an inefficient way, but which doesn't
>>>> matter that much compared to, say, opening an SQL connection.
>>>>
>>>> Programmers want to program, fast. They have schedules, they need to
>>>> deliver. They don't need to always find the best solution. They can
>>>> find a compromise between "working" and "fast", move on, and later
>>>> profile and worry about what matters most.
>>>>
>>>> Programmers don't want to fight with the language or think "Oh, so to
>>>> remove an element I need to use this operation and combine it with
>>>> that one and with that other one"...
>>>
>>> Or use the right container for the job?
>>>
>>> Where it really comes into play is generic programming.
>>>
>>> Let's say I write some algorithm that removes certain elements from a
>>> container:
>>>
>>> removeElements(C, T)(C c, T t[]...)
>>> {
>>> foreach(x; t)
>>> c.remove(t);
>>> }
>>>
>>> What's the complexity of this algorithm? For a HashSet, for instance, it
>>> will be O(n) where n is the number of elements to remove.
>>>
>>> But for an ArrayList, it will be O(n*m) where m is the number of
>>> elements in c.
>>
>> But I'm sure in this algorithm I have for this app I'm making, my
>> collection won't have more than 50 elements. So everything will be
>> O(1). I need to remove an element from the collection. I really don't
>> care about the complexity of the operation, because if n is 50,
>> everything is O(1).
>
> Then your specific application can use std.algorithm.find to implement
> the equivalent. Only the algorithm body changes, not the usage of the
> algorithm.
>
>>
>> Why can't I have an inefficient (for you) remove operation that, for
>> me, will be ok?
>
> I never said you couldn't (and I've even given examples of such
> implementations). It's just not neatly packaged into a method.
>
> But again, if the method is exactly the same as the efficient version
> for other containers, it becomes *impossible* to design an algorithm
> that guarantees any sort of complexity. As I said before, quadratic sort
> is epic fail, and needs to always be avoided.
>
> I'll give you a scenario:
>
> People often complain that Linked List does not have an opIndex on it.
> Yes it's inefficient, but so what? "I know it's inefficient, let me
> decide whether it's worth it or not."
>
> So let's say I add it to LinkList. Those people are happy.
>
> But now, LinkList becomes defined as a *random-access-range* according
> to std.ranges. Therefore, std.algorithm.sort(linklist) compiles! And is
> now something like O(n^3).
>
> Whereas LinkList already defines a sort method, which uses mergesort
> (O(nlgn)). So are you going to realize this when reading someones code
> and you see:
>
> sort(somelist);
>
> That it's going to be horribly inefficient? Why shouldn't we strive for
> a library where such things just don't compile?
>
>> I don't want to spend 2 hours browsing the ranges algorithms to figure
>> out how to combine them to remove an element...
>
> You severely exaggerate the amount of time needed to browse the
> algorithms. I wrote an equivalent in less than a minute. And I don't
> even look at std.algorithm maybe once every few months (and didn't look
> at it to write the solution).
>
>> My point is, as someone else said it in another post: add inefficient
>> operations and tell the programmer so. Then he can decide what to do.
>> If he's sure that that performance penalty is not a big issue for him,
>> he'll be happy to have that method available.
>
> The operation is available using std.algorithm. There is no need to
> reimplement it as a method, sanctioned by the container. As I said
> before, if you find yourself wanting to remove specific elements from a
> container, perhaps Array is not the smartest choice for a container.
> There are plenty of others.
>
> There is something to be said for a language/library that discourages or
> prevents you from writing dumb code. It means that I'm that much more
> confident a piece of code written in that language is more efficient
> than one written in another language.
>
> -Steve

Hello.

You generally arguing this is all nice and good, but this is a very specific case.

I am using a LinkList because in my code, the elements are iterated over a million times and during this, I add stuff in-between elements all the time. However, I will be removing stuff *very* rarely. I am thus using the appropriate container and it doesn't matter whether the remove will be inefficient.

To put it another way: if removing elements was of crucial importance to the performance of my code in the first place, I wouldn't (and shouldn't) be using a LinkList. Therefore, implementing an inefficient method which does this won't be of consequence. Finally, the fundamental statement I'm trying to make here is: adding and removing *single* elements should be a straightforward method call for *any* container.

As a side note, your example about generic programming is really neat and makes sense; personally, I would never want a linked list with indexes and it's also a horrible analogy to the complaint at hand.

/Max

On 11/2/2011 10:41 PM, Steven Schveighoffer wrote:
>

> Then your specific application can use std.algorithm.find to implement
> the equivalent. Only the algorithm body changes, not the usage of the
> algorithm.
>

This is the root of the problem. How are we supposed to know that we need something from std.algorithm to remove something from a container in std.container? It's non-intuitive and non-obvious unless you already have more than a passing familiarity with ranges. If we can't have remove(element) on a container, then we need some good documentation in the std.container module that points the way.

On Thursday, November 03, 2011 16:41:27 Mike Parker wrote:
> On 11/2/2011 10:41 PM, Steven Schveighoffer wrote:
> > Then your specific application can use std.algorithm.find to implement the equivalent. Only the algorithm body changes, not the usage of the algorithm.
> 
> This is the root of the problem. How are we supposed to know that we need something from std.algorithm to remove something from a container in std.container? It's non-intuitive and non-obvious unless you already have more than a passing familiarity with ranges. If we can't have remove(element) on a container, then we need some good documentation in the std.container module that points the way.

It's quite clear that we need to do a better job getting the concept of ranges across (probably with at least one explanatory article) and that std.container's documentation needs improvement.

- Jonathan M Davis

On 2011-11-03 08:41, Mike Parker wrote:
> On 11/2/2011 10:41 PM, Steven Schveighoffer wrote:
>>
>
>> Then your specific application can use std.algorithm.find to implement
>> the equivalent. Only the algorithm body changes, not the usage of the
>> algorithm.
>>
>
> This is the root of the problem. How are we supposed to know that we
> need something from std.algorithm to remove something from a container
> in std.container? It's non-intuitive and non-obvious unless you already
> have more than a passing familiarity with ranges. If we can't have
> remove(element) on a container, then we need some good documentation in
> the std.container module that points the way.

What about having a remove method on a container that calls remove in std.algorithm, just as a convenience.

-- 
/Jacob Carlborg

Dmitry Olshansky wrote:

> And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day.
> 

To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N).

I still think the interface to container lacks a important feature here.

On Thu, 03 Nov 2011 03:41:27 -0400, Mike Parker <aldacron@gmail.com> wrote:

> On 11/2/2011 10:41 PM, Steven Schveighoffer wrote:
>>
>
>> Then your specific application can use std.algorithm.find to implement
>> the equivalent. Only the algorithm body changes, not the usage of the
>> algorithm.
>>
>
> This is the root of the problem. How are we supposed to know that we need something from std.algorithm to remove something from a container in std.container? It's non-intuitive and non-obvious unless you already have more than a passing familiarity with ranges. If we can't have remove(element) on a container, then we need some good documentation in the std.container module that points the way.

The primitive for a container is remove(range).  Ranges are essential to containers, and should be the major interface to them.  remove(value) translates to remove(findRangeFor(value)).  I'm asserting that we should not promote this "shortcut" if it's unavoidably linear in nature, otherwise, remove(value) has the stigma of being slow, even for containers which can do it quickly.  It's not the only choice, and there are ways to argue both sides.  But the fact that one can still do this using std.algorithm makes it at least so you can have the best of both worlds -- it's difficult to do, not impossible, but we can still develop generic code with complexity guarantees.

I agree the documentation needs more care.  I think std.container suffers from neglect in other areas too.  I argued this position, however, because even though it's not spelled out in std.container's docs, it *is* the position std.container is taking.

-Steve

On Wed, 02 Nov 2011 19:24:03 -0400, Max Wolter <awishformore@gmail.com> wrote:

> On 11/2/2011 2:41 PM, Steven Schveighoffer wrote:

>> I never said you couldn't (and I've even given examples of such
>> implementations). It's just not neatly packaged into a method.
>>
>> But again, if the method is exactly the same as the efficient version
>> for other containers, it becomes *impossible* to design an algorithm
>> that guarantees any sort of complexity. As I said before, quadratic sort
>> is epic fail, and needs to always be avoided.
>>
>> I'll give you a scenario:
>>
>> People often complain that Linked List does not have an opIndex on it.
>> Yes it's inefficient, but so what? "I know it's inefficient, let me
>> decide whether it's worth it or not."
>>
>> So let's say I add it to LinkList. Those people are happy.
>>
>> But now, LinkList becomes defined as a *random-access-range* according
>> to std.ranges. Therefore, std.algorithm.sort(linklist) compiles! And is
>> now something like O(n^3).
>>
>> Whereas LinkList already defines a sort method, which uses mergesort
>> (O(nlgn)). So are you going to realize this when reading someones code
>> and you see:
>>
>> sort(somelist);
>>
>> That it's going to be horribly inefficient? Why shouldn't we strive for
>> a library where such things just don't compile?
>>
>
> Hello.
>
> You generally arguing this is all nice and good, but this is a very specific case.
>
> I am using a LinkList because in my code, the elements are iterated over a million times and during this, I add stuff in-between elements all the time. However, I will be removing stuff *very* rarely. I am thus using the appropriate container and it doesn't matter whether the remove will be inefficient.

A linked list (any list really) is important if you want to maintain insertion order.  If that's not important, don't use a list, a hash or tree is about as efficient.  There exist (not in D) hybrid container types that allow O(1) removal using value, and maintain insertion order.

In fact, the actual remove is not inefficient if you have a reference to an element (not just the value).  Unfortunately, for SList, this is not the case, but it should be fixed at some point.

But I still maintain, anything in std.container is not just a container for your code, it's a container that tries to cater to the most common needs.  If you want a remove(value) function, it is trivial to write.

> To put it another way: if removing elements was of crucial importance to the performance of my code in the first place, I wouldn't (and shouldn't) be using a LinkList.

As long as you don't need to search for the element to remove using its value, removal in a linked list should be O(1).  A linked list that does not allow O(1) removal and O(1) insertion given a topological reference is a failure (yes, that includes the current version of SList).

> Therefore, implementing an inefficient method which does this won't be of consequence. Finally, the fundamental statement I'm trying to make here is: adding and removing *single* elements should be a straightforward method call for *any* container.

Adding, yes.  Removing a container-selected element, yes.  Removing a *specific* element, no.  Inserting an element in a *specific location*, no.  std.container has taken the stance that primitives should reflect the efficiency of the operation.

This is not the only valid position to have.  It's just std.container's position.  For example, Java allows this.

> As a side note, your example about generic programming is really neat and makes sense; personally, I would never want a linked list with indexes and it's also a horrible analogy to the complaint at hand.

People have asked for it and argued vigorously for it on this newsgroup, just as you are arguing for this.

-Steve