[일반] 중간 삽입 및 삭제와 랜덤 엑세스가 모두 빠른 컨테이너가 있나요?

[익명(211.184)]

중간 삽입, 삭제가 적어도 amortized O(log N)으로 돌지만, 랜덤 액세스는 O(1)인 컨테이너는 없겠죠?

[익명(211.208)]

그나마 해시맵이 님이 말한거에 제일 가까운듯 한데, 해시맵도 완벽한 O(1)은 아닌지라

[익명(211.208)]

완벽한 컨테이너가 있었다면 다들 그걸 쓰지 지금처럼 용도에 따라 배열 리스트 트리 이런식으로 구분해서 쓰지 않았을듯

[익명(221.141)]

랜덤액세스 lgn까지야 가능한데 1은 그냥 이론적으로 안 됨. 되려면 삽입삭제가 n이어야됨