Php: what complexity [i.e O(N), O(1), ...] the the square brackets add function has? i.e $x[] = 'value'

Question

Imagine you are adding several elements to an array:

$array[] = 'dog';
$array[] = 'cat';
$array[32] = 'lachupacabra';
$array[] = 'cow';

Do you know what index the 'cow' will have? No? Neither did I until I've found out that it's 33. This seems logical, php should have a reference to the last element added to array, and while adding element with square brackets syntax it takes previous element, takes it's index increments it by one and associates the incremented index with the new value. But stop, this might cause trouble if the incremented index was added earlier. Example:

$array[] = 'dog';
$array[33] = 'cat';
$array[32] = 'lachupacabra';
$array[] = 'cow';

Gues what, the index of 'cow' is 34. Does it mean that php tests all keys before adding another one with the square brackets syntax? This will have O(N) complexity or is it storing something like $max_key value somewhere inside, the operation will have O(1) complexity but will use extra memory?

Question #1: What complexity the '[]' operation has?

Question #2: How the hell it is possible to get the index that the element was added at?

(Regarding Question#2 I'd prefer the O(1) operation if you don't mind)

EDIT

I need to implement the following method:

class X {

private $array;

public function AddItem($item) {
    $array[] = 'new value';

    return get_highest_index_with_o_1_comlexity($array);
}

public function RemoveItem($index) {
    unset($this->array[$index]);
}
}

NikiC · Accepted Answer · 2011-02-03 19:56:23Z

2

To get the key of the last element in an array use:

end($array);
$key = key($array);

end positions the cursor on the last element of the array, key returns the key at the current cursor position.

answered Feb 3, 2011 at 19:56

NikiC

102k39 gold badges194 silver badges226 bronze badges

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

2 Comments

Lu4 Over a year ago

I suppose there is no specialized single function in php that would do the same? Changing internal pointers of an array for just to getting the last index?

NikiC Over a year ago

@Lu4: No, there is no specialized function. But if you want, you can reset the pointer to the first element, after you're done.

Byron Whitlock · Accepted Answer · 2011-02-03 19:57:27Z

0

PHP uses the (largest index + 1) as the next index when using []. For example, If you had $arr = array(42 => 'foo') then the next element assigned would have the key 43. Array inserts happen in constant time. It's extremely silly to worry about this.

edited Feb 3, 2011 at 19:57

Byron Whitlock

54.2k29 gold badges128 silver badges170 bronze badges

answered Feb 3, 2011 at 19:47

mfonda

8,0431 gold badge29 silver badges30 bronze badges

2 Comments

mfonda Over a year ago

@nikic's method will give you the last key, end($arr) will give you the last element. Seems like you're doing something in the wrong order if you care about the last key.

Lu4 Over a year ago

I've added element to an array, i want to know the index, to remove it afterwards (if required)

Collectives™ on Stack Overflow

Php: what complexity [i.e O(N), O(1), ...] the the square brackets add function has? i.e $x[] = 'value'

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related